3
$\begingroup$

By the strong duality theorem we know that LP can have 4 possible outcomes:

  1. dual and primal are both feasible,
  2. dual is unbounded and primal is infeasible,
  3. dual is infeasible and primal is unbounded,
  4. dual & primal are both infeasible.

Given the primal program:

Maximize $z = a x_1 + b x_2$

subject to:

$c x_1 + d x_2 \leq e$

$f x_1 + g x_2 \leq h$

$x_1, x_2 \geq 0$

We can construct the dual program :

Minimize $w = e y_1 + h y_2$

subject to:

$c y_1 + f y_2 \geq a$

$d y_1 + g y_2 \geq b$

$y_1, y_2 \geq 0$

And my question is: is it possible to assign values for $a,b,c,d,e,f,g,h$ such that both primal and dual are infeasible?

I tried to came up with values but the case was always that one of them (dual or primal) was infeasible and the other was unbounded.

$\endgroup$
1
$\begingroup$

Take $(c,d,f,g)=(1,-1,-1,1)$ and $(a,b,e,h)=(1,0,0,-1)$. This way the primal constraints are $x_1-x_2\le 0$ and $-x_1+x_2\le -1$, which is equivalent to $x_1-x_2\ge 1$. Together we get $1 \le x_1 - x_2 \le 0$, which is impossible to satisfy.

Similarly, the dual constraints are $0\ge y_1-y_2\ge 1$.

$\endgroup$
  • $\begingroup$ Your Readers would benefit from a little more justification that both primal and dual are infeasible with these parameters. $\endgroup$ – hardmath May 12 '16 at 17:14
  • $\begingroup$ Thank you very much for your response, but when Im putting this variables in IORT tuttorial (mhhe.com/engcs/industrial/hillier/iortutorial/install/…) it states that model is unbounded, could you provide bit more explanation why with this variables primal and dual are infeasible? $\endgroup$ – Aleksandra May 12 '16 at 17:47
  • $\begingroup$ Maybe it's a bug in that program, @Aleksandra. You can check the very simple argument for infeasibility I added to the answer. $\endgroup$ – Omar Antolín-Camarena May 12 '16 at 18:11
0
$\begingroup$

You can get a more complete description of all the cases by arguing along the following lines: The feasible regions in both cases are the intersection of two half-spaces in the plane. (I am ignoring the nonnegative constraints on the coordinates). For such a region to be empty the lines defining the boundary should be parallel.

We can multiply each inequality by a positive number, without changing the region. So, it is enough to focus on the case where $c,f \in \{-1,0,+1\}$ from which all others can be obtained by rescaling. Consider the case where $c = 1$, then $f$ has be $-1$ for the the lines to be parallel and with possible non-empty intersection for the half-spaces. Now, if either of $d,g$ are anything but $\pm 1$, the lines in the dual won't be parallel, hence either $d = -1$ and $g = +1$ or vice versa. One an argue about the $0$ case similarly.

$\endgroup$
  • 1
    $\begingroup$ Do you mean that for such a region to be empty it is necessary (but not sufficient) that lines defining the boundary should be parallel? $\endgroup$ – Omar Antolín-Camarena May 13 '16 at 19:13
  • $\begingroup$ @OmarAntolín-Camarena, Yes, it certainly is not sufficient, because the half-spaces could be nested, i.e., one of the inequalities is vacuous: for example, when $c = f$ and $d = g$. Then, if $e \ge h$, the first inequality is vacuous and vice versa. The condition seems necessary to me, unless you have a counter-example. $\endgroup$ – passerby51 May 13 '16 at 20:40
  • $\begingroup$ I was just trying to point out you wrote "non-empty" when you should have said "empty". For the intersection of two half planes to be empty you certainly need the lines to be parallel (and then for the half planes to "look in opposite directions"). $\endgroup$ – Omar Antolín-Camarena May 13 '16 at 21:02
  • $\begingroup$ @OmarAntolín-Camarena, Oh... I see. Thanks. Fixed. $\endgroup$ – passerby51 May 13 '16 at 23:10

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.