# Can a non-degenerate LP have multiple optimal solutions?

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?

-

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.

-

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.

-