Linear programming relaxation

A linear program derived from a harder optimization problem by weakening constraints, often replacing integer restrictions with continuous ones. Its feasible region contains the original feasible solutions.

Integer programming: Optimization over variables constrained to take integer values. Its discrete feasible solutions are retained when integrality is removed to form a relaxation.
Linear inequality: An inequality in which variables appear only to the first power and are not multiplied together. Linear inequalities define the constraints retained or weakened in the relaxation.
Branch and bound: An optimization method that partitions a problem into subproblems and prunes them using bounds. LP relaxation values provide bounds used to prune integer-programming search nodes.
Lagrangian relaxation: An optimization technique that moves selected constraints into the objective using penalty multipliers. It weakens constraints through penalties rather than necessarily producing a linear program.
Linear programming: Optimization of a linear objective subject to linear constraints and variable bounds. The relaxation is solved as an ordinary linear program.
Objective function: A function whose value an optimization problem seeks to minimize or maximize. The same objective is usually optimized before and after relaxing constraints.
Branch and cut: An integer-programming method combining branching with added valid inequalities. It begins with LP bounds and tightens relaxations using cuts.
Semidefinite programming relaxation: A convex relaxation that replaces a difficult problem with optimization over positive semidefinite matrices. It can provide stronger bounds than an LP relaxation at greater computational cost.
Feasible region: The set of points satisfying all constraints of an optimization problem. A relaxation enlarges this set while preserving the original feasible points.
Convex hull: The smallest convex set containing a given set of points. The integer solutions' convex hull clarifies how closely a relaxation captures them.

Linked from 7 pages