0
$\begingroup$

I am trying to understand weak and strong duality given a toy example LP program, which is to:

maximize $m_D$D + $m_L$L

s.t.
0.3 L + $\ \ \ \ \ \ \ \ $D $\leq$ 1
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $ D $\leq$ 0.9
$\ \ \ \ \ $ L + 0.25 D $\leq$ 1
0.7 L + 0.70 D $\leq$ 1

introducing slack variables:

maximize $m_D$D + $m_L$L + $b_3y_3$ + $b_4y_4$ + $b_5y_5$ + $b_6y_6$ (with $b_3, b_4, b_5, b_6$ = 0)

s.t.
0.3 L + $\ \ \ \ \ \ \ \ $D + $y_3$ $\ \ \ \ \ $$\ \ \ \ \ $$\ \ \ \ \ $= 1
$\ \ \ \ \ $$\ \ \ \ \ \ \ \ \ $$\ \ \ \ \ $ D $\ \ \ \ \ $+$y_4$ $\ \ \ \ \ $$\ \ \ \ \ $= 0.9
$\ \ \ \ \ $ L + 0.25 D $\ \ \ \ \ $$\ \ \ \ \ $+ $y_5$ $\ \ \ \ \ $= 1
0.7 L + 0.70 D $\ \ \ \ \ $$\ \ \ \ \ $$\ \ \ \ \ $+$y_6$ $\ $= 1

I take the above as the dual because the primal (standard) is to $minimize$. However then I get too few equations in the primal because there are more coefficients ($b$) than constraints (in A) (?) and I don't know how or why the order between the dual and primal should correspond(?):

minimize $x_1$ + 0.9$x_2$ + $x_3$ + $x_4$

s.t.
0.3 $x_1$ + $\ \ \ \ \ \ \ \ $$x_2$ + $x_3$ $\ \ \ \ \ \ $$\ \ \ \ \ \ $$\ \ \ \ \ $= $m_D$
$\ \ \ \ \ \ $$\ \ \ \ \ \ \ \ \ \ \ $$\ \ \ \ \ $$x_2$ $\ \ \ \ \ \ $+ $x_4$ $\ \ \ \ \ \ $$\ \ \ \ \ $= $m_L$
$\ \ \ \ \ \ $$x_1$ + 0.25 $x_2$ $\ \ \ \ \ \ $$\ \ \ \ \ \ $+ $x_5$ $\ \ \ \ \ \ $= $b_3$
0.7 $x_1$ + 0.70 $x_2$ $\ \ \ \ \ \ $$\ \ \ \ \ \ $$\ \ \ \ \ \ $+ $x_6$ = $b_4$

(what about $b_5$ and $b_6$ and why would these first two equations pair with $m_D$ and $m_L$?)

What I did was to match my toy problem to a textbook primal dual formulaic description to derive the above.

$\endgroup$
  • $\begingroup$ You should probably look at the indicator variables in the augmented form. $\endgroup$ – Julius Baer Oct 22 '19 at 19:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.