Lesson 3: Feasibility, Optimality, and Model Checking

1 Modelling context

The solver reports "Solver found a solution." That report is a statement about the LP the solver was given. It is not a statement about the problem you intended to solve. Three questions must be addressed separately:

Is the reported solution feasible? Does it satisfy all the constraints you intended?
Is the reported solution optimal? Is there any feasible solution with a better objective value?
Does the reported solution correspond to a sensible decision? Would the recommended action be acceptable to the decision-maker in the real context?

The solver addresses the second question automatically. The first and third require the analyst's judgement. This lesson develops the checks for all three.

Three separate questions

A solution can be feasible but not optimal, optimal but not what was intended, or infeasible if the LP is mis-specified. The solver reports on one of these; the analyst is responsible for the other two.

2 Learning objectives

By the end of this lesson you will be able to

Check feasibility of a reported LP solution.
Recognise infeasible and unbounded LPs and diagnose their causes.
Recognise degeneracy and multiple optima.
Verify optimality by comparing against a manual solution on a small instance.
Assess whether the optimal solution is decision-relevant.
Produce a model-checking report for an LP model.

3 Prerequisite review

Feasible solution: A set of decision variable values satisfying all constraints, including nonnegativity.
Optimal solution: A feasible solution with the best objective value. May not be unique.
Infeasible LP: A linear program for which no feasible solution exists. The feasible region is empty.
Unbounded LP: A linear program in which the objective can be made arbitrarily large (for maximization) or small (for minimization) while remaining feasible.
Binding constraint: A constraint whose left-hand side equals its right-hand side at the optimal solution. Also called active.
Slack: The difference between the right-hand side and the left-hand side of a constraint. Positive slack means the constraint is not binding.

4 Mathematical formulation

Feasibility

A solution x* = (x*₁, …, x*ₙ) is feasible if it satisfies all constraints:

a_{i1} x*₁ + … + a_{in} x*ₙ ≤ b_i  for all i
x*_j ≥ 0  for all j

Feasibility of the reported solution can be checked directly by substituting the values into the constraints. This check is independent of the solver and catches configuration errors that the solver's own feasibility test may not detect.

Infeasibility

An LP is infeasible if no feasible solution exists. The solver reports "Solver could not find a feasible solution." Common causes:

A constraint is impossible: for example, x₁ ≥ 10 and x₁ ≤ 5.
The bounds on the right-hand sides are inconsistent, so the constraints cannot all be satisfied simultaneously.
The nonnegativity restrictions conflict with a constraint: for example, x₁ + x₂ ≤ −5 with x₁, x₂ ≥ 0.

Diagnosing infeasibility usually requires examining each constraint individually and identifying which subset of constraints is inconsistent.

Unboundedness

An LP is unbounded if the objective can be made arbitrarily good while remaining feasible. The solver reports "Objective cell values do not converge." Common causes:

A missing constraint: for example, an LP that maximizes profit without any bound on production is unbounded.
A constraint with the wrong direction: an inequality entered as ≥ when it should be ≤ may allow unbounded growth.
A nonnegativity restriction omitted: variables allowed to become arbitrarily negative (or positive) without constraint.

Multiple optima and degeneracy

An LP can have:

A unique optimum. One vertex is strictly better than all others.
Multiple optima. An entire edge or face of the feasible region is optimal. The solver reports one of these points.
Degeneracy. More constraints bind at the optimal vertex than there are decision variables. This can complicate sensitivity analysis.

In practice, multiple optima are a signal that the model is not completely determining the decision. Additional criteria (secondary objectives, tie-breakers) may be needed to select among the optimal solutions.

Figure 6.4. Three LP outcomes. Unique optimum (left), multiple optima along an edge (middle), and unbounded feasible region (right).

Model checking

Beyond feasibility and optimality, an LP should be checked against the decision problem it was meant to represent. Checks include:

Do the optimal decision variables make sense in context? A recommendation to produce 10⁶ units when the market is 100 units indicates a missing constraint.
Are the binding constraints the ones you expected? If the model says labour is binding when you expected it to be abundant, either the data are wrong or the formulation is wrong.
Is the objective value plausible? An objective wildly different from the expected scale indicates a units error or a coefficient error.
Is the solution sensitive to small changes? A solution that changes dramatically under a small coefficient change is fragile. Unit 6.2 quantifies this.

5 Worked example

Checking the production planning LP solution

The LP from Lesson 1 was solved in Lesson 2, giving x_A = 40, x_B = 16.67, with objective ≈ 2100. We check the solution.

Step 1 — Check feasibility directly.

Labour:    2·40 + 1·16.67 = 96.67 ≤ 100  ✓  (slack 3.33)
Material:  1·40 + 3·16.67 = 90.0  ≤ 90   ✓  (binding)
Demand A:  40                     ≤ 40   ✓  (binding)
Demand B:  16.67                  ≤ 30   ✓  (slack 13.33)
Nonnegativity: x_A, x_B ≥ 0             ✓

All constraints are satisfied. The solution is feasible.

Step 2 — Identify the binding constraints.

Two constraints are binding: material and demand A. Labour has slack 3.33 hours; demand B has slack 13.33 units. At the optimum, the binding constraints are the ones that limit further improvement.

Step 3 — Verify optimality on a small instance.

Because the LP has only two decision variables, we can verify the optimum geometrically. The feasible region has vertices at the intersections of the constraint lines. Solving pairs:

Labour ∩ Material: 2x_A + x_B = 100, x_A + 3x_B = 90 → x_A = 42, x_B = 16. But this violates the demand A constraint, so it is infeasible.
Labour ∩ Demand A: x_A = 40, 2·40 + x_B = 100 → x_A = 40, x_B = 20. Material check: 40 + 60 = 100 > 90. Infeasible.
Material ∩ Demand A: x_A = 40, 40 + 3x_B = 90 → x_A = 40, x_B = 16.67. Labour check: 80 + 16.67 = 96.67 ≤ 100. Feasible. Objective: 40·40 + 30·16.67 = 2100.

The feasible vertices give objective values: (0,0) → 0, (40,16.67) → 2100, (40,0) → 1600, (0,30) → 900. The maximum is 2100, confirming the solver's answer.

Step 4 — Check model plausibility.

The solution is x_A = 40, x_B = 16.67. Both are within sensible ranges. Demand A is binding (produces the maximum possible of A); demand B is not binding (well below the 30-unit limit). This is plausible given product A's higher profit margin.

Step 5 — Sensitivity preview.

If the profit on A rises, will the solution change? Since x_A is already at its maximum, raising the profit encourages more A but cannot produce more. The solution would reallocate some material from B to A — a change in the binding constraints. The systematic treatment of this question is the subject of Unit 6.2.

6 Verification check

Checks to perform

Substitute the optimal values into each constraint. Confirm each LHS ≤, =, or ≥ its bound, as appropriate.
Check the units of the objective and each constraint at the optimum. The optimal values should have sensible units and magnitudes.
Verify on a small instance by enumeration. For LPs with two or three decision variables, compute the objective at each feasible vertex and confirm the maximum.
Identify binding and slack constraints. Report which constraints are binding. A solution with no binding constraints is unusual and should prompt a re-examination.
Check for infeasibility or unboundedness in the model. If the solver reports either, examine the constraints and bounds for inconsistency or missing limits.
Assess the recommendation in context. Does the optimal solution correspond to an action that makes sense? Are the units correct? Would a decision-maker accept the recommendation?

7 Interpretation

The optimal solution is a recommendation, not a fact. It is the best action according to the objective and constraints that were stated. Three interpretive points:

The recommendation depends on the model. If any coefficient, bound, or constraint is wrong, the recommendation may be wrong, even though the LP was solved correctly.
The recommendation is a starting point, not an endpoint. The decision-maker may have additional considerations not captured in the LP. The model supports the decision; it does not make it.
Binding constraints are decision-relevant. They identify the limiting factors. If a binding constraint can be relaxed (by hiring more labour, sourcing more material), the objective can improve. The marginal value of relaxing each binding constraint is the subject of Unit 6.2.

Reporting an LP solution

A complete report states: the LP formulation, the solver configuration, the optimal decision variables, the objective value, which constraints are binding, and the units of each. Then it interprets the solution in the decision context and states the model's claim-support scope.

8 Uncertainty and limitations

The LP solution is exact given the model. The uncertainty is in the model, not in the solution.

Sources of uncertainty in an LP solution
Source	Effect
Objective coefficients	The recommendation may change if coefficients change
Constraint bounds	Changing bounds changes the feasible region and the optimum
Constraint coefficients	Uncertain resource consumption per unit propagates to the solution
Model form	If the problem is not linear, the linear approximation may mislead
Rounding and precision	For LPs with integer solutions, near-integer values may indicate a required integer model

Solution fragility

An optimal solution that changes dramatically under a small change in one coefficient is fragile. Fragile solutions should be reported with the sensitivity information and, if necessary, replaced by a more robust recommendation. The sensitivity analysis of Unit 6.2 quantifies this.

9 Common implementation errors

Watch for these

Trusting the solver's feasibility report without checking. The solver checks the constraints it was given. If a constraint was mis-entered, the solver's report is against the wrong constraints.
Not identifying the binding constraints. The binding constraints are the ones that limit the objective. If they are not identified, the report is incomplete.
Ignoring the possibility of multiple optima. If the objective is parallel to a constraint edge, an entire edge may be optimal. Reporting only the solver's chosen point may conceal this.
Confusing an infeasible LP with a solver error. Infeasibility means no feasible solution exists. It is a property of the model, not a solver failure.
Confusing unboundedness with a large objective value. Unboundedness means the objective can be made arbitrarily large. It is a different condition from a large optimum.
Not checking the recommendation against the decision context. A solution to the LP that does not correspond to an implementable decision is a model error, not a solution error.
Skipping documentation of the model's claim-support scope. What assumptions underlie the LP? Under what conditions would the recommendation not apply?

10 Independent modelling task

Your turn

Use the LP from Lesson 2's task.
Verify the feasibility of the solver's solution by substituting the optimal values into each constraint.
Identify the binding and slack constraints.
If the LP has two decision variables, verify the optimum by enumerating the feasible vertices.
Assess the recommendation in context. Does it correspond to a sensible decision? Are the units and magnitudes correct?
Write a model-checking report: the LP statement, the solution, the verification of feasibility, the binding constraints, the optimality check, and a discussion of the recommendation's plausibility.
State the model's claim-support scope: under what assumptions is the recommendation valid, and what does the model not address?

This exercise completes the LP component of Laboratory 11 and Assignment 5.

11 Reflection prompt

Reflect before continuing

The solver reports "Solver found a solution" and returns specific values for the decision variables. What three questions must you ask before relying on these values?

Two or three sentences. Consider feasibility, optimality, and the correspondence to the intended decision problem.

12 Lesson summary

Key takeaways

Feasibility must be verified independently of the solver. Substituting the optimal values into each constraint catches configuration errors.
Binding constraints are decision-relevant. They identify what limits further improvement.
Optimality can be checked by enumeration on small instances. For two or three decision variables, compute the objective at each vertex.
Infeasibility and unboundedness are properties of the model, not of the solver. They require re-examination of the constraints.
Multiple optima and degeneracy complicate interpretation. Multiple optima mean the model does not fully determine the decision.
A complete LP report includes the formulation, the solution, the binding constraints, and a claim-support statement.

Unit 6.1 complete

You have formulated linear programs, implemented them in a spreadsheet, solved them, and verified the solutions. Unit 6.2 turns to the dual problem, the fundamental duality theorem, and the sensitivity analysis that makes an LP solution decision-relevant.

§ Self-quiz, practice, and homework

Practice exercises

For the production planning LP, verify that the solution x_A = 40, x_B = 16.67 is feasible by substituting into each constraint.
Identify the binding constraints at this optimum. Which would you relax to improve the objective?
For a small LP with two variables and three constraints, enumerate the feasible vertices and compute the objective at each. Confirm the optimal vertex.
Explain in two sentences why an LP with a binding constraint at x_A = 40 but no constraint on x_B might be unbounded.

Homework problems

Model-checking report. Take the LP from Lesson 2's homework. Produce a model-checking report that includes: the LP statement, the solver's solution, verification of feasibility against each constraint, identification of binding constraints, and a verification of optimality by enumeration (if two variables) or by comparison against the solver's tolerance report. Write 500–700 words.
Infeasibility and unboundedness experiments. Starting from a feasible LP, deliberately introduce (a) an inconsistent pair of constraints that makes the LP infeasible, and (b) a missing upper bound that makes the LP unbounded. For each case, document the solver's report, verify the diagnosis by examining the constraints, and correct the model.
Claim-support scope. For your LP model, write a claim-support statement: under what assumptions is the recommendation valid, what range of coefficient values is it valid for (if you can determine this), and what does the model not address?

Mini project

Produce a complete model-checking report for an LP of your choice. The report should include the formulation, the solver configuration, the solution, verification of feasibility and optimality, identification of binding constraints, interpretation in the decision context, and a claim-support statement. Submit the spreadsheet and the report. This completes Laboratory 11.