The answer here mentioned a table from Sierksma's $\textit{Linear and Integer Programming: Theory and Practice}$, Volume 1, page 144. Both primal and dual are under standard form in table below (Here is the link to the book):

Primal Optimal Solution                     Dual Optimal Solution
(a) Multiple                     implies    Degenerate
(b) Unique and nondegenerate     implies    Unique and nondegenerate
(c) Multiple and nondegenerate   implies    Unique and degenerate
(d) Unique and degenerate        implies    Multiple

However, my friend shows me an example seems to conflict with case(d). Here is the primal $$ \begin{aligned} \min \quad x_1 &+ x_2\\ \text{s.t.}\quad \quad & \\ x_1 &= 1\\ x_1 + x_2 &= 1\\ x_1 \geq 0,\ &x_2 \text{ is free.} \end{aligned} $$ and here is the dual $$ \begin{aligned} \max \quad y_1 &+ y_2\\ \text{s.t.}\quad \quad & \\ y_1 + y_2 &\leq 1\\ y_2 &= 1\\ y_1,y_2 &\text{ are free.} \end{aligned} $$

Primal problem has unique degenerated optimal solution $x_1 = 1,x_2 =0$ and the dual also has unique degenerated optimal solution $y_1 = 0,y_2 =1$. (Although with the slack variable, we have two bases corresponding to the dual optimal solution). It seems like there is no other assumptions for the case(d), is there anything wrong with the example above?

  • $\begingroup$ But there are infinitely many solutions to the dual. Write the first constraint as $y_1+y_2+s=1$, with $s\geqslant 0$, then from $y_2=1$ we have $y_1+s=0$ and so $y_1=-s$, where $y_1$ is unrestricted in sign. $\endgroup$ – Math1000 Oct 16 '19 at 16:41
  • $\begingroup$ @Math1000 This is true but the table only includes optimal solutions and in this case I believe $y_1$ has to be 0 in order to maximize $y_1 + y_2$. I added a link to the book in the question. $\endgroup$ – Firepanda Oct 16 '19 at 22:20

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.