0
$\begingroup$

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?

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

1 Answer 1

1
$\begingroup$

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}

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Mike Lang
    Commented Jan 11, 2023 at 10:43
  • $\begingroup$ The dual change you suggested for the primal change looks correct to me. Do you have a small test instance that yields the unexpected behavior? $\endgroup$
    – RobPratt
    Commented Jan 11, 2023 at 13:27
  • $\begingroup$ 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$ $\endgroup$
    – Mike Lang
    Commented Jan 12, 2023 at 13:14
  • $\begingroup$ 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$. $\endgroup$
    – RobPratt
    Commented Jan 12, 2023 at 15:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .