Provable optimality means a solver such as Gurobi has established that no other solution feasible for the model can improve its objective beyond the specified tolerances. This proof is about the modeled objective, constraints, data, and solver settings, not a guarantee that the plan is safe, correct in the real world, compliant with an unmodeled rule, or free of risk. This is inherent to all modeling - as George E.P. Box said "all models are wrong, but some are useful".
Provable optimality via deterministic software such as a solver is especially useful when decisions must withstand review. It replaces “the algorithm picked this” with a bounded, inspectable claim, again subject to the requirement that you have modeled the problem with the necessary accuracy to make the claims you need to make.
Want to test what Gurobi can establish for your model? Speak with a Gurobi expert.
What provable optimality actually means
In the most common real-world optimization model type (a mixed-integer program, or MIP), two quantities allow us to prove optimality. The "incumbent" is the best feasible solution found so far. The "bound" comes from what is called a relaxation. Together, the branch-and-bound search limits how good any still-undiscovered solution could be.
For a minimization problem, the incumbent is an upper bound on the unknown optimum and the best bound is a lower bound. For maximization, the directions reverse. Subject to numerical tolerances (that is, tolerances that are core to how computers do arithmetic), the modeled optimum lies between them.
Suppose a minimization model has an incumbent cost of 1,000 and a best bound of 990. The solver has found a modeled-feasible plan costing 1,000 and established that no modeled-feasible plan can cost less than 990. The remaining absolute gap is 10, and the relative gap is therefore 1% under Gurobi's standard MIP-gap definition:
|incumbent − best bound| / |incumbent|
The MIPGap parameter allows users to set the stopping rule precisely. Its default value is 1e-4, or 0.01%, while MIPGapAbs provides an absolute stopping rule. This absolute gap can be more meaningful when the objective is near zero or when a difference in business units, such as dollars, minutes, or megawatt-hours, is easier to interpret.
When the achieved gap meets the configured criterion, Gurobi returns the status of OPTIMAL. As noted in the status-code documentation, this status means optimal “subject to tolerances.” It does not necessarily mean exact equality in real arithmetic (because computers do not do math in real arithmetic).
Stopping early is also completely normal. If a time or work limit is reached after a feasible incumbent and a valid bound are available, the result is the best plan found plus a quantified limit on how much its modeled objective might improve. Record the early-termination status as well as the incumbent, bound, and gap. This solution is not provably optimal, but it's quite close (and could in fact actually be the optimal, just not proven yet because the bound has not fallen), and can be good enough for many business uses.
A standalone heuristic can also be reproducible and well logged, but it generally does not supply a globally valid objective bound. It can return a plausible plan without quantifying how far that plan may be from the best modeled outcome. The bound—not the mere existence of a log—is the crucial difference.
What provable optimality does not establish
Provable optimality does not validate the model as 100% accurate. Software can never do this for you, because the model is an arbitrary representation of reality that you must define at the level of fidelity necessary to make the decisions you need to make. Gurobi's own Decision Optimization FAQ scopes the claim correctly: the result is optimal for the modeled objective, given the data, constraints, and solver tolerances.
A missing constraint can therefore produce a provably optimal plan that breaks a rule nobody encoded. Stale demand, travel-time, capacity, or availability data can produce a plan that is optimal for yesterday's conditions. A poorly chosen objective can optimize the wrong proxy with complete mathematical consistency.
One deterministic solve also doesn't resolve uncertainty. Scenario analysis, sensitivity analysis, or robust and stochastic formulations can test how a decision performs across plausible futures, but none turns an uncertain future into a guaranteed outcome. Multiple solutions can also share the same optimal objective value, so optimality does not necessarily identify one unique plan.
Numerics matter too. Gurobi uses finite-precision arithmetic and treats sufficiently small violations according to feasibility, integrality, and optimality tolerances. Our guidance on tolerances and ill conditioning recommends checking final violations and states that, for MIP models, there is no simple independent method to verify that a returned solution is truly optimal in exact arithmetic.
Nonconvex models require one more question
Ask which algorithm and formulation were solved. For supported nonlinear constraints, Gurobi's global method uses spatial branch-and-bound with globally valid primal and dual bounds, refining the search until it reaches the requested gap. The nonlinear-constraint documentation describes that global process.
Gurobi 13.0 and beyond also includes a nonlinear barrier mode for continuous nonlinear models. When enabled with OptimalityTarget=1, it seeks a local solution and may return LOCALLY_OPTIMAL; except for convex problems, that is not a global-optimality claim. If a nonlinear relationship is replaced with a static piecewise-linear approximation, optimality applies to that approximating model, not automatically to the original nonlinear formulation.
Why provable optimality improves auditability
An auditor, contract owner, union representative, or incident reviewer may ask how a planning decision was reached. “The algorithm chose it” is incomplete. This is why LLMs are not a suitable replacement on their own for optimization. "ChatGPT said this was optimal" will not hold up in court. A defensible answer identifies the rule set, objective, input snapshot, solver configuration, termination status, incumbent objective, best bound, gap, and any manual override.
Those artifacts let reviewers ask sharper questions. Was a proposed alternative infeasible because of a capacity rule, labor provision, or timing conflict? Was it feasible but worse under the documented objective? To investigate a specific alternative, teams can fix or constrain the relevant decisions and re-solve, then preserve the comparison.
The proof does not remove the burden of getting the model right. It shifts where the burden sits. The review can focus on whether the model faithfully represents the rules and priorities that accountable people approved — not on whether the plan merely looks good.
Explore how the Gurobi Optimizer fits into a governed decision workflow.
A six-step checklist for auditable optimization
Write every rule as a reviewable requirement. Map each requirement to a constraint or a documented downstream control. Ask the rule owner to approve that mapping, not merely the final schedule.
Version the inputs. Preserve the exact data snapshot, transformations, forecasts, units, and missing-data treatment used for each plan. A result cannot be reconstructed or defended without its inputs.
Record solution quality on every run. Save the model and solver versions, relevant parameters, status, incumbent value, best bound, relative and absolute gaps, runtime, log, and final constraint-violation metrics. Apply the same recordkeeping to routine runs and exceptions.
Diagnose infeasibility instead of hiding it. An INFEASIBLE status says no plan satisfies the modeled rules at the stated tolerances; reaching a time limit without an incumbent does not. Use Gurobi's infeasibility analysis to compute an irreducible inconsistent subsystem (IIS), then retain the IIS and the rule owner's interpretation.
Backtest incidents and edge cases. Re-run historical situations using the information that would have been available at the time. Check whether the model would have permitted the observed failure, and add or revise requirements through controlled model governance.
Keep accountable acceptance in the path. Give a qualified person authority to reject or override a plan, record the reason, and recheck feasibility after any manual change. Ensure operational controls enforce the accepted plan's limits independently.
Step four is easy to skip because infeasibility can look like a failed run. In a governed process, “no feasible plan exists under these modeled rules” is itself a result that deserves investigation.
To summarize, keep logs of everything, just as you would any part of a system of consequence.
Bring your model, stopping rules, and review requirements: Schedule a Discovery Call.
Frequently asked questions about provable optimality
Does provably optimal mean safe, correct, or risk-free?
No. It means no modeled-feasible solution improves the modeled objective beyond the specified tolerances. Safety, real-world correctness, compliance, and risk depend on the model, data, system context, assurance process, and accountable review.
Does an OPTIMAL status mean the MIP gap is exactly zero?
No. Gurobi's OPTIMAL status means the model was solved to optimality subject to tolerances, including any configured relative or absolute MIP-gap criterion. Record the achieved gap and the settings instead of interpreting the status as exact-arithmetic equality.
Can Gurobi establish global optimality for a nonconvex model?
It depends on the formulation and solution mode. Gurobi's global spatial branch-and-bound method maintains global bounds for supported nonconvex models and can establish optimality to the requested tolerances, while the optional nonlinear barrier mode for continuous models seeks local optimality and does not generally make that global claim.
Is a time-limited solution defensible?
Yes, if a feasible incumbent exists and its scope is reported honestly. Preserve the termination status, objective, best bound, gap, solver settings, data, and model; call it the best solution found with a quantified bound, not a proven-optimal solution. This can be necessary when decisions require fast turnarounds to keep operations going.
Does an infeasible status prove that no workable real-world plan exists?
No. It establishes that no solution satisfies the model as formulated, subject to tolerances. An IIS can identify an irreducible conflict among modeled constraints and bounds, but people must determine whether the conflict reflects reality, bad data, or a modeling error.
Can a heuristic process be audited?
Yes, but auditability and an optimality bound are different properties. A heuristic can preserve inputs, code, logs, and outputs, yet it generally cannot quantify how far its result is from the global optimum without an independent valid bound.
Provable optimality moves the central review question from “Why should we trust this answer?” to “Why should we trust this model, its inputs, and its stated tolerances?” That is a narrower claim — and a stronger audit trail.
Ready to evaluate that claim on your own planning problem? Start a free Gurobi trial.
