An LP has infinitely many feasible solutions and infinitely many optimal solutions. Does this automatically mean the Simplex method must encounter degeneracy? Why or why not?
Welcome!
This community is for professionals and enthusiasts of our products and services.
Share and discuss the best content and new marketing ideas, build your professional profile and become a better marketer together.
This question has been flagged
8
Replies
49
Views
No, a problem having infinitely many feasible and optimal solutions does not mean the Simplex method must encounter degeneracy.
These two concepts describe completely different geometric properties of a linear programming problem. Infinitely many optimal solutions describe how the objective function aligns with an edge, while degeneracy describes how constraints intersect at a single corner point.
No. Infinitely many optimal solutions do not automatically mean degeneracy. Multiple optimal solutions can occur along an edge of the feasible region without any basic variable being zero.
No. Infinitely many optimal solutions do not automatically mean degeneracy. Multiple optima occur when the objective function is parallel to an edge or face of the feasible region, while degeneracy occurs when a basic variable is zero at a basic feasible solution; they are different special cases.
No, this does not automatically mean the Simplex method will encounter degeneracy.
No — infinitely many optimal solutions do NOT automatically mean degeneracy.
Infinitely many optimal solutions happen when the objective function runs parallel to an edge or face of the feasible region — a nonbasic variable has reduced cost = 0, but all basic variables remain strictly positive. Degeneracy, by contrast, means a basic variable = 0 at a corner point where too many constraints intersect, and only one optimal point exists. They are separate things: multiple optima come from the objective aligning with a boundary, degeneracy comes from overlapping constraints at a single vertex. The Simplex method can find an optimal corner point along that parallel edge with all positive basic variables — no degeneracy encountered at all.
No, not necessarily. Having infinitely many feasible and optimal solutions means the LP has alternative optimal solutions, but this does not automatically imply degeneracy. Degeneracy occurs when a basic feasible solution has at least one basic variable equal to zero. An LP can have infinitely many optimal solutions along an edge while all the relevant basic solutions remain nondegenerate. Thus, multiple optimal solutions and degeneracy are different concepts, although they can occur together.
No. Infinitely many optimal solutions do not automatically mean the Simplex method will encounter degeneracy. Multiple optimal solutions can occur when the objective function is parallel to a binding constraint, while degeneracy occurs when more constraints are binding than necessary at a basic feasible solution.
No, not necessarily. Multiple optimal solutions and degeneracy are different things. Degeneracy happens when a basic variable equals zero, while infinitely many optimal solutions can occur even without this condition.
Enjoying the discussion? Don't just read, join in!
Create an account today to enjoy exclusive features and engage with our awesome community!
Sign up