The primal problem has a unique solution while the dual problem has many solutions

Question

Is it possible that the primal problem has a unique solution while the dual problem has many solutions? If so, does this situation have a particular name?

Answer 1

Yes, this is possible. In linear programming, when there are degenerate constraints at the unique optimal solution to the primal LP, there will be multiple optimal dual solutions.

For example, consider the primal LP

$\max x_{1} + x_{2}$

subject to

$x_{1} \leq 1$

$x_{2} \leq 1$

$x_{1}+2x_{2} \leq 3$

$2x_{1}+x_{2} \leq 3$

$x_{1}, x_{2} \geq 0$

The primal has only one optimal solution: $x_{1}=1$, $x_{2}=1$, with optimal objective value 2.

The dual of this LP is

$\min y_{1}+y_{2}+3y_{3} + 3y_{4}$

subject to

$y_{1}+y_{3}+2y_{4} \geq 1 $

$y_{2} + 2y_{3} + y_{4} \geq 1$

$y \geq 0$

There are infinitely many optimal dual solutions, including

$y=[1, 1, 0, 0]$

$y=[0, 0, 1/3, 1/3]$

$y=[1/2, 1/2, 1/6, 1/6]$

$\ldots$

Geometrically, degeneracy at the optimal basic feasible solution in the primal problem (more than $m$ constraints are active at a particular basic feasible solution) results in multiple dual solutions, corresponding to different bases in the primal, plus convex combinations of these dual basic solutions.