Solver Statuses, Gaps, and Time Limits
A solver result is a structured evidence record, not just a vector of decision values. Status, incumbent, bound, gap, limit, tolerances, and model version belong together.
Prerequisites
Complete heuristics and metaheuristics and review feasibility, optimality, and certificates.
Learning goals
- Distinguish a feasible incumbent from a dual bound.
- Interpret absolute and relative gaps with the objective's direction and units.
- Handle optimal, infeasible, unbounded, and limit statuses explicitly.
- Avoid reading a missing incumbent or bound as zero.
What the gap says
For a minimization MIP, a feasible incumbent is an upper bound on the optimal model objective, while a valid dual bound is a lower bound. HiGHS uses their difference to measure search progress. A relative gap normalizes that difference, but conventions near a zero objective vary; record the solver's definition.
A zero gap can certify optimality within numerical tolerances for the encoded model. It says nothing about wrong coefficients, omitted constraints, uncertain inputs, or operational validity. If a time limit fires, distinguish:
- a feasible incumbent plus a nonzero gap: usable candidate with bounded model suboptimality;
- no incumbent but a valid bound: no deployable decision yet;
- neither: no quality statement beyond termination metadata.
Never report a time-limited feasible status as optimal. Likewise, infeasible means the declared mathematical model was proven infeasible under tolerances; diagnose data and formulation before concluding the real operation is impossible.
Worked example
import numpy as np
from scipy.optimize import Bounds, LinearConstraint, milp
optimal = milp(
[-1.0], integrality=[1], bounds=Bounds([0.0], [10.0]),
constraints=LinearConstraint([[1.0]], [0.0], [3.0]),
options={"mip_rel_gap": 0.0},
)
infeasible = milp([1.0], integrality=[1], bounds=Bounds([2.0], [1.0]))
n = 100
limited = milp(
-np.arange(1, n + 1, dtype=float),
integrality=np.ones(n),
bounds=Bounds(np.zeros(n), np.ones(n)),
constraints=LinearConstraint([np.arange(1, n + 1, dtype=float)], [-np.inf], [1000]),
options={"time_limit": 0.0, "presolve": False},
)
print(f"optimal status={optimal.status} incumbent={-optimal.fun:.0f} gap={optimal.mip_gap:.1f} claim=optimal_for_model")
print(f"infeasible status={infeasible.status} solution_available={infeasible.x is not None}")
gap = "unavailable" if getattr(limited, "mip_gap", None) is None else limited.mip_gap
print(f"time_limited status={limited.status} solution_available={limited.x is not None} gap={gap} claim=none")
Expected output:
optimal status=0 incumbent=3 gap=0.0 claim=optimal_for_model
infeasible status=2 solution_available=False
time_limited status=1 solution_available=False gap=unavailable claim=none
The zero-second run is intentionally deterministic and has no incumbent. Production limits should be meaningful budgets, and any returned incumbent must be validated before use.
Limitations and common mistakes
- Status integers are library-specific; persist the message and version as well as the number.
- A relative gap is not an error bar, confidence interval, or model-risk estimate.
- Floating-point feasibility is tolerance-based. Recompute material residuals in business units.
- Changing presolve, threads, randomization, or hardware can change a limited run's incumbent even when the model is unchanged.
Practice
Construct a larger knapsack model, stop it at a fixed node limit, and record whether an incumbent and dual bound exist. Explain the strongest claim each field supports.
Next steps
Turn solver output into independent behavioral checks in validating optimization models.
Primary sources
Checked 2026-10-19: SciPy 1.18.1, milp statuses, time_limit, and mip_rel_gap; HiGHS, MIP terminology and option definitions; Google OR-Tools, CP-SAT status meanings.