Primal- degenerate optimal, Dual - unique optimal
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.
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
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