11
$\begingroup$

I have a given formulation that looks like this (just for the constraints):

$$\sum_i \beta_{i,j} \geq \alpha_j,\qquad\forall j$$ $$\alpha_j \geq \sum_i f_{i,j},\qquad\forall j$$ $$\alpha_j \geq 0, f_{i,j} \geq 0$$

In order to reduce the size of my formulation, I eliminated the variable $\alpha_j$ by the means of a valid inequality (may I call it a projection?):

$$\sum_i \beta_{i,j} \geq \sum_i f_{i,j},\qquad\forall j$$ $$f_{i,j} \geq 0$$

However, I am now interested in the dual values for each of these constraints (actually, just $\sum_i \beta_{i,j} \geq \alpha_j$). How these dual values are related to the ones of the reformulation (mostly $\sum_i \beta_{i,j} \geq \sum_i f_{i,j}$)?

$\endgroup$
3
  • $\begingroup$ Do the $\alpha_j$ variables appear in any other constraints or in the objective? Is the reduced formulation equivalent to the original formulation (projected on the $\beta_{i,j}$ and $f_{i,j}$ variables), or is it a relaxation? $\endgroup$ Aug 6, 2019 at 17:26
  • 1
    $\begingroup$ The $\alpha_j$ are only used in these two constraints. The new formulation is equivalent to the original one, it is not a relaxation. $\endgroup$
    – dourouc05
    Aug 6, 2019 at 22:55
  • $\begingroup$ I propose to use the term "reformulation" or "projection" instead of "valid inequality" here. Valid inequalities to me are inequalities that are used to strengthen the LP, which is not the case here. $\endgroup$ Aug 7, 2019 at 11:34

1 Answer 1

9
$\begingroup$

For simplicity, I will

  • replace $\sum_i \beta_{i,j}$, $ \sum_i f_{i,j}$, and $\alpha_j$ by $x$, $y$, and $z$, respectively.
  • assume that $x$, $y$, and $z$ are defined to be non-negative.
  • assume that $x$ has a coefficient $c$ in the objective, and $y$ has a coefficient $d$ in the objective.

That is, we consider the following program, with the dual variables in parenthesis: $$\begin{align} \min &~cx + dy\\ x & \ge z & (\lambda)\\ z & \ge y & (\mu)\\ x, y, z & \ge 0. \end{align}$$ The dual program is given by $$\begin{align} \max & ~0 \\ \lambda & \le c\\ \mu & \ge -d\\ \lambda & \ge \mu\\ \lambda, \mu & \ge 0. \end{align}$$

Similarly, we can consider the smaller formulation: $$\begin{align} \min &~cx + dy\\ x & \ge y & (\gamma)\\ x, y & \ge 0, \end{align}$$ with dual $$\begin{align} \max & ~0 \\ \gamma& \le c\\ \gamma & \ge -d\\ \gamma & \ge 0. \end{align}$$

Given a feasible dual solution $\gamma$ for the second formulation, we can always obtain a dual feasible solution for the first formulation by using $\lambda = \gamma$ and $\mu = \max\{0,-d\}$. Note that other choices for $\lambda$ and $\mu$ may also be possible.

Verification:

Let $\gamma$ be a dual feasible solution to the second formulation, and let $\lambda = \gamma$ and $\mu = \max\{0,-d\}$. Now, we check the constraints of the dual of the first formulation:

  • $\lambda \le c \Leftrightarrow \gamma \le c$, follows from dual feasibility of $\gamma$.
  • $\mu \ge -d \Leftrightarrow \max\{0,-d\} \ge -d$, holds by definition.
  • $\lambda \ge \mu \Leftrightarrow \gamma \ge \max\{0,-d\}$, follows from dual feasibility of $\gamma$.
  • $\lambda \ge 0 \Leftrightarrow \gamma \ge 0$, follows from dual feasibility of $\gamma$.
  • $\mu \ge 0 \Leftrightarrow \max\{0,-d\} \ge 0$, holds by definition.
$\endgroup$
3
  • $\begingroup$ Thanks for your answer, very detailed! Just one more thing: knowing $\gamma$, can you tell anything else about $\lambda$ and $\mu$? That would be my use case: solve the smaller problem, get $\gamma$, compute (cheaply) one of $\lambda$ or $\mu$. $\endgroup$
    – dourouc05
    Aug 7, 2019 at 13:54
  • $\begingroup$ @dourouc05 When I went over my answer, I spotted a mistake: $\gamma = \lambda - \mu$ may not be feasible if $d < 0$. As you are interested in the other direction, I removed the faulty part and instead explain how to obtain $\lambda$ and $\mu$ from $\gamma$. Do note that $\lambda$ and $\mu$ need not be unique for a given $\gamma$, so asking for 'the' dual values of the constraints may not be meaningful. $\endgroup$ Aug 7, 2019 at 14:29
  • 1
    $\begingroup$ Thank you for the detail! $\endgroup$
    – dourouc05
    Aug 7, 2019 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.