LPrelaxation

LP relaxation is a technique in mathematical optimization where an integer programming problem is transformed into a linear program by relaxing integrality constraints. Given an optimization problem such as maximize c^T x subject to Ax ≤ b with x constrained to take integer values, the LP relaxation replaces x with real variables, yielding maximize c^T x subject to Ax ≤ b and x ∈ R^n. The feasible region becomes a polyhedron and the problem can be solved in polynomial time by standard LP methods.

The primary purpose of an LP relaxation is to obtain bounds on the original problem. For a maximization problem, the optimal value of the relaxation is an upper bound; for a minimization problem, it is a lower bound. If the LP optimum happens to be integral, it also solves the integer program. In many cases the LP relaxation provides a good guide to the structure of the optimal solution and can be used within exact algorithms such as branch-and-bound or branch-and-cut, where LP solutions are used to prune search branches or generate cutting planes that tighten the feasible region.

Common examples lie in combinatorial optimization, such as the 0-1 knapsack, vertex cover, or set cover problems. The LP relaxation often yields fractional solutions, highlighting integrality gaps between the relaxed and original problems. To improve the bound, one may add valid inequalities, use extended formulations, or apply column generation and cutting planes.

LP relaxation is a foundational tool in operations research and optimization, closely tied to duality, polyhedral theory, and efficient polynomial-time solvers.