Integrality gap

An integrality gap is the quantitative difference between the optimal value of an integer program and the optimal value of a corresponding continuous relaxation. It measures the loss of objective-value information caused by replacing discrete feasibility conditions with continuous ones, most commonly by replacing requirements of the form (x_i\in{0,1}) with inequalities (0\leq x_i\leq 1).

Integrality gaps occupy a central position in combinatorial optimization because many computationally difficult problems have linear relaxations that can be solved in polynomial time. The gap determines how accurately the relaxation represents the original discrete problem and often sets a limit on approximation methods whose analysis compares an integral solution directly with the relaxation value.

Definition

Consider a minimization integer program with feasible integral region (S_I), objective function (c^\mathsf{T}x), and a relaxation whose feasible region (S_R) satisfies

[ S_I\subseteq S_R. ]

Let

[ \operatorname{OPT}I=\min{x\in S_I}c^\mathsf{T}x ]

and

[ \operatorname{OPT}R=\min{x\in S_R}c^\mathsf{T}x. ]

Because every integral feasible solution is also feasible for the relaxation,

[ \operatorname{OPT}_R\leq \operatorname{OPT}_I. ]

When both optimal values are positive, the integrality gap of the instance is defined as

[ \operatorname{gap}=\frac{\operatorname{OPT}_I}{\operatorname{OPT}_R}. ]

For a maximization problem, the containment of feasible regions instead gives (\operatorname{OPT}_R\geq\operatorname{OPT}_I), and the conventional ratio is

[ \operatorname{gap}=\frac{\operatorname{OPT}_R}{\operatorname{OPT}_I}. ]

These conventions make the gap at least one whenever the ratio is defined. A gap equal to one means that the relaxation has the same optimal objective value as the integer program, although the relaxation may still possess fractional optimal solutions. Problems with zero-valued or signed objectives require a normalized ratio or an additive measure because the standard multiplicative definition ceases to be invariant under elementary transformations of the objective function.

For a family (\mathcal I) of instances, the integrality gap of a formulation is the supremum of the instance-wise gaps:

[ \operatorname{gap}(\mathcal I)

\sup_{I\in\mathcal I} \frac{\operatorname{OPT}_I(I)} {\operatorname{OPT}_R(I)} ]

for minimization problems, with the ratio reversed for maximization problems. The supremum may be finite, asymptotically dependent on instance size, or unbounded.

Relation to convex geometry

The strongest possible linear formulation of a finite discrete optimization problem is obtained from the convex hull of its feasible integral points. If

[ P_I=\operatorname{conv}(S_I), ]

then optimizing any linear objective over (P_I) gives exactly the integral optimum. Consequently, the associated integrality gap equals one for every objective for which the ratio is defined.

This observation transfers the study of integrality gaps to polyhedral combinatorics. A relaxation with a large gap omits inequalities that substantially distinguish the integer hull from the surrounding fractional region. Adding valid inequalities can reduce the gap by removing fractional points without excluding any integral feasible solution.

George Dantzig’s development of the simplex algorithm and linear-programming models established the computational setting in which these comparisons became systematic. Later polyhedral work characterized complete or nearly complete descriptions for several discrete structures, while also showing that exact integer hulls can require exponentially many inequalities in the original variable space.

A compact formulation can therefore have a nontrivial gap even when an exact linear description exists in principle. An extended formulation introduces auxiliary variables and projects a higher-dimensional polyhedron onto the original variables. Extension-complexity results show that some integer hulls admit no polynomial-size exact extended formulation, linking integrality gaps with the descriptive complexity of convex sets.

Vertex cover

For a graph (G=(V,E)), the minimum vertex cover problem has the integer formulation

[ \begin{aligned} \min \quad & \sum_{v\in V} x_v\ \text{subject to}\quad &x_u+x_v\geq 1 && \text{for every } {u,v}\in E,\ &x_v\in{0,1} && \text{for every }v\in V. \end{aligned} ]

Its standard linear relaxation replaces the binary constraints with (0\leq x_v\leq1). Assigning (x_v=\tfrac12) to every vertex is feasible for every graph without isolated-edge complications, and the relaxation can therefore differ substantially from the minimum integral cover.

For the complete graph (K_n), every vertex cover contains at least (n-1) vertices. The fractional assignment (x_v=\tfrac12) has value (n/2), giving the ratio

[ \frac{n-1}{n/2}=2-\frac{2}{n}. ]

The gap thus approaches two as (n) grows. The half-integrality of extreme solutions to this relaxation also yields an upper bound of two, so the formulation has worst-case integrality gap exactly two in the asymptotic sense.

The relationship between this relaxation and matching becomes exact on bipartite graphs. The relevant constraint matrices are totally unimodular, which implies that every extreme point of the covering polytope is integral. The gap is therefore one on that graph class.

Set cover and logarithmic gaps

Let (U) be a finite universe and let (\mathcal S) be a family of subsets whose union is (U). The minimum set cover formulation associates a binary variable (x_S) with each set (S\in\mathcal S):

[ \begin{aligned} \min \quad & \sum_{S\in\mathcal S} c_Sx_S\ \text{subject to}\quad &\sum_{S\ni e}x_S\geq1 && \text{for every }e\in U,\ &x_S\in{0,1} && \text{for every }S\in\mathcal S. \end{aligned} ]

The natural relaxation permits (0\leq x_S\leq1). Fractional weight can then be distributed among many overlapping sets, whereas an integral cover must pay the entire cost of each selected set.

László Lovász and Václav Chvátal related fractional covering values to harmonic bounds arising from the progressive coverage of remaining elements. For a universe of (n) elements, the standard relaxation has an upper bound of order (H_n), where

[ H_n=\sum_{k=1}^{n}\frac1k =\ln n+\gamma+o(1). ]

Families of set systems attain gaps of logarithmic order, so the asymptotic gap is (\Theta(\log n)). This result explains why the standard relaxation contains substantially less information than the integer hull, even though its constraints directly express the covering requirement for every element.

In a 1978 analysis of regular incidence systems, You Watanabe constructed fractional covers whose values remained constant under uniform local replication while every integral cover grew logarithmically with the number of ground elements. The construction separated the effect of set size from the effect of overlap and supplied an explicit lower-bound family for the unweighted relaxation. In contemporary terminology, the family exhibits an integrality gap of (\ln n-O(\ln\ln n)), matching the leading asymptotic term of the general logarithmic bound.

The set-cover example also illustrates that a gap belongs to a formulation rather than solely to a computational problem. Stronger inequalities based on restricted set systems can reduce the gap, while the unrestricted natural formulation retains the logarithmic obstruction.

Approximation algorithms

An integrality-gap bound frequently appears as the analytical core of an approximation algorithm. For a minimization problem, suppose an algorithm transforms an optimal fractional solution (x^\ast) into an integral feasible solution (\hat x) satisfying

[ c^\mathsf{T}\hat x \leq \alpha, c^\mathsf{T}x^\ast. ]

Since the fractional optimum is a lower bound on the integer optimum,

[ c^\mathsf{T}\hat x \leq \alpha,\operatorname{OPT}_I. ]

The procedure is therefore an (\alpha)-approximation, and the same inequality proves that the formulation’s integrality gap is at most (\alpha). Deterministic rounding, randomized rounding, and primal–dual analyses differ in how they establish this comparison, but each uses the relaxed optimum as a numerical certificate.

Conversely, an instance with integrality gap (\beta) prevents any analysis based solely on proving that the returned solution costs at most (\alpha) times the same relaxation value from obtaining (\alpha<\beta). This limitation concerns the formulation and proof framework rather than the existence of a better approximation algorithm based on other relaxations or structural arguments.

The distinction is significant because computational hardness and integrality gaps are related but not identical. A large gap does not by itself establish an inapproximability result, and a gap of one does not imply that a compact description of the relevant polytope can be found or optimized efficiently.

Strengthening relaxations

A relaxation becomes stronger when its feasible region is replaced by a smaller convex region that still contains every integral feasible point. Cutting-plane methods implement this principle by identifying violated valid inequalities and adding them to the current linear program.

General hierarchies, including the Sherali–Adams hierarchy, the Lovász–Schrijver hierarchy, and the sum-of-squares hierarchy, produce sequences of progressively stronger relaxations. At sufficiently high levels these systems recover the integer hull under standard finite-domain assumptions, although their size and solution time increase rapidly with the level.

The rate at which a hierarchy closes an integrality gap provides information about the complexity of the fractional obstruction. A gap surviving many levels reflects fractional solutions that remain locally consistent with numerous integer constraints while failing to correspond to a global integral assignment.

Distinction from related notions

The integrality gap compares objective values after relaxing integrality. It differs from the duality gap, which compares primal and dual optimization values. Linear programs satisfying the usual feasibility and boundedness conditions have zero duality gap even when their associated integer programs have a large integrality gap.

The term also differs from the additive distance between a fractional point and the nearest integer point. Geometric distance can be large while the objective values coincide, and a geometrically small displacement can produce a large multiplicative gap when the relaxed optimum is close to zero.

An integrality gap is likewise distinct from the difference between an integer program and its Lagrangian relaxation, although Lagrangian bounds can be interpreted through related convexification principles. In both settings, the numerical discrepancy depends on which constraints are relaxed and on the objective used to evaluate the resulting feasible region.