# LP Duality. What is the correct dual to this linear program?

Suppose a linear program that is defined as follows with decision variables $$w, x, y, z$$ and parameters $$a, b, c_j, d_i$$.

$$\min \sum_{I}^{} a x_{i} + \sum_{I}^{} b y_{i}$$

$$s.t.$$

$$x_{i} \geq w + \sum_{J}^{} c_{j} z_j - d_i \ \forall i \in I$$

$$y_{i} \geq d_i - w + \sum_{J}^{} c_{j} z_j \ \forall i \in I$$

$$x_{i}, y_{i} \geq 0 \ \forall i \in I$$, $$w \in \mathbb{R}$$, $$z_j \in \mathbb{R} \ \forall j \in J$$

I get to the following with $$u_i$$ and $$v_i$$ as dual variables for the constraints

$$\max - \sum_{I}^{} d_i u_{i} + \sum_{I}^{} d_i v_{i}$$

$$s.t.$$

$$u_{i} \leq a \ \forall i \in I$$

$$v_{i} \leq b \ \forall i \in I$$

$$- \sum_{I}^{} u_{i} + \sum_{I}^{} v_{i} \leq 0$$

$$- \sum_{J}^{} c_j u_{i} + \sum_{J}^{} c_j v_{i} \leq 0 \ \forall i \in I$$

$$u_{i}, v_i\geq 0 \ \forall i \in I$$

but I am not sure how to correctly account for z and c of the primal. Is the above formulation complete and correct?

• You didn't list $w$ among the decision variables or parameters. Is $w$ a free variable? Dec 21, 2022 at 21:11
• $w$ is also a decision variable, edited the question accordingly. Thanks for the hint! Dec 22, 2022 at 9:04

Rewrite the primal problem in standard form with the dual variables in parentheses: \begin{align} &\text{minimize} &\sum_i (a x_i + b y_i) \\ &\text{subject to} &x_i - w - \sum_j c_j z_j &\ge -d_i &&\text{for all i} &(u_i \ge 0)\\ &&y_i + w - \sum_j c_j z_j &\ge d_i &&\text{for all i} &(v_i \ge 0) \\ &&x_i &\ge 0 &&\text{for all i} \\ &&y_i &\ge 0 &&\text{for all i} \end{align}
The dual problem is (with the primal variables in parentheses): \begin{align} &\text{maximize} &\sum_i (-d_i u_i + d_i v_i) \\ &\text{subject to} & u_i &\le a &&\text{for all i} &(x_i \ge 0)\\ && v_i &\le b &&\text{for all i} &(y_i \ge 0) \\ && \sum_i(-u_i + v_i) &= 0 && &(\text{w free}) \\ && -c_j \sum_i (u_i + v_i) &= 0 &&\text{for all j} &(\text{z_j free}) \\ &&u_i &\ge 0 &&\text{for all i} \\ &&v_i &\ge 0 &&\text{for all i} \end{align}
• I have to change the original problem to where now the two constraints read $x_{i} - w - \sum_{J}^{} c_{ij} z_j \geq - d_i \ \forall i$ and $y_{i} + w + \sum_{J}^{} c_{ij} z_j \geq d_i \ \forall i$. In this edit parameter $c_{ij}$ has a second index and there is a sign change in the second constraint. For the dual problem that leads me to $\sum_{i} c_{ij} (-u_i + v_i) \ \forall j$ as the last constraint (while the others stay as defined in your answer) but it seems that there is a mistake, at least numerical comparison of primal and dual objectives suggests so. Jan 11 at 10:43
• Sure. With $d = [1,2,3,4,5], c = [[6,7,8,9,10],[11,12,13,14,15],[16,17,18,19,20]], a = 0.4, b = 0.2$ I find a primal objective of $1.125$ but get a dual objective of $-1.110$ Jan 12 at 13:14
• With your sample data, the optimal objective value is $0$, attained, for example, by $w=0$, $z_1=1.5$, $z_3=-0.5$, and $x_i=y_i=0$ for all $i$. Maybe you have a sign wrong somewhere. Or maybe something is wrong with your $c_{ij}$ indexing. You have given a $3 \times 5$ matrix, but $c$ should be $5 \times 3$. Jan 12 at 15:41