0

Let $P$ be a minimization primal problem $\min c^T x$ and let $P^*$ be its dual.

I've been wondering about the following:

Suppose $P$ has exactly $n$ optimal solutions.

I know that $P^*$ also has an optimal solution $\bar u$ with the same objective value by Strong Duality.

Does $P^*$ also has exactly $n$ optimal solutions then ?

I know about Complementary Slackness, but haven't yet come across an example where the equality doesn't hold.

Shuzheng
  • 5,533
  • In linear programming you have one optimal solution (intersection of two or more constraints). Or you have infinite number of optimal solutions, if the objective function lies on a constraint. Thus you cannot have n optimal solutions. – callculus42 Nov 14 '14 at 13:07
  • The optimal solution may not be unique ! – Shuzheng Nov 14 '14 at 14:04
  • This is what I wrote. You can have an infinite number of optimal solutions. – callculus42 Nov 14 '14 at 14:15

0 Answers0