The integrality gap of a mixed integer programming (MIP) instance is the ratio between the optimal value of the linear programming (LP) relaxation (obtained by removing all integrality constraints and allowing integer variables to take any real value in range) and the optimal value of the MIP itself. For a minimisation problem, the LP relaxation always provides a lower bound on the MIP optimal, so the integrality gap equals MIP_opt divided by LP_opt, a number always greater than or equal to 1. For a maximisation problem, the LP relaxation is always an upper bound, so the gap equals LP_opt divided by MIP_opt, again at least 1. A gap of exactly 1.0 means the LP relaxation is perfectly tight: the optimal LP solution already satisfies all integer constraints (or can be rounded to an optimal integer solution at no cost). A gap of 1.5 means the LP relaxation underestimates (for minimisation) or overestimates (for maximisation) the true optimum by 50%.
The integrality gap is not a solver performance metric. It is a property of the LP relaxation formulation of the specific problem instance. Formulations of the same underlying problem can have radically different integrality gaps depending on how constraints are modelled. Adding valid inequalities (cutting planes) tightens the LP relaxation, bringing LP_opt closer to MIP_opt and thereby reducing the gap. Reformulating the problem to use stronger variable bounds or disaggregated constraints can achieve a gap of 1 on instances where the standard formulation has a gap of 2 or more. This is the central reason why OR formulation expertise remains irreplaceable even as solvers become faster: no amount of hardware acceleration can close a gap that formulation has left open.
The integrality gap connects directly to solver performance. Faster LP solving (via modern interior-point methods like PDHG) accelerates branch-and-bound on well-formulated problems with small gaps. On problems with large gaps, faster LP solving allows more LP relaxations to be computed in the same time, but cannot prevent the exponential branching that a large gap implies.
Standard formulation: Minimise the cost of locating warehouses and assigning customers to them. The LP relaxation allows warehouses to be fractionally open (e.g., a warehouse at 0.3 capacity). This fractional solution is artificial and almost never represents a feasible integer solution. The integrality gap can be 1.5 or larger.
Improved formulation: Add valid inequalities: "For each customer, the sum of warehouse assignments cannot exceed the total warehouse capacity." These additional constraints tighten the LP relaxation without cutting off any integer-feasible solutions. The gap shrinks to 1.1 or better.
The payoff: Solvers prove optimality orders of magnitude faster on the improved formulation, not because the hardware is faster, but because the branching tree is exponentially smaller.
Confusion 1: The integrality gap versus the MIP gap in solver output. When a solver is running, it displays an optimality gap (also called the MIP gap): the difference between the best feasible integer solution found so far (the incumbent) and the best lower bound (for minimisation), expressed as a percentage of the incumbent. This gap changes throughout the solve and reaches 0 when optimality is proved. The integrality gap is a theoretical, fixed property of a specific LP relaxation versus the true integer optimum. You cannot read the integrality gap from the solver log, because computing it would require already knowing the MIP optimal value. Confusing the two leads practitioners to interpret a large running MIP gap as evidence of a bad formulation (possibly true) or to believe a gap of 0% at termination means the LP relaxation was tight (not implied).
Confusion 2: Hardware closes the integrality gap. Faster LP solving means branch-and-bound can evaluate more nodes per second, potentially proving optimality faster on well-formulated problems. But on problems with large integrality gaps, the branching tree is exponentially larger regardless of LP speed: the solver must enumerate more nodes before finding and proving the optimum. Hardware acceleration reduces wall-clock time per node; it does not reduce the number of nodes required when the formulation is weak. Adding valid inequalities (cutting planes), tightening variable bounds, or using a stronger reformulation are the tools that reduce the integrality gap and therefore reduce the tree size. Practitioners who respond to a slow-solving MIP by upgrading hardware are often addressing the wrong bottleneck.
Confusion 3: Instance-level gap versus problem-class gap. The integrality gap of a specific MIP instance is a number. The integrality gap of a problem class (such as the Travelling Salesman Problem, vertex cover, or bin packing) refers to the worst-case ratio across all instances, which governs the approximation ratio achievable by LP-rounding algorithms. Practitioners sometimes refer to "the integrality gap of our routing problem" as if it were a constant, when in fact it varies by instance structure, constraint density, and how the formulation is constructed.
Solve the LP relaxation of your MIP and compare the LP optimal value to the best integer solution you can find (either by running the MIP to proven optimality on a small instance, or by using a known upper bound for the problem class). If the ratio exceeds 1.2 to 1.3 for a minimisation problem, strong cutting planes or reformulation are likely to yield a larger improvement than hardware upgrades. If the gap is below 1.05, the formulation is already tight and solver speed becomes the primary lever.
The integrality gap is a property of the formulation, not the solver. If your MIP is slow, measure the gap before upgrading hardware — a loose formulation wastes compute regardless of solver speed.