MIP Optimality Gap: (bounds, logs, stop rules)

Beginner → intermediate

Always translate “gap” into a certified interval

The most robust way to read the gap is as a statement about where the optimum must lie:

Minimization: BestBound ≤ Optimum ≤ Incumbent
Maximization: Incumbent ≤ Optimum ≤ BestBound

If you can write this interval, you can explain to a non-technical audience what is proven, what is unknown, and how much better (or worse) things could still get.

People also ask

What happens if there is no incumbent yet?

If no feasible integer solution has been found, the solver has no incumbent—so any “gap” number is either undefined or not decision-useful. Your priority is feasibility, not proof of optimality: check constraints and bounds, simplify logic, or provide a warm start.

If this feels fuzzy, the ILP beginner’s guide is a good bridge to feasibility concepts.

Formulas

Absolute gap (objective units) is usually the best decision tool

AbsoluteGap = |Incumbent - BestBound|

This is often the most intuitive measure: “We’re guaranteed to be within 500 dollars of the optimum” or “within 3 minutes of the fastest possible schedule.” If your objective has real-world units, absolute gap is usually where you start.

Formulas

Relative gap is common—but definitions differ slightly by solver

RelativeGap = |Incumbent - BestBound| / (|Incumbent| + ε)

# some solvers use |BestBound| in the denominator instead
# ε avoids division by zero or numerical explosion near 0

Relative gap makes it easier to compare performance across instances of different scale. But it can be misleading when objectives can be near zero or can change sign.

Edge case

Why negative objectives make gap percentages look odd

Imagine a maximization problem where your incumbent is −50 and your best bound is +10. Any relative-gap formula can give a strange percentage—but the interval remains crystal clear: “The optimum lies in [−50, 10].”

For reporting, always show absolute gap and the interval. Include the solver-specific percentage only if you document how it’s computed.

Mechanics

Best bound is built from relaxations over many nodes

Most MIP solvers use branch-and-bound (usually with cuts). At each node in the search tree, they solve a relaxed problem—often the LP relaxation—to get a bound on what that subtree could ever achieve.

The “best bound” in logs is the best (lowest for min, highest for max) among these node bounds. It is, by construction, a global guarantee on where the true optimum can’t possibly be beaten.

The quality of this bound depends on your formulation; the LP relaxation bound is the easiest place to see this structurally.

Why gaps stall

Three stall patterns (and how to respond)

Logs

1) Look at the root relaxation first

The root LP relaxation objective is your first bound. If it is very far from any realistic integer solution, the solver will have weak pruning power and the gap is more likely to stall. That’s a signal to improve the formulation, not just increase time.

Logs

2) Watch incumbent and best bound as separate “stories”

The incumbent tells you how good your best known solution is. The best bound tells you what’s still mathematically possible. Plotting or mentally tracking both is more informative than watching a single percentage.

Logs

3) Translate the log into a sentence you can defend

Minimization example:
Incumbent (best feasible) = 12400
Best bound (proven)       = 11900

Certified statement:
"The true optimum is in [11900, 12400]."

That sentence is unit-aware and solver-agnostic. It’s also what non-specialists actually need to hear.

Mini-lab

Lab 1: Compute a defensible bound interval (ILP vs LP relaxation)

1. Solve your integer model in the ILP/MIP calculator. Record the incumbent objective.
2. Relax integrality and solve the new model in the LP calculator. Record the LP relaxation objective.
3. Use the min/max formulas above to write the certified interval for the optimum.

Mini-lab

Lab 2: Diagnose a stubborn gap as a “bound problem” or “incumbent problem”

1. Run your model with a moderate time limit; note how quickly the incumbent improves vs how quickly the best bound moves.
2. If incumbents improve but the bound doesn’t, inspect your LP relaxation with LP relaxation bound and tighten formulation.
3. If the bound improves but incumbent doesn’t, focus on feasibility and heuristics (warm starts, simplified logic, better initial solutions).

Worked example

Example 1: baseline minimization gap

Incumbent = 12400
BestBound = 11900

AbsoluteGap = 12400 - 11900 = 500
RelativeGap ≈ 500 / 12400 ≈ 4.03%

Certified interval: Optimum ∈ [11900, 12400]

If you know that “within 200 units of optimal” is fine in your application, this result tells you you’re not there yet. You can now rationally choose to run longer or improve the formulation to tighten the bound.

Worked example

Example 2: negative objective (maximization)

Maximization example:

Incumbent = -50
BestBound =  10

Certified interval: Optimum ∈ [-50, 10]
AbsoluteGap = 60

The relative gap may look odd or large depending on the denominator, but the interval says everything: there is at most 60 units of improvement possible.

Worked example

Example 3: “gap won’t close” due to oversized Big‑M

Suppose a model uses constraints like 0 ≤ y ≤ 10,000 · x with x binary. In the LP relaxation, x can be fractional and still allow large y, making the bound unrealistically strong. The solver’s best bound stays far from realistic integer solutions, so the gap appears stuck.

Fix: derive the smallest valid multiplier (e.g., capacity or demand limit) and use that instead of 10,000. For a checklist of safe Big‑M practices, see how to model an ILP.

Stop policy

Use objective units to define “good enough”

Most practitioners combine:

• a relative gap target (e.g., 1–5%) for comparability across instances,
• an absolute gap target in meaningful units (e.g., “≤ $100 of optimal”), and
• a time limit to control total runtime.

When setting stop rules, always tie them back to decision impact: how much would a slightly better solution really change your action?

Misconception

“Gap = 0% means my real-world decision is correct”

Gap = 0% means the solver proved optimality for your model, not for reality. If a solution is unusable, it is usually a modeling issue (missing constraints, wrong units, misaligned objective). Use how to model an ILP as a checklist when this happens.

Common mistake

Mixing up optimality gap with integrality tolerance

Optimality gap is about objective values (incumbent vs best bound). Integrality tolerance decides how close to an integer a variable must be to count as integer-feasible. Seeing 0.99999 instead of 1.0 is an integrality-tolerance question, not a gap problem.

Common mistake

Comparing gaps across different models

If you change constraints or objectives, you’ve changed the optimization problem. Gaps from different models are not directly comparable. When benchmarking, keep the model fixed and vary only time or formulation details, and report incumbent, best bound, and runtime together.

Reporting

A minimal, defensible reporting template

• Model: summary of objective, main constraints, and data source/version.
• Solver setup: solver name/version, key parameters (time limit, gap tolerances), and hardware if relevant.
• Outcome: incumbent objective, best bound, certified interval, absolute gap, relative gap (with definition).
• Status: optimal proven vs stopped early (time, gap, or user stop), with a short justification.

This structure speaks well to both technical reviewers and non-technical stakeholders because it makes uncertainty explicit and reproducible.