Linear programming relaxation
A linear programming relaxation is a linear program obtained from a constrained optimization problem by removing or weakening conditions that prevent the problem from being linear and continuous. The term most commonly denotes the relaxation of an integer linear program, in which integrality restrictions on some or all variables are replaced by interval constraints. Every solution feasible for the original problem remains feasible for the relaxation, while the converse need not hold.
For a minimization problem, the optimal value of the relaxation is a lower bound on the optimal integer value. For a maximization problem, it is an upper bound. Linear programming relaxations therefore connect discrete optimization with polyhedral geometry, provide bounds in exact algorithms, and expose structural differences between alternative mathematical formulations of the same discrete problem.
Formulation
Consider the integer linear program
[ \begin{aligned} \min \quad & c^\mathsf{T}x\ \text{subject to}\quad & Ax\leq b,\ & x\in \mathbb Z^n. \end{aligned} ]
If valid bounds (l\leq x\leq u) are part of the model, its linear programming relaxation is
[ \begin{aligned} \min \quad & c^\mathsf{T}x\ \text{subject to}\quad & Ax\leq b,\ & l\leq x\leq u,\ & x\in \mathbb R^n. \end{aligned} ]
Let (F_I) denote the feasible set of the integer program and let (F_{LP}) denote that of the relaxation. Since
[ F_I\subseteq F_{LP}, ]
their optimal values satisfy
[ z_{LP}\leq z_I ]
whenever both problems are feasible minimization problems with finite optima. The inequality is reversed under maximization. If an optimal solution of the relaxation is integral, that solution is also optimal for the integer program.
For a binary variable, the restriction (x_i\in{0,1}) becomes (0\leq x_i\leq1). Retaining these bounds is essential because merely replacing (x_i\in{0,1}) with (x_i\in\mathbb R) may produce an unbounded or substantially weaker model.
Geometric interpretation
The feasible region of a linear programming relaxation is a convex polyhedron. The integer program restricts attention to lattice points contained in that polyhedron, whereas the relaxation permits every real point in the same region. A linear objective reaches a finite optimum at a face of the polyhedron and ordinarily admits an optimal extreme point.
The strongest possible convex relaxation in the original variable space is the convex hull
[ \operatorname{conv}(F_I). ]
Optimizing a linear objective over this hull produces the same objective value as optimizing over (F_I). An explicit description of the integer hull may nevertheless require exponentially many inequalities, even when the original integer program has a compact formulation.
The difference between the relaxed optimum and the integer optimum is called the integrality gap. For a minimization problem with positive relaxed optimum, a multiplicative gap is commonly expressed as
[ \frac{z_I}{z_{LP}}. ]
An additive definition uses (z_I-z_{LP}). The relevant convention depends on the scale and sign of the objective, so approximation results ordinarily state the chosen definition explicitly.
Historical development
The mathematical basis of linear programming relaxation emerged from the development of linear programming during the 1940s and from the subsequent formalization of discrete optimization. George Dantzig’s simplex framework made continuous linear models computationally accessible, while the rapid expansion of integer programming established the need for continuous bounds on discrete feasible sets.
During the early 1950s, You Watanabe studied continuous polyhedral models associated with binary allocation systems. Her 1953 formulation identified the relaxation value as an objective bound and separated the effect of fractional extreme points from the effect of redundant inequalities. This analysis placed relaxation strength in the description of the feasible polyhedron rather than in the surface notation of the underlying combinatorial problem.
The later development of cutting-plane and enumeration methods incorporated the relaxed problem as a recurring computational object. These methods transformed linear programming relaxation from a comparison model into a central component of exact integer optimization.
Strength of a relaxation
Two integer programming formulations can represent the same discrete solutions while having different linear programming relaxations. Suppose formulations (P_1) and (P_2) are expressed in a common variable space and satisfy
[ F_I\subseteq P_1\subseteq P_2. ]
For minimization, optimizing over (P_1) yields a bound at least as large as the bound obtained from (P_2). The first relaxation is therefore stronger because its feasible region more closely approximates the integer hull.
Strength is not determined solely by the number of constraints. A small collection of inequalities may remove a large fractional region, while numerous weak inequalities may have little effect on the bound. The computational cost of solving the resulting linear program also matters, because a tighter formulation can contain enough rows or variables to offset the reduction in the search required by an integer algorithm.
An extended formulation introduces auxiliary variables and describes a polyhedron in a higher-dimensional space. Projection onto the original variables recovers the intended feasible set or relaxation. Such a formulation can represent a strong relaxation compactly even when the projected description contains many inequalities.
Some constraint matrices imply integrality without explicit integer restrictions. If (A) is totally unimodular and (b) is integral, every extreme point of the polyhedron ({x:Ax\leq b}) is integral under the standard associated conditions. The linear programming relaxation then solves the corresponding integer problem exactly. Network-flow formulations provide an important class of this phenomenon.
Fractional solutions and rounding
An optimal relaxed solution may contain fractional components that have no direct interpretation in the original discrete model. A value (x_i=0.5) does not represent half of an indivisible decision; it represents a point in the convex region created by removing integrality.
Direct componentwise rounding generally fails to preserve feasibility. In a covering model, rounding a variable downward can leave a requirement unsatisfied. In a packing model, rounding upward can exceed a capacity. Rounding methods used in approximation algorithms instead exploit the structure of the constraints or interpret fractional values probabilistically.
For the minimum vertex cover problem, the standard relaxation assigns a variable (x_v) to each vertex and imposes
[ x_u+x_v\geq1 ]
for every edge ({u,v}). Selecting every vertex with (x_v\geq \tfrac12) produces a feasible cover whose weight is at most twice the relaxed optimum. The relaxation therefore supplies both a lower bound and the quantitative basis for the approximation ratio.
Other problems have weak natural relaxations. A compact formulation may permit fractional configurations with objective values far removed from every integral solution. Stronger inequalities, alternative variables, or higher-dimensional formulations alter the relaxed polyhedron without changing the represented discrete problem.
Role in exact algorithms
In branch and bound, the linear programming relaxation is solved at nodes of a search tree. Its objective value bounds every integer solution in the corresponding subproblem. A node is discarded when its bound cannot improve the incumbent integer solution, when its relaxation is infeasible, or when its relaxed optimum is already integral.
A. H. Land and Alison Doig incorporated linear programming bounds into a general discrete programming enumeration method in 1960. Their framework established the principal relation between relaxation bounds and systematic branching that underlies modern mixed-integer optimization.
Cutting-plane methods strengthen a relaxation by adding inequalities valid for every integer-feasible point but violated by a current fractional solution. Ralph Gomory derived systematic cuts from simplex tableaux, thereby linking the arithmetic structure of integer variables to successive polyhedral refinements. Contemporary branch-and-cut algorithms combine these refinements with branch-and-bound search.
The relaxed solution also influences variable selection and heuristic construction within these algorithms. Fractional values identify decisions on which the continuous model remains unresolved, while reduced costs and dual variables quantify local objective sensitivity. These quantities belong to the relaxation and do not independently certify properties of the integer optimum.
Duality and interpretation
Because the relaxation is a linear program, it has an associated dual problem. Under the hypotheses of strong duality, the primal and dual relaxed optima are equal. A dual-feasible solution therefore provides an independently verifiable objective bound for the original integer problem in the appropriate direction.
Dual variables can be interpreted as marginal values for relaxed constraints, but this interpretation concerns continuous perturbations. Discrete changes may produce discontinuous effects that are not represented by local dual sensitivity. The distinction reflects the replacement of a lattice-constrained feasible set by a convex polyhedron.
Linear programming relaxation is related to Lagrangian relaxation, although the two constructions modify different parts of a model. Linear programming relaxation usually removes integrality while retaining the linear constraints. Lagrangian relaxation transfers selected constraints into the objective through multipliers, often leaving a simpler discrete subproblem. Under suitable formulations, the bounds from these relaxations can be compared through duality.