1
$\begingroup$

Suppose a linear program that is defined as follows with decision variables $x_i, y_i z$ and parameters $a, b, c_i$.

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

$s.t.$

$x_{i} \geq z - c_i \ \forall i \in I$

$y_{i} \geq c_i - z \ \forall i \in I$

$x_{i}, y_{i} \geq 0 \ \forall i \in I$

$z\geq 0$

I now want to find the dual problem. I get to the following with $u_i$ and $w_i$ as dual variables.

$\max - \sum_{I}^{} c_i u_{i} + \sum_{I}^{} c_i w_{i} $

$s.t.$

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

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

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

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

Solving the problem (Gurobi) for some parameter combination (To give a numerical example, suppose that $a = 5$, $b = 95$ and $c = [5,8,6,3,9,6,10,4,9, 11]$), the objective values of the two problems are not identical, however. Thus, there must be an error in the dual formulation, which I cannot find.

Where am I going wrong?

$\endgroup$

1 Answer 1

0
$\begingroup$

You have the correct dual formulation. For your sample data, the optimal objective values are both $195$. An optimal primal solution is \begin{align} x^* &= (6,3,5,8,2,5,1,7,2,0)\\ y^* &= (0,\dots,0) \\ z^* &= 11 \end{align} An optimal dual solution is \begin{align} u^* &= (5,5,5,5,5,5,5,5,5,0) \\ w^* &= (0,0,0,0,0,0,0,0,0,45) \end{align}

$\endgroup$
1
  • $\begingroup$ Thanks a lot for the confirmation! The error was actually hidden in my implementation. thanks! $\endgroup$
    – Mike Lang
    Commented Sep 9, 2021 at 8:09

You must log in to answer this question.

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