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.

In linear programming, an LP can have multiple optimal solutions if it contains degenerate vertices, i.e. where one of the base-variables is 0.

Can an LP also have multiple optimal solutions if it does not contain degenerate solutions? If so, what is an example LP?

share|improve this question

2 Answers 2

up vote 3 down vote accepted

Yes. A simple example is

$$\max x_1 + x_2$$

subject to

$$ x_1 + x_2 \leq 1,$$ $$ x_1, x_2 \geq 0.$$

The level curves of the objective function are parallel to the boundary of the constraint $x_1 + x_2 \leq 1$, and so every point on the line segment $x_1 + x_2 = 1$ with $x_1, x_2 \geq 0$ is optimal.

This example gives you the general case: You can have multiple, nondegenerate optimal solutions if the level surfaces of the objective function are parallel to one of the constraint inequalities.

There's an interesting connection with the dual problem, too. If the original problem has multiple, nondegenerate optimal solutions, then the dual problem must have a unique, degenerate optimal solution.

share|improve this answer

Consider a 2-dim case. In this case, degeneracy corresponds to having a couple of lines passing through the optimal corner. On the other hand, an optimal corner is non-degenerate if it is at the intersection of only two lines.

Now consider the issue of whether there is unique/multiple solution(s). Again from a geometric point of view, the case of multiple solution happens when the objective line is parallel to one of the constraint lines. Otherwise, there is a unique solution (if there is any solution at all).

Since the above geometric descriptions are not directly related to each other, I would expect all the four cases:

  • non-degenerate / unique solution
  • degenerate / unique solution
  • non-degenerate / multiple solutions
  • degenerate / multiple solutions

to be possible.

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.