Why can a linear program be unbounded?

What Does It Mean When a Linear Program Is Unbounded?

In mathematical terms, an LP is unbounded if there exists a direction \( d \) such that:

\[ Ad \le 0,\quad d \ge 0,\quad c^\top d > 0 \]

This means you can move infinitely far in direction \( d \) while improving the objective and never violating constraints.

Why Does Unboundedness Happen?

1. Missing or incomplete constraints

If a model forgets to include a capacity limit, demand limit, or resource restriction, the feasible region may extend infinitely.

2. Objective improves along an open direction

If the objective increases along a direction where no constraint blocks movement, the LP becomes unbounded.

3. Feasible region is open in the direction of optimization

Geometrically, the feasible region is a polyhedron with a “ray” extending infinitely in a direction that improves the objective.

4. Surplus variables without proper bounds

If constraints allow variables to grow without upper limits, the objective may grow without bound.

5. Modeling errors

Most unbounded LPs in practice come from missing constraints or incorrect inequality directions.

How to Detect Unboundedness (Step by Step)

Step 1: Examine the feasible region

If the feasible region extends infinitely in a direction that improves the objective, the LP is unbounded.

Step 2: Check constraints for missing upper bounds

Variables without upper limits can cause the objective to grow indefinitely.

Step 3: Analyze the objective direction

Determine whether the objective vector points into an unbounded region of the feasible set.

Step 4: Use simplex tableau logic

In the simplex method, unboundedness occurs when:

• the entering variable has a positive reduced cost (maximization), and
• its column has no positive entries.

This means the entering variable can increase indefinitely without violating any constraint.

Step 5: Check for rays in the feasible region

A ray is a direction in which the LP can move infinitely while remaining feasible. If the objective improves along that ray, the LP is unbounded.

Step 6: Verify model completeness

Ensure all real‑world limits (capacity, demand, budgets, etc.) are included. Missing constraints are the most common cause of unboundedness.

Numerical Example

Consider the LP:

\[ \text{Max } z = 5x_1 + 3x_2 \]

\[ \begin{aligned} x_1 – x_2 &\le 4 \\ x_1, x_2 &\ge 0 \end{aligned} \]

There is no constraint limiting \( x_1 \) from increasing. As \( x_1 \to \infty \), the objective \( z = 5x_1 + 3x_2 \to \infty \).

The LP is unbounded.