Infeasible Linear Program¶

Definition¶

An infeasible linear program has no decision vector satisfying all its constraints. Equivalently, its feasible region is empty. In the two-phase method, a negative optimal value of $\displaystyle r=-\sum_iR_i$ proves infeasibility.

Interpretation¶

An LP is infeasible when its constraints cannot all hold at once, so the feasible region is the empty set. Conflicting requirements can make a model impossible even when each requirement is sensible on its own, and no choice of objective can resolve the conflict.

Two shaded regions, below the line x1 + x2 = 40 and above the line x1 + x2 = 60, that do not overlap, so no point satisfies both constraints.

The blue triangle contains the points with $x_1+x_2\le40$ and the red region those with $x_1+x_2\ge60$ $60$ . No point can have $x_1+x_2$ at most 40 and at least 60, so the two regions do not meet.

Infeasibility is a property of the constraints alone. To prove it, combine constraints into a contradiction, as in the Examples, where $2x_1+x_2\le2$ and nonnegativity force $3x_1+4x_2\le8$ $8$ , which contradicts $3x_1+4x_2\ge12$ $12$ . In the simplex method it shows up in Phase I of the two-phase method: the artificial variables cannot all be driven to zero.

Do not confuse an infeasible LP with an unbounded one. Both have no optimal solution, but an unbounded LP has feasible points whose objective values grow without limit, while an infeasible LP has no feasible point at all. In an applied model, infeasibility often points to a requirement that is too strict or to a constraint entered with the wrong direction.

Key Results¶

An infeasible model has no optimal feasible solution.
A positive remaining artificial variable at the Phase I optimum indicates an unsatisfied original requirement.
Infeasibility differs from an unbounded objective, which requires feasible points.

Examples¶

$2x_1+x_2\le2$ $2$ , $3x_1+4x_2\ge12$ $12$ , $x_1,x_2\ge0$ is infeasible: the first constraint implies $3x_1+4x_2\le8$ $8$ .
A negative phase-I optimum, such as $r^*=-4$ $- 4$ , cannot be repaired by beginning Phase II.

Prerequisites¶

Unbounded Linear Program

Sources¶

OR Modelling · Week 2

Aliases: infeasible LP Symbols: sum

Last updated: 20 October 2026 03:02