Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 38 ยท Simplex Method

Unbounded and Infeasible LPs

Learn what unbounded and infeasible LPs mean, how simplex detects them, how to extract a ray, and how to find conflicting constraints with an elastic relaxation.

Not every LP has an optimal solution. A model can be infeasible (no point satisfies all constraints) or unbounded (the objective can be improved forever). In practice these outcomes are bugs in the model far more often than genuine facts about the world, so you need to recognise them, understand how a solver detects them, and know how to track down the cause.

The three possible outcomes

Every LP falls into exactly one of three classes:

Outcome Feasible region Meaning in a real model
Optimal Non-empty, objective bounded in the improving direction Normal result
Infeasible Empty Requirements contradict each other (or data error)
Unbounded Non-empty and extends infinitely in an improving direction A limit is missing (a capacity, a demand cap, a bound)

There is no fourth outcome. In particular, a non-empty feasible region that is unbounded can still have a finite optimum if the objective does not improve along the open directions.

Unboundedness in the simplex method

During the ratio test, simplex looks for rows with a positive entry in the entering column. If the entering column has no positive entries, increasing the entering variable never makes any basic variable hit zero, so you can increase it forever, while the objective improves (it had a negative reduced cost). That is exactly an extreme ray: a direction d along which you can move without ever leaving the feasible region, and along which the objective keeps improving.

You can even write down the ray. If variable k enters, set d_k = 1, set each basic variable d_(B_i) = -T[i, k] (the negative of its column entry), and leave everything else at zero. Then x + t d is feasible for all t >= 0.

Python Detect unboundedness and extract the ray

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The objective grows without bound along t. A modeller should ask: which real-world limit have I forgotten? Typical culprits are a missing capacity constraint, a missing demand cap, or a sign error in the objective (maximizing a cost).

Infeasibility

An infeasible LP has no point satisfying all constraints. Simple examples: x + y <= 2 together with x + y >= 5, or a requirement x >= 10 when a capacity says x <= 8. In big models the conflict is spread over many rows and hard to spot.

How does simplex notice? With only <= constraints and b >= 0 the origin is feasible, so infeasibility cannot occur. Models with >= or = rows need a Phase 1: first find any feasible vertex by minimizing artificial variables. If the minimum is positive, the problem is infeasible. The full procedure is the subject of two-phase simplex and Big-M.

Diagnosing an infeasible model: elastic relaxation

When a solver says "infeasible" it rarely says why. A practical technique is to relax every constraint with a non-negative violation variable and minimize the total violation. Because that relaxed model is always feasible, you can solve it and read which constraints had to be violated, and by how much.

For a constraint a . x <= b, relax it to a . x - v <= b with v >= 0; for a . x >= b use a . x + v >= b. Minimize sum v.

Python Find which constraints conflict

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The wood limit cannot supply the committed 40 chairs and 20 tables (they need 2*40 + 4*20 = 160 units of wood but only 100 exist). The relaxation reports the cheapest repair: after building 40 chairs only 20 units of wood remain, enough for 5 tables, so the tables commitment is short by 15. It tells you which requirements must give, and by how much, which is a quick way to negotiate commitments or buy capacity. Solvers such as Gurobi offer this as "IIS" (irreducible infeasible subsystem) computation; the elastic method is the same idea in spirit. (Which constraint is flagged can vary between equally good relaxations, so treat the result as a clue, not a verdict.)

When a model is infeasible, check the data before the logic: wrong units, a requirement entered with the wrong sign, a bound lb > ub, or >= and <= swapped are the usual causes.

Telling the two apart in linprog

res.status is 2 for infeasible and 3 for unbounded. A subtle point: if you suspect unboundedness but linprog reports infeasible (or the reverse), test with a zero objective. With c = 0 an unbounded model becomes a plain feasibility problem, so "optimal" means "the region is non-empty".

Python Separate infeasible from unbounded

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The same region can be unbounded for one objective and perfectly fine for another, because unboundedness is a property of the pair (region, objective).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In simplex, how is unboundedness detected?

    Without a positive entry no basic variable blocks the entering variable, so it can grow forever.
  2. 2. A model returns 'unbounded'. What is the most likely cause?

    Real resources are finite; an unbounded model usually omitted a constraint.
  3. 3. What does an elastic relaxation minimize?

    Violation variables make the model feasible; minimizing them shows which constraints must be broken.
  4. 4. True or false: the same feasible region may be unbounded for one objective and have a finite optimum for another.

    Unboundedness depends on whether the objective improves along an unbounded direction of the region.

Summary

  • Every LP is optimal, infeasible or unbounded.
  • Simplex detects unboundedness when the entering column has no positive entries and yields an improving ray.
  • Infeasibility is detected by Phase 1 (next lesson); diagnose it with an elastic relaxation.
  • Both outcomes usually point to modelling or data errors.
  • Use a zero objective to test whether the region is empty.

Next: Two-Phase Simplex and Big-M