The Four Terminal Outcomes

A linear program ends in one of exactly four states. Naming which one, and citing what settles it, is a competence separate from any method for finding an optimum.

The four outcomes are infeasible, unbounded, a unique optimum, and infinitely many optima. You have met all four already, scattered: the feasible region unit noted that a region can be empty or unbounded, the graphical unit showed a contour coming to rest on a corner or along an edge, and the simplex unit observed that an iteration can fail to find a leaving variable.

What has not happened yet is the decision. Recognising a case when you are told which case to look for is a different skill from being handed a program and asked which of the four holds. That decision is this unit's subject, and it is why the cases are taught together rather than one at a time.

This unit assumes you can classify a feasible region and slide an objective contour.

Push the objective contour across the region and watch how the motion ends. There are exactly four endings.

There may be no region to push across. The constraints contradict each other and their intersection is empty, so nothing is shaded and nothing can be touched. Notice what you did not need in order to see this: the objective never entered the argument.

The region may run on forever in the direction you are pushing, so the contour never loses contact. There is no final position and no finite best value. The detail that matters is the phrase in the direction you are pushing. A region that runs on forever in some other direction ends the motion perfectly normally.

The contour may come to rest touching one corner. Push any further and contact is lost entirely. That corner is the answer, and it is the only one.

Or the contour may come to rest lying flat along a whole edge, because it happens to be parallel to the constraint that stopped it. Then every point of that edge is equally good and the program has infinitely many answers.

The reason to hold all four at once is that the work is discrimination. Each case is easy to verify once named; naming the right one from a cold start is the competence, and it decomposes into a short sequence of cheap questions asked in a deliberate order.

For $max\{c^{\mathsf{T}}x:x\in F\}$ with $F$ the feasible region, exactly one of the following holds.

Infeasible. $F=\mathrm{\varnothing }$: no point satisfies every constraint. Decided by the constraints alone.

Unbounded. $F\ne \mathrm{\varnothing }$ and there is a direction $d$ in which $F$ continues without limit, with . Both parts are needed: the region must admit the direction, and the objective must improve along it.

Unique optimum. The optimal value $z^{\ast }$ is finite and attained at exactly one point, which is necessarily an extreme point of $F$.

Multiple optima. $z^{\ast }$ is finite and attained at more than one point. The optimal set $\{x\in F:c^{\mathsf{T}}x=z^{\ast }\}$ is then a face of $F$ of dimension at least one, an edge, or a larger flat, and every one of its points is optimal.

The four are mutually exclusive and, for a linear program, exhaustive. A linear program that is neither infeasible nor unbounded attains its optimum; there is no fourth possibility in which the value is finite but never reached. That guarantee is specific to linear programs over polyhedra and does not extend to optimisation in general.

Decide feasibility first, using only the constraints. Ask whether any point satisfies all of them together. Do not involve the objective: it cannot make an empty region nonempty, and consulting it here is the most common way the order of work goes wrong. If the region is empty, the program is infeasible and you are finished.

Look for a direction in which the region continues without limit. If the region is bounded, no such direction exists, the program cannot be unbounded, and a finite optimum is guaranteed. If unbounded directions exist, identify them before bringing in the objective.

Test the objective along those directions only. For each direction $d$ in which the region continues, compute $c^{\mathsf{T}}d$. If any is positive for a maximisation, the program is unbounded and you are finished. If all are zero or negative, the region's unboundedness does not produce an unbounded program, and a finite optimum exists.

Locate the optimum. With a finite optimum established, find the point or points attaining it. The last position of the contour, or the basis at which no reduced cost improves.

Decide uniqueness by parallelism, not by arithmetic. Ask whether the objective is parallel to the constraint that stopped it. Equivalently, in the algebra, whether a nonbasic variable has reduced cost exactly zero at the optimal basis. If so, an entire face is optimal and the answer is a set; otherwise the optimum is the single point found.

Report the outcome, not just a number. Say which case holds. For multiple optima, describe the set rather than picking one member of it silently.

Take the region

which is nonempty and unbounded. It contains $(0,t)$ for every $t\ge 0$. Holding it fixed, change only the objective.

Maximise $x_2$. The direction $d=(0,1)$ keeps you in $F$ forever and . The program is unbounded.

Minimise $x_1+x_2$. The objective is nonnegative on $F$ and equals $0$ at the feasible point $(0,0)$. The optimum is $0$, attained once. Unique optimum, on an unbounded region.

Maximise $x_2-x_1$. Along $(0,1)$ the objective improves without limit, so this is unbounded again, but now consider instead minimising $x_2-x_1$ subject to the same constraints plus $x_1\le 3$. The constraint $x_1-x_2\le 1$ is parallel to the objective $x_2-x_1$, so the objective is constant along that boundary and every point of it attains the minimum $-1$. Multiple optima.

And for the fourth case, add $x_1\ge 5$ to the original constraints alongside $x_1\le 3$. No point satisfies both, so $F$ becomes empty: infeasible, regardless of which objective is attached.

The region was doing very little of the work. Three of these four verdicts turned on the objective.

Problem. Classify the outcome of

Goal. Name the outcome and the evidence that decides it.

Relevant principle. Work the checks in order, feasibility, then unboundedness, then uniqueness, so that each is answered with the least information required.

Step 1: feasibility, constraints only. The origin $(0,0)$ satisfies $0\le 8$, $0\le 6$, and both sign restrictions. A feasible point exists, so the program is not infeasible. The objective was not consulted.

Step 2: unbounded directions. Ask where the region continues without limit. Increasing $x_2$ alone is blocked by $x_1+2x_2\le 8$; increasing $x_1$ alone is blocked by $x_1\le 6$. With both variables bounded above and below, the region is bounded, so no unbounded direction exists and a finite optimum is guaranteed.

Step 3: locate the optimum. The corners are $(0,0)$, $(6,0)$, $(6,1)$ and $(0,4)$. Objective values: $0$, $12$, $16$, $16$.

Step 4: uniqueness. Two corners tie at $16$, which is a symptom. The cause is parallelism: the objective $2x_1+4x_2$ is exactly twice the constraint left-hand side $x_1+2x_2$, so the objective is constant along that boundary. The contour comes to rest lying flat along the edge from $(6,1)$ to $(0,4)$.

Answer. Multiple optima, optimal value $16$, attained at every point of that edge:

Check. Take the midpoint $(3,2.5)$: it satisfies $3+5=8\le 8$ and $3\le 6$, and gives $6+10=16$. Optimal, as claimed.

What decided it. Not the tie in the arithmetic, that was the clue. The proportionality between objective and constraint coefficients is the reason, and it would have been visible before computing a single corner.

Not infeasible: constraints that only look contradictory. $x_1+x_2\ge 10$ with $x_1\le 2$ and $x_2\le 2$ is genuinely infeasible, since . But $x_1+x_2\ge 10$ with $x_1\le 2$ alone is perfectly feasible, take $(2,8)$. Pairwise inspection is not a feasibility test; the constraints have to be considered together.

Not unbounded: an unbounded region with a finite optimum. Minimising $x_1+x_2$ over $x_1-x_2\le 1$, $x_1,x_2\ge 0$ has optimal value $0$ at the origin, though the region runs on forever. The feasible-region unit works this case through in full; the point to carry here is that the region's unboundedness never entered the verdict.

Not multiple optima: two corners with close values. Corners valued $15.98$ and $16.01$ are not a tie, and no amount of rounding makes them one. Multiple optima require exact equality along a face, which comes from parallelism between the objective and a binding constraint.

Not a unique optimum: a single corner reported from a degenerate basis. A solver may return one point while a whole edge is optimal, because it stopped at the first optimal basis it reached. The report says what the algorithm found, not how large the optimal set is; a zero reduced cost on a nonbasic variable is the signal to look further.

The fastest way to get these classifications wrong is to decide them from the shape of the feasible region. The region is settled by the constraints; three of the four outcomes also depend on the objective.

Bounded region does not mean unique optimum. The worked example above has a bounded region, a quadrilateral, and infinitely many optima. Boundedness guarantees that a finite optimum exists and is attained. It says nothing about how many points attain it.

Unbounded region does not mean unbounded program. This is the reverse error and it is thoroughly worked through in the feasible-region unit, which shows one fixed unbounded region yielding a finite optimum under one objective and no finite optimum under another. Treat that result as settled here and carry the consequence: an unbounded region is a necessary condition for an unbounded program, never a sufficient one.

Empty region does mean infeasible, and this is the case that is a property of the region alone. Infeasibility is decided by the constraints alone, which is exactly why it is checked first and why bringing the objective into that check is wasted work at best.

So the useful summary is a division of labour. The constraints decide feasibility outright. The constraints decide which directions are available. The objective decides what happens along those directions, and whether the optimum is one point or many. A learner who classifies regions fluently and then reads outcomes off them will be right about infeasibility and unreliable about everything else.

1. Classify $max3x_1+x_2$ subject to $x_1-x_2\le 2$, $x_1\ge 0$, $x_2\ge 0$. Name the evidence that decides it.

2. The same constraints, now minimising $3x_1+x_2$. Which outcome, and what changed?

3. A colleague says a program must have a unique optimum because its feasible region is a bounded pentagon. Give a counterexample with a bounded region and infinitely many optima.

4. A simplex iteration selects an entering variable and finds that every component of its direction is zero or negative, so no ratio limits the step. Which outcome has been detected, and how would the same outcome have looked on a two-variable plot?

5. Without computing any corner, predict the outcome of $max4x_1+6x_2$ subject to $2x_1+3x_2\le 12$, $x_1\le 5$, $x_1,x_2\ge 0$, and say what in the coefficients told you.

Four outcomes, mutually exclusive and exhaustive for a linear program: infeasible, unbounded, unique optimum, multiple optima.

Check them in order, because the order makes each check cheap. Feasibility first, from the constraints alone. Then whether the region continues without limit in any direction. Then the objective's behaviour along those directions only. Then, with a finite optimum secured, whether the objective is parallel to the constraint that stopped it.

Two separations do most of the work. The region is decided by the constraints; the outcome usually also needs the objective. And multiple optima come from parallelism, not from two numbers turning out close.

The same four cases return in the algebra with different signatures, no feasible basis, an entering column with no positive component, a zero reduced cost on a nonbasic variable at optimality, and again in a solver's status line. They are the same four facts about the same program, which is why the competence is recognising them rather than memorising any one representation's symptoms.