Optimality Gap

The incumbent solution is the best feasible solution found by the solver at a given point in the search. It represents the upper bound (for minimization problems) on the optimal solution's cost. Its quality directly determines the gap's numerator.

• Role: Provides the known, implementable plan (e.g., a specific vehicle route schedule).
• Source: Typically found by heuristic algorithms (like a greedy construction) early in the search and improved via local search or metaheuristics.
• Key Property: As the solver runs, the incumbent should monotonically improve, tightening the gap from above.

The lower bound is a provable, mathematical estimate of the best possible objective value, derived without necessarily finding a feasible solution. For minimization, the true optimum lies between this bound and the incumbent.

• Calculation Methods: Often comes from solving a Linear Programming (LP) relaxation of the original Mixed-Integer Programming (MIP) model, or from combinatorial arguments like the Held-Karp bound for the Traveling Salesman Problem (TSP).
• Role: Provides an absolute benchmark for solution quality. A gap of 0% means the incumbent's cost equals the lower bound, proving optimality.
• Progression: In exact algorithms like Branch and Bound, the global lower bound strengthens as the search tree is explored.

The absolute gap is the raw numerical difference between the incumbent solution's objective value and the best-known lower bound. It is the fundamental, unscaled measure of sub-optimality.

• Formula: Absolute Gap = Incumbent Value - Lower Bound Value (for minimization).
• Interpretation: A gap of 50 means the current best solution is 50 units (e.g., meters, seconds, dollars) worse than the theoretical optimum.
• Termination Criterion: Solvers often stop when the absolute gap falls below a user-defined tolerance (e.g., MIPGap = 0.001 in Gurobi), accepting a near-optimal solution.

The relative gap (or optimality gap percentage) is the absolute gap expressed as a percentage of the lower bound (or sometimes the incumbent). It is the standard, scale-invariant metric for reporting solution quality.

• Standard Formula: Relative Gap = ((Incumbent - Lower Bound) / |Lower Bound|) * 100%.
• Business Interpretation: A 5% gap indicates the current operational plan is at most 5% more expensive than the perfect, undiscovered plan. This quantifies the value of further computation.
• Decision Tool: Helps CTOs perform a cost-benefit analysis: Is closing the final 0.5% gap worth hours of additional compute time?

In the context of Mixed-Integer Programming (MIP), the dual bound is synonymous with the best global lower bound during the optimization process. It is the solution to the continuous relaxation of the active branch-and-bound nodes.

• Mechanism: As the solver branches on integer variables, it creates nodes with LP relaxations. The dual bound is the minimum objective value among all active node relaxations.
• Convergence: The dual bound increases (for minimization) during the search, while the incumbent decreases. The optimality gap closes as these two values converge.
• Practical Insight: A rapidly improving dual bound indicates the solver is effectively pruning the search space.

The integrality gap is a specific, structural component of the optimality gap for integer programs. It is the worst-case ratio between the optimal integer solution and the optimal solution to its LP relaxation.

• Definition: It's a property of the problem formulation, not a specific instance. A large integrality gap means the LP relaxation is weak, providing a poor lower bound and making the problem harder to solve.
• Impact on Solving: Problems with a large integrality gap (e.g., certain Vehicle Routing Problem (VRP) formulations) will have a large initial optimality gap, requiring sophisticated cutting-plane methods or stronger formulations to tighten bounds.
• Distinction: The optimality gap for a specific instance includes the integrality gap of its formulation but can be larger due to incomplete search.

A primary mathematical optimization technique used to model and solve problems like the VRP and job shop scheduling. MIP solvers compute both a best incumbent solution and a proven lower bound, providing the exact components needed to calculate the optimality gap. The gap closes to 0% when the solver proves optimality.

• Key Components: Linear objective function, linear constraints, integer decision variables.
• Solver Output: Incumbent value, best bound, optimality gap percentage.

A classification of computational complexity indicating that no known algorithm can solve the problem to guaranteed optimality in polynomial time for all cases. Most practical scheduling and routing problems (VRP, TSP, job shop) are NP-hard. This intrinsic intractability is the fundamental reason why we accept non-zero optimality gaps in real-world applications—finding the provably optimal solution is often computationally prohibitive for large instances.

Practical algorithms designed to find good feasible solutions to NP-hard problems within reasonable time, but without optimality guarantees. They are the primary source of incumbent solutions.

• Heuristic: Problem-specific, fast method (e.g., nearest neighbor, greedy insertion).
• Metaheuristic: High-level strategy guiding heuristics (e.g., Genetic Algorithms, Simulated Annealing, Tabu Search).

The optimality gap quantifies how far these heuristic solutions are from the best-known lower bound, guiding the trade-off between solution quality and compute time.

An exact algorithm for solving integer programming problems like MIPs. It systematically explores the solution space by:

• Branching: Dividing the problem into smaller subproblems.
• Bounding: Calculating optimistic bounds for each subproblem.
• Pruning: Discarding subproblems that cannot beat the current best solution.

This process continuously improves the global lower bound and updates the incumbent solution, dynamically reducing the optimality gap until it reaches zero (proving optimality) or the search is terminated by a time limit.

The mathematical expression that defines the goal of an optimization problem, such as minimizing total travel distance, makespan, or cost. The optimality gap is calculated relative to the value of this function.

• Formula: (Incumbent Value - Best Bound) / |Best Bound| * 100%.
• Minimization vs. Maximization: For minimization, the incumbent is an upper bound and the solver finds a lower bound. The gap is the percentage by which the incumbent exceeds the lower bound.