How to relate dual values of valid inequality to the dual values of the original problem?

Question

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}$)?

Answer 1

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.