Skip to main content

For questions relating to the relaxation of linear integer or mixed-integer-linear programming (MILP) problems where the integer constraints are removed.

For Mixed Integer Linear Programming (MILP) models, a Linear Programming (LP) Relaxation removes the integer constraints on the decision (& auxiliary) variables. This permits using traditional LP solver techniques (e.g. simplex) to solve the relaxed problem.

If the MILP problem was a minimization problem, the optimal solution (indeed, every feasible solution) to the LP relaxation provides a lower bound on the optimal solution to the MILP problem.

The tightness (closeness) of this bound is a subject of great interest and applicability for both practitioners and theoreticians in optimization.

Learn more:

[1] Integer Programming by Lawrence Wolsey

[2] LP Relaxation Wiki