Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

up vote 9 down vote accepted

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
share|improve this answer

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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