The MIP Gap Is a Decision Bound

The MIP Gap Is Not a Quality Score

One of the easiest solver numbers to misuse is the MIP gap.

A model finishes with a 2% gap and someone says the solution is 98% optimal. Another run stops at 8% and gets labeled bad. A third run reaches 0.1% and gets celebrated even though the recommended operating decision is effectively identical to the one found twenty minutes earlier.

That is not what the gap means.

For a minimization MILP, the solver maintains an incumbent objective value—the best feasible solution it has found—and a bound on how good any still-undiscovered solution could possibly be. A relative gap summarizes the distance between those two numbers. For a maximization problem the direction flips, but the idea is the same.

The gap is a statement about the modeled objective, not a direct statement about business regret, forecast quality, implementation quality, or whether the decision is operationally sensible.

That distinction matters a lot in production optimization.

Start With the Actual Decision

Before discussing solver tolerances, write down what the system is deciding.

Suppose a supply-chain model chooses purchase quantities by SKU and vendor:

[ q_i \in {0, p_i, 2p_i, \ldots} ]

where (p_i) is the case-pack size. The model may also include binary variables for opening vendor orders, satisfying shared MOQs, activating lanes, selecting production setups, or choosing which inventory opportunities receive scarce capacity.

A simplified objective might be

[ \max_x ; \text{ExpectedMargin}(x)

• \text{HoldingCost}(x)
• \text{ShortageCost}(x)
• \text{Freight}(x)
• \text{OrderingCost}(x). ]

Now ask the questions that actually matter:

• Which decisions are executed immediately?
• Which variables are only planning artifacts for future periods?
• What is the dollar scale of the objective?
• How much can the first-period decision change before operations care?
• Which constraints create discrete breakpoints such as MOQs, truckloads, setups, or capacity tiers?
• How uncertain are the economic coefficients feeding the objective?
• What happens operationally if the solve runs another 5, 20, or 60 minutes?

A stopping rule should be connected to those answers. A generic MIPGap = 0.01 is not a business requirement.

What the Solver Actually Knows

Assume a maximization model currently has:

• incumbent objective: $9.80 million
• best bound: $10.00 million

The solver has proved that no feasible solution can exceed $10.00 million, while it already possesses a feasible solution worth $9.80 million under the model.

The absolute optimization opportunity left is therefore at most:

[ 10.00 - 9.80 = 0.20 \text{ million}. ]

The relative gap is roughly 2%.

The useful business translation is not:

We are 98% optimal.

It is closer to:

Under this model, the most we could possibly gain by continuing the exact search is about $200,000 of modeled objective value.

That is a much better sentence because it immediately creates the next question: is another $200,000 worth chasing?

Sometimes yes. Sometimes absolutely not.

The Absolute Gap Is Often More Useful Than the Percentage

Percentages hide scale.

A 1% gap on a $500 million objective can represent $5 million of unresolved modeled value. A 10% gap on a small subproblem might represent $8,000.

The percentage alone tells you almost nothing about operational importance.

In production, I like to log at least:

[ \text{AbsoluteGap} = |z_{incumbent} - z_{bound}| ]

along with the relative gap.

Then translate the absolute gap into the economics of the decision.

If a procurement model controls $200 million of spend but the objective is mostly unavoidable purchase cost, the raw objective scale may also be misleading. A 0.5% gap against total spend could look huge even though the discretionary economic value being optimized is much smaller.

This is why objective design matters. If the solver objective contains giant constants or accounting terms that do not vary with the decision, relative gaps can become difficult to interpret economically.

The Gap Bounds the Model, Not Reality

This is the most important caveat.

Suppose the solver proves a 0.01% gap. That means it has nearly closed the mathematical gap for the model you gave it.

It does not prove that:

• demand was modeled correctly,
• lead-time uncertainty was realistic,
• lost-sales economics were estimated correctly,
• substitution was captured,
• the inventory state was clean,
• the MOQ hierarchy matches the vendor agreement,
• planners will execute the recommendation,
• the objective reflects actual profit,
• or the model contains the right decision in the first place.

A beautifully solved wrong model is still a wrong decision system.

In many real supply-chain systems, input and structural uncertainty are economically larger than the final few basis points of solver gap. Spending an hour moving from 0.5% to 0.05% can be irrational if forecast error, lead-time uncertainty, or cost estimation can move the decision by several percent.

That does not make exact optimization unimportant. It means solver precision has to be viewed in the same economic system as every other approximation.

Decision Stability Can Matter More Than Gap Closure

Imagine the following solve history:

Time	Incumbent	Bound	Gap	Immediate purchase decision
10 sec	$9.62M	$10.40M	7.5%	182,400 units
30 sec	$9.78M	$10.18M	3.9%	185,100 units
2 min	$9.84M	$10.04M	2.0%	185,300 units
10 min	$9.86M	$9.92M	0.6%	185,300 units
30 min	$9.87M	$9.88M	0.1%	185,300 units

The solver continues proving things for twenty additional minutes, but the executable decision stopped changing at two minutes.

That is useful information.

It does not mean you should blindly terminate whenever the incumbent stops moving. The solver might later discover a structurally different and materially better solution. But it means decision stability should be part of the production telemetry.

Track things such as:

• percentage of first-stage quantities that changed,
• total units changed,
• dollar-weighted decision change,
• number of vendors whose MOQ activation changed,
• number of binary commitments that flipped,
• change in expected economic value,
• and whether the operational action set changed at all.

A solver gap tells you how much mathematical opportunity remains. Decision stability tells you whether that opportunity is still changing what you intend to do.

You want both.

Not Every Variable Deserves Equal Attention

A long-horizon planning MILP might contain decisions for 52 weeks, but perhaps only this week’s purchase orders will actually be released.

If weeks 20 through 52 keep rearranging while week 1 remains fixed, the global MIP gap can continue shrinking even though the actionable decision is stable.

This is a framing issue.

Separate:

1. commitment variables — decisions that will be executed now,
2. lookahead variables — future decisions needed to price consequences correctly,
3. state variables — inventory, backlog, capacity, or flow accounting,
4. auxiliary variables — mathematical structure used to formulate the model.

Then monitor stability at the commitment boundary.

The whole solution vector does not have to be identical for the operational recommendation to be effectively identical.

Discrete Decisions Make the Story More Interesting

MILPs are difficult precisely because important business decisions are often discrete.

Suppose a vendor requires a $50,000 MOQ. Below that threshold, the order is infeasible. Above it, a large family of SKU quantities suddenly becomes available.

The incumbent may sit on one side of that breakpoint while the bound suggests unexplored value on the other side. A seemingly small objective gap can still contain a meaningful structural change.

The same issue appears with:

• opening a facility,
• adding a truck,
• selecting a production setup,
• activating a supplier,
• accepting a price-break tier,
• choosing an assortment,
• or crossing a labor-capacity threshold.

This is why I would not reduce a production stopping policy to a single percentage. You should know which economically important binary decisions are still unstable.

A 0.8% gap with all strategic activations fixed may be acceptable. A 0.3% gap where the model is still flipping between two suppliers may deserve more time.

Uncertainty Should Change How You Think About Precision

Now put the MILP inside an uncertain supply chain.

Demand (D), lead time (L), yield (Y), and perhaps price or capacity are random. The objective may really be an approximation to something like:

[ \max_x ; \mathbb{E}[\Pi(x, D, L, Y)] - \lambda \cdot \text{Risk}(x). ]

If the expectation is estimated with scenarios or simulation, the objective itself may have sampling noise.

Suppose candidate A evaluates to $9.84M and candidate B to $9.86M, but the Monte Carlo standard error of the difference is $70,000. Treating the $20,000 estimated difference as sacred would be nonsense.

You now have at least three different uncertainties:

• optimization uncertainty: the unresolved incumbent-to-bound gap,
• statistical uncertainty: noise in estimating candidate value,
• model uncertainty: error in the assumptions and economic representation.

They should not be confused.

A mature system spends precision where precision can actually change the decision.

Build a Business-Aware Stopping Policy

A useful production stopping policy can combine several conditions instead of relying on one solver parameter.

For example, stop when any of the following is true:

1. The solver reaches the hard runtime SLA.
2. The absolute bound gap falls below an economically meaningful threshold.
3. The relative gap falls below a standard tolerance.
4. The incumbent has not materially improved for a defined period and the commitment decisions are stable.
5. The remaining bound opportunity is smaller than the uncertainty in downstream economic evaluation.

You may still configure the solver’s native MIP gap and time limit, but the orchestration layer should understand the business context around those settings.

A simple conceptual rule might be:

[ \text{stop if } \Delta z_{bound} < \tau_{econ} \quad \text{and} \quad \Delta x_{commit} < \tau_{decision}. ]

Here (\tau_{econ}) is an economic tolerance and (\tau_{decision}) is a decision-change tolerance.

That is much closer to what the business actually means by “good enough.”

Questions to Ask Before Choosing a Gap Tolerance

When someone asks, “What should our MIP gap be?” I would not answer with a number first.

Ask:

• What is the objective measured in?
• What is the typical incumbent value?
• How much of that value is actually controllable by the optimization?
• What dollar improvement would be material?
• What is the runtime SLA?
• What happens if no incumbent exists at timeout?
• How quickly do good incumbents normally appear?
• Which first-stage decisions must be stable?
• Are there major discrete thresholds still flipping late in the solve?
• How noisy is the objective evaluation?
• How often is the model solved?
• Can yesterday’s solution provide a warm start?
• Is the same model solved thousands of times, making small runtime savings operationally large?

The correct tolerance for a monthly network-design study may be completely different from the tolerance for a replenishment service that solves every SKU-vendor scope every hour.

Implementation: Log the Solve as a Time Series

Do not only store the final status.

For each production solve, capture a trajectory such as:

elapsed_seconds
incumbent_objective
best_bound
absolute_gap
relative_gap
node_count
solution_count
first_incumbent_time
last_incumbent_improvement_time
commitment_decision_hash
commitment_change_from_previous_incumbent

Also record model context:

model_version
solver_version
parameter_set
input_snapshot_id
scenario_set_id
variable_count
binary_count
constraint_count
warm_start_used
termination_reason

This gives you the evidence needed to tune the system intelligently.

You can answer questions like:

• Does 95% of economic improvement happen in the first 20 seconds?
• Is runtime spent finding better incumbents or proving the bound?
• Which model families routinely fail to find an incumbent?
• Does a warm start improve the first feasible solution?
• At what point do commitment decisions stop changing?
• Are certain vendors or constraint structures responsible for long tails?

Without this history, solver tuning becomes folklore.

Failure Mode: Optimizing the Gap Instead of the Decision

A team sees a 4% gap and starts tuning cuts, heuristics, presolve, threads, and branching parameters.

Maybe that is appropriate.

But first inspect the solve trajectory.

If the incumbent is found in 15 seconds and never improves, while the remaining 20 minutes are spent tightening the bound, the operational problem may not be incumbent quality. The issue may be proof difficulty.

If the business only needs a high-quality executable decision in 60 seconds, your engineering strategy changes. Warm starts, primal heuristics, decomposition, better incumbent construction, or a stronger formulation may matter more than chasing a tiny final gap.

Conversely, if the bound is tight immediately but the solver struggles to find good feasible solutions, you have a different problem.

The same final gap can hide very different solver behavior.

Failure Mode: Comparing Gaps Across Different Objectives

Suppose model version A has a 1.2% gap and version B has a 0.6% gap.

That does not automatically mean B solves better.

If you changed the objective scaling, added a large constant term, modified penalties, or changed the economic horizon, the percentages may no longer be comparable.

Compare:

• incumbent quality on a common economic evaluation,
• absolute bounds where meaningful,
• runtime trajectories,
• decision stability,
• and out-of-sample performance.

A prettier solver statistic is not the objective of the project.

Failure Mode: No Feasible Incumbent

A 5% gap is inconvenient. No executable solution is much worse.

Production systems need a fallback hierarchy.

For example:

1. use the best feasible incumbent from the current solve,
2. repair a warm-start solution against current constraints,
3. run a fast feasibility-oriented heuristic,
4. fall back to the previous accepted decision where still valid,
5. escalate scopes that remain infeasible or unsafe.

This is part of the decision architecture, not an afterthought.

A model that theoretically proves optimality in 30 minutes but occasionally has no feasible solution at a 2-minute operational deadline may be less useful than a model that reliably produces excellent incumbents in 10 seconds.

Metrics That Actually Help

For a production MILP, I would monitor at least four classes of metrics.

Solver metrics: runtime, incumbent, bound, relative gap, absolute gap, nodes, first-incumbent time, termination reason.

Decision metrics: commitment-variable stability, quantity changes, binary activation changes, feasibility after downstream business rules, override rate.

Economic metrics: modeled objective, independently evaluated profit or cost, improvement versus baseline, opportunity remaining at termination.

Operational metrics: end-to-end latency, percentage of solves meeting SLA, percentage returning feasible incumbents, fallback frequency, execution rate.

This prevents the solver from becoming the only judge of its own usefulness.

What to Do in Practice

Treat the MIP gap as a bound on unresolved modeled economic opportunity.

Then connect it to the actual decision.

For a new production model, start by logging the full incumbent-and-bound trajectory across representative instances. Measure when the executable decisions stabilize. Convert absolute gaps into dollars or another business unit. Compare those gaps with forecast, simulation, and parameter uncertainty. Identify the binary commitments that remain unstable late in the solve. Establish a hard runtime SLA and a fallback path before deployment.

Only then choose tolerances.

You may discover that 2% is completely adequate for one model and 0.1% is necessary for another. You may discover that the gap is not your bottleneck at all. You may even discover that most of the runtime is being spent proving a decision the business already had five minutes ago.

The solver’s job is not to make the gap number look impressive.

The job is to produce a defensible decision, within the time available, with enough evidence to know what you are leaving on the table.