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$
  • $\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$ – Kevin Dalmeijer Aug 6 '19 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 '19 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$ – Kevin Dalmeijer Aug 7 '19 at 11:34
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.
| improve this answer | |
$\endgroup$
  • $\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 '19 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$ – Kevin Dalmeijer Aug 7 '19 at 14:29
  • 1
    $\begingroup$ Thank you for the detail! $\endgroup$ – dourouc05 Aug 7 '19 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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