Linear programming relaxation

In mathematics, the linear programming relaxation of a 0-1 integer program is the problem that arises by replacing the constraint that each variable must be 0 or 1 by a weaker constraint, that each variable belong to the interval [0,1].

That is, for each constraint of the form

${\displaystyle x_{i}\in \{0,1\}}$

of the original integer program, one instead uses a pair of linear constraints

${\displaystyle 0\leq x_{i}\leq 1.}$

The resulting relaxation is a linear program, hence the name. This relaxation technique transforms an NP-hard optimization problem (integer programming) into a related problem that is solvable in polynomial time (linear programming); the solution to the relaxed linear program can be used to gain information about the solution to the original integer program.

Example

Consider the set cover problem, the linear programming relaxation of which was first considered by Lovász (1975). In this problem, one is given as input a family of sets F = {S₀, S₁, ...}; the task is to find a subfamily, with as few sets as possible, having the same union as F.

To formulate this as a 0-1 integer program, form an indicator variable x_i for each set S_i, that takes the value 1 when S_i belongs to the chosen subfamily and 0 when it does not. Then a valid cover can be described by an assignment of values to the indicator variables satisfying the constraints

${\displaystyle \textstyle x_{i}\in \{0,1\}}$ 

(that is, only the specified indicator variable values are allowed) and, for each element e_j of the union of F,

${\displaystyle \textstyle \sum _{\{i\mid e_{j}\in S_{i}\}}x_{i}\geq 1}$ 

(that is, each element is covered). The minimum set cover corresponds to the assignment of indicator variables satisfying these constraints and minimizing the linear objective function

${\displaystyle \textstyle \min \sum _{i}x_{i}.}$ 

The linear programming relaxation of the set cover problem describes a fractional cover in which the input sets are assigned weights such that the total weight of the sets containing each element is at least one and the total weight of all sets is minimized.

As a specific example of the set cover problem, consider the instance F = {{a, b}, {b, c}, {a, c}}. There are three optimal set covers, each of which includes two of the three given sets. Thus, the optimal value of the objective function of the corresponding 0-1 integer program is 2, the number of sets in the optimal covers. However, there is a fractional solution in which each set is assigned the weight 1/2, and for which the total value of the objective function is 3/2. Thus, in this example, the linear programming relaxation has a value differing from that of the unrelaxed 0-1 integer program.

Solution quality of relaxed and original programs

The LP-relaxation of an integer program may be solved using any standard linear programming technique. If the optimal solution to the linear program happens to have all variables either 0 or 1, it will also be an optimal solution to the original integer program. However, this is generally not true, except for some special cases (e.g., problems with totally unimodular matrix specifications.)

In all cases, though, the solution quality of the linear program is at least as good as that of the integer program, because any integer program solution would also be a valid linear program solution. That is, in a maximization problem, the relaxed program has a value greater than or equal to that of the original program, while in a minimization problem such as the set cover problem the relaxed program has a value smaller than or equal to that of the original program. Thus, the relaxation provides a bound on the integer program's solution quality.

In the example instance of the set cover problem described above, in which the relaxation has an optimal solution value of 3/2, we can deduce that the optimal solution value of the unrelaxed integer program is at least as large. Since the set cover problem has solution values that are integers (the numbers of sets chosen in the subfamily), the optimal solution quality must be at least as large as the next larger integer, 2. Thus, in this instance, despite having a different value from the unrelaxed problem, the linear programming relaxation gives us a tight lower bound on the solution quality of the original problem.

Approximation and integrality gap

LP relaxation is a standard technique for designing approximation algorithms for hard optimization problems. In this application, an important concept is the integrality gap, the maximum ratio between the solution quality of the integer program and its relaxation. Typically, this gap translates into the approximation ratio of an approximation algorithm.

For the set cover problem, Lovász proved that the integrality gap for an instance with n elements is H_n, the nth harmonic number. This matches the approximation ratio of the greedy algorithm for approximating the optimal set cover, by repeatedly selecting the set that covers the largest possible number of remaining uncovered elements. There are strong complexity-theoretic reasons for believing that no polynomial time approximation algorithm can achieve a significantly better approximation ratio than the integrality gap for this problem (Feige 1996).

Branch and bound

If some variables in the optimal solution have fractional values, we may start a branch and bound type process, in which we recursively solve subproblems in which some of the fractional variables have their values fixed to either zero or one.

For any subproblem in this process, the LP relaxation provides a valid bound on the solution quality of the optimal integer solution. Therefore, if a subproblem's LP relaxation has a solution quality that is not better than the best integer solution found so far, that branch of the search may be pruned without further searching.

References

• Agmon, Shmuel (1954), "The relaxation method for linear inequalities", Canadian Journal of Mathematics, 6: 382–392.
• Feige, U. (1996), "A threshhold of ln n for approximating set cover", Proc. 28th ACM Symp. Theory of Computing (STOC), pp. 312–318.
• Lovász, Lászlo (1975), "On the ratio of optimal integral and fractional covers", Discrete Mathematics, 13: 383–390, doi:10.1016/0012-365X(75)90058-8.
• Motzkin, TS (1954), "The relaxation method for linear inequalities", Canadian Journal of Mathematics, 6: 393–404 {{citation}}: Unknown parameter |coauthors= ignored (|author= suggested) (help).