LP Relaxation

The LP relaxation drops integrality from an integer program, yielding a tractable linear program whose optimum bounds the true integer optimum.

What relaxation means

Given an integer program, the LP relaxation is obtained by replacing every integrality requirement x integer with the interval x in [lower, upper], leaving all linear constraints intact. The result is an ordinary linear program that can be solved efficiently. Because the relaxed feasible set contains the integer feasible set, its optimum is at least as good as the integer optimum.

A bound, and sometimes an answer

For a minimization, the relaxation gives a valid lower bound: the true integer optimum can be no smaller. This bound is exactly what branch and bound needs to prune. Occasionally the relaxation returns an all-integer solution by itself, in which case it is optimal for the integer problem. Certain constraint matrices, called totally unimodular, guarantee integer LP vertices, so their relaxations are always exact; network-flow and assignment problems have this property.

The integrality gap

The distance between the relaxed optimum and the integer optimum is the integrality gap. A small gap means the relaxation is a faithful proxy and branch and bound will prune heavily; a large gap means many branching steps are needed. Tightening the relaxation, by adding valid cutting planes or by reformulating with auxiliary variables, shrinks the gap and is often the single most effective way to speed up an integer solver.

from scipy.optimize import linprog

# max 5x + 4y  s.t. 6x+4y<=24, x+2y<=6, x,y>=0, integer
# LP relaxation ignores integrality:
res = linprog(c=[-5,-4], A_ub=[[6,4],[1,2]], b_ub=[24,6],
              bounds=[(0,None),(0,None)])
print(-res.fun, res.x)  # relaxed optimum >= integer optimum

Why it is central

Nearly every practical method for integer and mixed-integer programming is built on repeatedly solving LP relaxations: at the root to get an initial bound, and at each node of the search tree. The quality of the relaxation, not the raw problem size, usually determines how quickly an integer program is solved.