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

Question

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?

Answer 1

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}