Skip to main content

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.