Feasibility, Optimality, and Certificates
Feasibility asks whether any point satisfies all encoded constraints. Optimality asks whether a feasible point has the best encoded objective. These are different claims, and both are conditional on the model and numerical tolerances.
Prerequisites
Complete decision variables, objectives, and constraints.
Learning goals
- Check a status before reading a candidate solution.
- Distinguish optimal, infeasible, unbounded, and interrupted outcomes.
- Use primal and dual objective values as optimality evidence for this LP.
- Treat tolerances and certificates as model evidence rather than real-world proof.
Status is part of the result
For SciPy linprog, status 0 means the algorithm reports successful termination, 2 infeasibility, 3 unboundedness, and 4 numerical difficulty. A limit or interruption is not an optimal certificate. Result members may differ when optimization is unsuccessful, so code must branch on status before using x, fun, residuals, or marginals.
Solvers apply a feasibility tolerance: tiny floating-point residuals can be accepted as zero. Compare with using declared absolute and relative tolerances appropriate to scaled units; never round a visibly infeasible solution into feasibility.
For the baseline LP, a primal feasible value of 200 and a dual feasible bound of 200 give a zero primal-dual gap within tolerance. Strong duality certifies model optimality here. It does not certify coefficient accuracy, missing constraints, causal impact, or implementability.
Worked example
The second model requires at least 15 workshop and 20 clinic batches. Those minima alone need 50 staff-hours, exceeding the hard 40-hour capacity, so the model is genuinely infeasible.
import numpy as np
from scipy.optimize import linprog
benefit = np.array([8.0, 6.0])
A = np.array([[2.0, 1.0], [1.0, 2.0]])
b = np.array([40.0, 50.0])
primal = linprog(-benefit, A_ub=A, b_ub=b,
bounds=[(0.0, None)] * 2, method="highs")
dual = linprog(b, A_ub=-A.T, b_ub=-benefit,
bounds=[(0.0, None)] * 2, method="highs")
if primal.status != 0 or dual.status != 0:
raise RuntimeError("expected feasible primal and dual")
infeasible_A = np.vstack([A, [-1.0, 0.0], [0.0, -1.0]])
infeasible_b = np.array([40.0, 50.0, -15.0, -20.0])
failed = linprog(-benefit, A_ub=infeasible_A, b_ub=infeasible_b,
bounds=[(0.0, None)] * 2, method="highs")
gap = dual.fun - (-primal.fun)
print(f"feasible_status={primal.status} primal_points={-primal.fun:.3f} dual_bound_points={dual.fun:.3f} gap={gap:.3e}")
print(f"infeasible_status={failed.status} solution_available={failed.x is not None} conflicting_minima=workshop>=15,clinic>=20")
Expected output:
feasible_status=0 primal_points=200.000 dual_bound_points=200.000 gap=0.000e+00
infeasible_status=2 solution_available=False conflicting_minima=workshop>=15,clinic>=20
An infeasibility status should trigger diagnosis: inspect bounds, units, signs, data, and policy combinations. Do not repeatedly loosen tolerances until a desired answer appears. Some solver interfaces can return an infeasibility certificate or irreducible inconsistent subsystem; this SciPy lesson verifies the contradiction directly instead of claiming that interface.
Limitations and common mistakes
- “No solution” may mean infeasible, unbounded, a limit, or numerical trouble; preserve the exact status and message.
- An unbounded model often reveals a missing bound or resource, but a real decision can also be mathematically unbounded under a poor objective.
- A small gap is meaningful only when primal and dual feasibility also hold at appropriate tolerances.
- Feasibility of aggregate resources does not establish scheduling, staffing, eligibility, or legal feasibility.
- Solver certificates concern the encoded mathematical problem, not real-world validity.
Practice
Derive the staff contradiction for the two minima without a solver. Then remove the room constraint and one variable's upper control; construct an objective direction that is unbounded and state which missing assumption caused it.
Next steps
Understand why convex structure makes local evidence globally useful in convexity and local versus global optima.
Primary sources
Checked 2026-10-18: SciPy 1.18.1, linprog statuses and result fields and the linear-programming tutorial; HiGHS, official documentation; Boyd and Vandenberghe, Convex Optimization, duality and alternatives.