Multiple Optimal Solutions in LP: How to Detect Alternate Optima (Zero Reduced Cost) + What to Do Next
In linear programming (LP), it’s common to have more than one optimal solution. This usually means your objective is “flat” along a binding edge (or face) of the feasible region. This guide shows how to recognize it (graphically and algebraically), how simplex signals it (zero reduced cost), and how to choose a final solution that fits your decision needs.
You can confirm every example below using the Linear Programming calculator. If you’re new to the basics (feasible region, corner points), start with Linear Programming (LP) — Beginner Guide and Graphical Method for LP (2 Variables).
On this page
- Quick takeaway (what multiple optima means)
- Geometric reason: objective parallel to a binding edge/face
- Simplex signal: zero reduced cost at optimum
- What to do next (choose a solution you actually want)
- Questions people ask (PAA)
- Worked examples (fully solved)
- Check your answer (calculator + Excel/Python)
- Troubleshooting table (symptom → cause → fix)
- Glossary
Quick takeaway: An LP has multiple optimal solutions when there is a whole line segment (or face) of feasible points that all produce the same best objective value. Geometrically, the objective’s level lines are parallel to a binding edge. In simplex terms, at an optimal tableau at least one nonbasic variable has zero reduced cost, meaning you can pivot to a different optimal basic solution without changing the objective. If you also see “infeasible” or “unbounded,” that’s a different issue—see Unbounded vs Infeasible LP (Fix Checklist).
Geometric reason: objective parallel to a binding edge/face
Beginner → intermediate
Why a “flat” optimum happens
In 2 variables, the objective z = c1x1 + c2x2 has straight-line level sets. If the optimal level set
overlaps a boundary edge of the feasible region, every point on that overlap gives the same objective value.
This is the common case: you solve, get a corner solution, but the objective is equally good at neighboring points along the same edge. The Graphical Method for LP (2 Variables) makes this easy to see.
Simplex signal: zero reduced cost at optimum
Intermediate (solver-aligned)
Zero reduced cost means “another optimum exists”
In simplex, each nonbasic variable has a reduced cost (often written Cj − Zj or similar, depending on convention).
At an optimal solution, reduced costs must satisfy an optimality sign condition.
If a nonbasic variable also has reduced cost = 0, then increasing it from zero does not change the objective locally.
That is the algebraic signal for alternate optima.
What to do next (choose a solution you actually want)
Decision guidance
Multiple optima isn’t an error—it’s a choice you must make
If you have multiple optimal solutions, the “best” one depends on business preferences not represented in the objective. Common tie-break approaches:
- Add a secondary objective (lexicographic optimization): optimize your main objective, then optimize a second criterion over the optimal face.
- Add a small preference penalty (e.g., minimize total variation, minimize one variable, etc.) to select a unique point.
- Select an extreme point on purpose (for interpretability), or select a more “balanced” point for operational stability.
If you’re implementing this in tools, see Linear Programming in Excel Solver or Linear Programming in Python (PuLP/OR Tools).
Questions people ask about multiple optimal solutions in linear programming (PAA)
People ask
What does multiple optimal solutions mean in linear programming?
It means there is more than one feasible solution that achieves the same best objective value. Typically there is an entire line segment (in 2D) or a face (in higher dimensions) of optimal points.
People ask
How do you know if an LP has multiple optimal solutions?
Graphically (2 variables), the objective line is parallel to a binding edge at the optimum. In simplex output, an optimal tableau with a nonbasic variable having zero reduced cost indicates alternate optima.
People ask
Are multiple optimal solutions bad?
Not necessarily. It means your current objective does not uniquely rank solutions on the optimal face. It can be an opportunity: you can choose an optimal solution that also satisfies a secondary preference (stability, fairness, simplicity).
People ask
Can an LP have infinitely many optimal solutions?
Yes. That is the common case for “multiple optima”: an entire line segment (or higher-dimensional face) is optimal. The worked examples below show exactly how that happens.
People ask
How do you find all optimal solutions in a linear program?
In 2D, you can describe the optimal edge as a line segment between two optimal corner points. In simplex, you can pivot along zero reduced-cost variables to generate alternate optimal bases, then describe the set using the binding constraints.
People ask
How do you choose one solution when there are multiple optimal solutions?
Add a secondary objective (lexicographic), add a tiny tie-break penalty, or impose an extra business constraint. If adding a constraint causes infeasibility, use Unbounded vs Infeasible LP to debug.
Worked examples (fully solved)
Worked examples
Expand only the example you need
Each example below is collapsible (collapsed by default) to keep the page scannable while remaining fully indexable. You can verify them in the LP calculator.
Example 1 — Multiple optimal solutions in LP (maximize; optimal edge segment)
LP (maximize):
maximize z = x1 + x2
subject to x1 + x2 ≤ 4
x1 ≤ 3
x2 ≤ 3
x1, x2 ≥ 0
Step 1: Find the maximum possible value of z
Because x1 + x2 ≤ 4, we immediately get:
z = x1 + x2 ≤ 4
So the best possible objective value is at most 4.
Step 2: Check if z = 4 is achievable under all constraints
To achieve z = 4, we need:
x1 + x2 = 4
Now also enforce x1 ≤ 3 and x2 ≤ 3.
Along the line x2 = 4 − x1:
x1 ≤ 3 ⇒ x1 ∈ [0,3] x2 ≤ 3 ⇒ 4 − x1 ≤ 3 ⇒ x1 ≥ 1
Combine with nonnegativity: x1 ∈ [1,3] and x2 = 4 − x1 automatically gives x2 ∈ [1,3].
Step 3: Describe all optimal solutions
Every point on the segment:
(x1, x2) = (t, 4 − t) for 1 ≤ t ≤ 3
is feasible and yields:
z = x1 + x2 = t + (4 − t) = 4
Optimal value: z* = 4.
Multiple optimal solutions: infinitely many points on the line segment from (1,3) to (3,1).
x1 + x2 = constant is parallel to the binding constraint x1 + x2 ≤ 4 at optimum.
See Graphical Method for LP (2 Variables) if you want to visualize it.
Example 2 — Multiple optimal solutions in LP (minimize; equality boundary creates an optimal face)
LP (minimize):
minimize z = x1 + x2
subject to x1 + x2 ≥ 4
x1, x2 ≥ 0
Step 1: Lower bound the objective
Since every feasible point satisfies x1 + x2 ≥ 4, we have:
z = x1 + x2 ≥ 4
So the smallest possible objective value is at least 4.
Step 2: Show the bound is achievable
Choose any nonnegative pair with sum exactly 4, for example (4,0) or (1,3).
These satisfy the constraint and give z = 4.
Step 3: Describe all optimal solutions
The set of optimal solutions is:
(x1, x2) = (t, 4 − t) for 0 ≤ t ≤ 4
which is the full line segment from (0,4) to (4,0).
Optimal value: z* = 4.
Multiple optimal solutions: every feasible point with x1 + x2 = 4.
Example 3 — Simplex interpretation (alternate optimum via zero reduced cost)
We’ll use the same LP idea but show the simplex-style “signal” for alternate optima: an optimal solution with a nonbasic variable of zero reduced cost.
LP (maximize):
maximize z = x1 + x2
subject to x1 + x2 ≤ 4
x1 ≤ 3
x2 ≤ 3
x1, x2 ≥ 0
Step 1: Write in standard form (slacks)
x1 + x2 + s1 = 4
x1 + s2 = 3
x2 + s3 = 3
x1, x2, s1, s2, s3 ≥ 0
Step 2: Pick one optimal basic feasible solution (a corner)
From Example 1, any point with x1 + x2 = 4 and 1 ≤ x1 ≤ 3 is optimal.
Choose the corner (x1,x2) = (3,1).
Compute slacks:
s1 = 4 − (3 + 1) = 0 s2 = 3 − 3 = 0 s3 = 3 − 1 = 2
So one optimal BFS is:
(x1, x2, s1, s2, s3) = (3, 1, 0, 0, 2) with z = 4
Step 3: Show the “flat direction” that keeps z constant
Consider moving along the line x1 + x2 = 4. Let:
x1 = 3 − t x2 = 1 + t
Then:
z = x1 + x2 = (3 − t) + (1 + t) = 4 (constant)
Step 4: Check feasibility limits for t
Enforce bounds x1 ≥ 0, x2 ≥ 0, x1 ≤ 3, x2 ≤ 3:
x1 = 3 − t ≥ 0 ⇒ t ≤ 3 x2 = 1 + t ≤ 3 ⇒ t ≤ 2 x2 = 1 + t ≥ 0 ⇒ t ≥ −1 (not binding here) x1 ≤ 3 holds automatically for t ≥ 0
Therefore, for 0 ≤ t ≤ 2, every point is feasible and keeps z = 4.
This proves there are alternate optima beyond the corner.
Simplex takeaway: the existence of a feasible “move” that keeps the objective unchanged corresponds to a zero reduced cost direction at optimum (alternate optimal basis exists). In practice, solvers often report “multiple optimal solutions” or allow you to retrieve alternate optima by pivoting/adding a tie-break objective.
Check your answer (calculator + Excel/Python)
Tooling
Verify objective value, then decide your tie-break rule
Enter any example into the Linear Programming calculator. You should see the same optimal objective value at different feasible points (or you may see a solver report that alternate optima exist).
If you need a specific optimal solution (e.g., maximize x1 among all optimal points), implement a secondary objective in
Excel Solver or Python (PuLP/OR Tools).
Troubleshooting table (symptom → cause → fix)
Troubleshooting
When “multiple optima” surprises you
| What you observe | Likely cause | What to do next |
|---|---|---|
| Solver reports multiple/alternate optimal solutions | Objective is flat along a binding edge/face | Add a secondary objective or pick a preferred extreme point |
| You expected a unique answer but got a “range” of answers | Your objective doesn’t encode a tie-break preference | Encode preferences (stability, fairness, simplicity) as a second-stage objective |
| Changing the objective slightly changes the chosen solution a lot | Optimal face is large; small changes select different points | Consider robust/tie-break objectives (e.g., minimize variability) |
| Solver returns infeasible or unbounded instead | This is not an alternate-optimum case | Use Unbounded vs Infeasible LP (Fix Checklist) and add bounds |
| Hard to set up simplex by hand due to ≥ or = constraints | Need artificials for a starting basis | Use two-phase simplex or Big‑M |
Glossary
Glossary
- Multiple optimal solutions (alternate optima): more than one feasible solution achieves the same best objective value.
- Optimal face: set of points (edge/face) where the objective is maximized/minimized.
- Binding constraint: a constraint satisfied with equality at the solution (often shapes the optimal face).
- Reduced cost: simplex quantity indicating how the objective changes if a nonbasic variable increases from 0.
- Zero reduced cost (at optimum): indicates there is an alternate optimal basis/solution.
- Lexicographic optimization: optimize a primary objective first, then optimize a secondary objective over the primary-optimal set.
Disclaimer
This article and the associated calculators are provided for educational and informational purposes only. Optimization outcomes depend on modeling assumptions and input data and may not reflect real-world constraints unless you encode them correctly. This is not legal, financial, operational, or safety advice. For high-stakes decisions, validate results against domain requirements and consult a qualified professional. For details, read our full disclaimer.