Bounded infeasible and unbounded problems
Bounded Infeasible and Unbounded Problems
A linear program does not always have a normal finite optimum.
It may be feasible or infeasible, bounded or unbounded.
These words describe different issues.
Feasible vs Infeasible
A problem is feasible if at least one point satisfies all constraints.
That means:
\[S\ne \emptyset\]A problem is infeasible if no point satisfies all constraints.
That means:
\[S=\emptyset\]Example of Infeasibility
The constraints:
\[x_1\ge 5\]and:
\[x_1\le 2\]cannot both be true.
So the feasible set is empty.
The problem is infeasible.
Bounded Feasible Set
A feasible set is bounded if it does not extend infinitely far.
In two variables, a bounded feasible region is enclosed.
Example:
\[x_1+x_2\le 10\] \[x_1,x_2\ge 0\]This feasible set is bounded.
It is a triangle.
Unbounded Feasible Set
A feasible set is unbounded if it extends infinitely in at least one direction.
Example:
\[x_1-x_2\le 3\] \[x_1,x_2\ge 0\]This feasible set is unbounded because it continues forever upward.
Unbounded Objective Value
A problem has an unbounded objective value if the objective can improve forever while staying feasible.
For maximization, this means:
\[c^Tx\to +\infty\]For minimization, this means:
\[c^Tx\to -\infty\]In that case, there is no finite optimal solution.
Important Distinction
An unbounded feasible set does not automatically mean the LP is unbounded.
The feasible set may extend infinitely in a direction that does not improve the objective.
Example:
\[\min x_1\]subject to:
\[x_1\ge 0,\qquad x_2\ge 0\]The feasible set is unbounded because $x_2$ can grow forever.
But the optimal value is finite:
\[x_1^*=0\]Example of Unbounded Maximization
Consider:
\[\max x_1+x_2\]subject to:
\[x_1,x_2\ge 0\]There is no upper limit on either variable.
For:
\[x=(t,t)\]we get:
\[x_1+x_2=2t\]As $t\to\infty$, the objective goes to $+\infty$.
So the problem is unbounded.
Example of Unbounded Minimization
Consider:
\[\min -x_1\]subject to:
\[x_1\ge 0\]As $x_1\to\infty$:
\[-x_1\to -\infty\]So the problem is unbounded below.
Bounded Problem
An LP has a bounded optimal value if the objective cannot improve forever over the feasible set.
If the feasible set is nonempty and bounded, then every linear objective has a finite optimum.
If the feasible set is unbounded, the objective may or may not be unbounded.
Possible LP Outcomes
An LP may have:
| Feasible Set | Objective Behavior | Outcome |
|---|---|---|
| empty | none | infeasible |
| nonempty | finite best value | optimal solution exists |
| nonempty | improves forever | unbounded |
| nonempty | same best value on an edge/face | multiple optima |
Multiple Optima
Multiple optimal solutions occur when the objective contour line is parallel to an edge of the feasible region.
Then every point on that edge gives the same optimal value.
Example:
If the objective is:
\[\max x_1+x_2\]and the optimal edge satisfies:
\[x_1+x_2=10\]then every feasible point on that edge is optimal.
Unique Optimum
A unique optimum occurs when the best contour line touches the feasible region at exactly one vertex.
This is the most common graphical case.
Graphical Diagnosis
In two-variable LP:
- infeasible means the shaded regions do not overlap
- unbounded feasible set means the region extends forever
- unbounded objective means the contour line can move forever in the improving direction
- multiple optima means the last contour line overlaps an edge
- unique optimum means the last contour line touches one vertex
Solver Diagnosis
Solver tools usually report statuses such as:
- optimal
- infeasible
- unbounded
- infeasible or unbounded
- time limit
- numerical issue
For exams, the important statuses are:
- feasible
- infeasible
- bounded
- unbounded
- optimal
Key Takeaway
Infeasible means no allowed point exists.
Unbounded means allowed points exist, but the objective can improve forever.
Exam checkpoint
For formulation questions, show variables, objective, constraints, sign restrictions, and units. Do not solve unless the question asks for a solution.