# Degeneracy, redundant constraints, multiple optimal solutions in LP

I am not sure about the relationship among degeneracy, redundant constraints, and multiple optimal solutions in linear programming problems. In the book INTRODUCTION TO OPERATIONS RESEARCH by Hillier and Lieberman, 7th edition, page 130, the authors says,

Whenever a problem has more than one optimal BF solution, at least one of the nonbasic variables has a coefficient of zero in the final row 0, so increasing any such variable will not change the value of objective function.

Note that this statement is made in terms of a simplex tableau, which from what I understand is saying, an LP has multiple optimal solutions if it has degeneracy.

However, let's consider the following problem:

$$\text{minimize: } x_1 + x_2$$ Subject to, $$x_1+x_2 = 2$$ $$x_1-x_2 = 2$$ $$x_1 = 2$$ $$x_1,x_2\geq0$$

Here, we have redundant constraints since all three lines meet at a single point but the optimal solution is unique $$(2,0)$$.

Is there anything wrong with my understanding of the above problem?

Whenever we encounter degeneracy in the simplex method, can we conclusively say anything about having redundant constraints and/or multiple optimal solutions?

In my opinion, your constraints do not represent the situation. You can have more than one optimal basic solution if the slope of the objective function is equal to one of the constraints. Then the objective function lies on a line, between two corners of the feasible region. I give you an example with the corresponding graph:

$$\textrm{max} \ Z=500x_{1}+300x_{2}$$

s.t.

$$15x_{1}+5x_{2}\leq 300$$

$$10x_{1}+6x_{2}\leq 240$$

$$8x_{1}+12x_{2}\leq 450$$

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

The corresponding graph is

To make the graph we have to solve the (in-)equalities for $$x_2$$. I focus on the the objective function and on the constraint with the same slope.

1. $$\textrm{Objective function}$$

$$Z=500x_{1}+300x_{2}$$

$$Z-500x_{1}=300x_{2}$$

$$\frac{Z}{300}-\frac53x_1=x_2$$

The slope is $$-\frac53$$

2. $$\textrm{Second constraint}$$

$$6x_{2}\leq 240-10x_{1}$$

$$x_{2}\leq 40-\frac{10}6x_{1}$$

The slope is $$-\frac53$$ as well.

So you may have multiple solution if at least one of the constraints have the same slope as the objective function. In this case you have two optimal BFS: $$(x_1,x_2)=\left(\frac52, \frac{215}{6} \right), (x_1,x_2)=\left(15, 15 \right)$$

And between the two corners on the green line the solution are optimal as well. The multiple optimal solution can be written as $$(x_1^*,x_2^*)=\left(x_1, \ 40-\frac{10}6x_{1}\right) \ \ \forall \ \frac52 \leq x_1\leq 15$$

• So, in your example, there is no connection between having multiple optimal solutions and degeneracy? Commented Oct 10, 2022 at 1:54
• No. The quoted paragraph does not mention degenration at all. Commented Oct 10, 2022 at 2:25
• got it, thanks!! Commented Oct 10, 2022 at 2:43
• @T_k That's fine. Then mark the answer as accepted. Thanks. Commented Oct 10, 2022 at 2:57