8
$\begingroup$

Simple question-

Is it possible for a linear programming optimization problem possible to have a degenerate optimal solution whereas the dual has a unique optimal solution? I can't find a scenario where this is possible but intuitively it seems that it is possible.

$\endgroup$
15
$\begingroup$

The answer is yes, but only if there are other optimal solutions than the degenerate one. For example, suppose the primal problem is

$$\max x_1 + x_2$$ subject to $$x_1 \leq 1,$$ $$x_1 + x_2 \leq 1,$$ $$x_1, x_2 \geq 0.$$

The solution $(1,0)$ is optimal and degenerate, but every solution $(a,1-a)$, for $0 \leq a \leq 1$ is also optimal.

The dual is

$$\min y_1 + y_2$$ subject to $$y_1 + y_2 \geq 1,$$ $$y_2 \geq 1,$$ $$y_1, y_2 \geq 0.$$

The dual has the unique (degenerate) optimal solution $(0,1)$. So we do have a situation with a degenerate optimal solution in the primal but a unique dual optimal.

However, if the degenerate optimal solution is unique, then there must be multiple optimal solutions in the dual. The following table is from Sierksma's Linear and Integer Programming: Theory and Practice, Volume 1, page 144.

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
$\endgroup$
  • $\begingroup$ Why only if? If there are other solutions, then yes (math.stackexchange.com/questions/1049796/…). But why is the converse true? $\endgroup$ – BCLC Dec 23 '14 at 6:33
  • $\begingroup$ Could there be a primal with both a degenerate optimal solution and a non-degenerate one where the dual has multiple solutions? $\endgroup$ – Ofer Magen Nov 15 '18 at 0:39
2
$\begingroup$

If an optimal solution is degenerate, then a) There are alternative optimal solutions b) The solution is infeasible c) The solution is of no use to the decision- maker d) None of the above

$\endgroup$
0
$\begingroup$

Proof 1: 1) Consider a minimization LP in standard form.If there exits a nondegenerate optimal bfs for this LP,then the dual LP will have a unique optimial solution.

Proof 2: 2) consider a minimization LP in standard form.If the primal LP has a unique optimal solution,then the dual LP will have a non-degenerate optimal solution.

$\endgroup$

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.