线性规划的松弛

A (general) integer program and its LP-relaxation

在数学中，0-1整数规划的线性规划的松弛是这样的问题：把每个变量必须为0或1的约束，替换为较弱的每个变量属于区间[0,1]的约束。

也就是说，对于原整数规划的每个下列形式的约束：

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

我们转而使用一对线性约束来代替：

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

这样产生的松弛是线性规划，因此得名线性规划的松弛。这种松弛技术把NP难的最优化问题（整数规划）转化为一个相关的多项式时间可解的问题（线性规划）。我们可以用松弛后的线性规划的解来获得关于原整数规划的解的信息。

例子

考虑集覆盖问题，该问题的线性规划松弛最先由Lovász (1975)详细研究。在该问题中，给定输入为一族集合F = {S₀, S₁, ...}；任务是找到其中的一个集合数量尽可能少的子族，其并集也是F。

若想把该问题形式化为0-1整数规划，对每个集合S_i构造一个指示变量x_i，它取值为1当S_i属于所选子族时，取0当其不属于。那么一个有效的覆盖可由一个满足下列约束的对指示变量的赋值来描述：

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

（即只允许指定的指示变量值）并且，对于每个并集F的元素e_j：

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

（即覆盖每个元素）。最小的对应指示变量赋值的集覆盖满足这些约束且最小化线性目标函数：

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

这个集覆盖问题的线性规划松弛描述了一个分数覆盖，其中输入集被赋予权值，使得包含每个元素的这些集合的总权值至少是1，且所有集合的总权值最小。

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 linear programming 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

Linear programming 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 of 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. One can turn the linear programming relaxation for this problem into an approximate solution of the original unrelaxed set cover instance via the technique of randomized rounding （Raghavan & Tompson 1987）. Given a fractional cover, in which each set S_i has weight w_i, choose randomly the value of each 0-1 indicator variable x_i to be 1 with probability w_i ×(ln n +1), and 0 otherwise. Then any element e_j has probability less than 1/(e×n) of remaining uncovered, so with constant probability all elements are covered. The cover generated by this technique has total size, with high probability, (1+o(1))(ln n)W, where W is the total weight of the fractional solution. Thus, this technique leads to a randomized approximation algorithm that finds a set cover within a logarithmic factor of the optimum. As Young (1995) showed, both the random part of this algorithm and the need to construct an explicit solution to the linear programming relaxation may be eliminated using the method of conditional probabilities, leading to a deterministic greedy algorithm for set cover, known already to Lovász, that repeatedly selects the set that covers the largest possible number of remaining uncovered elements. This greedy algorithm approximates the set cover to within the same H_n factor that Lovász proved as the integrality gap for set cover. There are strong complexity-theoretic reasons for believing that no polynomial time approximation algorithm can achieve a significantly better approximation ratio （Feige 1998）.

Similar randomized rounding techniques, and derandomized approximation algorithms, may be used in conjunction with linear programming relaxation to develop approximation algorithms for many other problems, as described by Raghavan, Tompson, and Young.

对精确解的分支定界

在近似理论中，线性规划的松弛也有应用。线性规划在计算困难的最优化问题的最优解时的分支定界算法中也扮演着重要角色。

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. In each step of an algorithm of this type, we consider a subproblem of the original 0-1 integer program in which some of the variables have values assigned to them, either 0 or 1, and the remaining variables are still free to take on either value. In subproblem i, let V_i denote the set of remaining variables. The process begins by considering a subproblem in which no variable values have been assigned, and in which V₀ is the whole set of variables of the original problem. Then, for each subproblem i, it performs the following steps.

1. Compute the optimal solution to the linear programming relaxation of the current subproblem. That is, for each variable x_j in V_i, we replace the constraint that x_j be 0 or 1 by the relaxed constraint that it be in the interval [0,1]; however, variables that have already been assigned values are not relaxed.
2. If the current subproblem's relaxed solution is worse than the best integer solution found so far, backtrack from this branch of the recursive search.
3. If the relaxed solution has all variables set to 0 or 1, test it against the best integer solution found so far and keep whichever of the two solutions is best.
4. Otherwise, let x_j be any variable that is set to a fractional value in the relaxed solution. Form two subproblems, one in which x_j is set to 0 and the other in which x_j is set to 1; in both subproblems, the existing assignments of values to some of the variables are still used, so the set of remaining variables becomes V_i \ {x_j}. Recursively search both subproblems.

Although it is difficult to prove theoretical bounds on the performance of algorithms of this type, they can be very effective in practice.

割平面方法

两种有着相同的目标函数和相同的可行解集因而等价的整数规划，可能有着非常不一样的线性规划松弛：一种线性规划松弛可从几何上视为包含了所有可行解并排除了所有其余0-1向量的凸多面体，而且有无穷多的多面体都具有这种性质。理想情况下，我们想把可行解的凸包作为松弛来使用，因为这种多面体上的线性规划将自动产生原整数规划的正确解。尽管如此，一般情况下，这种多面体有指数多的面且难以构造。典型的松弛，比如我们前面讨论过的集覆盖问题的松弛，构造了一个严格包含可行解的凸包且排除可解非松弛问题的0-1向量的多面体。

The cutting-plane method for solving 0-1 integer programs, first introduced for the traveling salesman problem by Dantzig，Fulkerson & Johnson (1954) and generalized to other integer programs by Gomory (1958), takes advantage of this multiplicity of possible relaxations by finding a sequence of relaxations that more tightly constrain the solution space until eventually an integer solution is obtained. This method starts from any relaxation of the given program, and finds an optimal solution using a linear programming solver. If the solution assigns integer values to all variables, it is also the optimal solution to the unrelaxed problem. Otherwise, an additional linear constraint (a cutting plane or cut) is found that separates the resulting fractional solution from the convex hull of the integer solutions, and the method repeats on this new more tightly constrained problem.

Problem-specific methods are needed to find the cuts used by this method. It is especially desirable to find cutting planes that form facets of the convex hull of the integer solutions, as these planes are the ones that most tightly constrain the solution space; there always exists a cutting plane of this type that separates any fractional solution from the integer solutions. Much research has been performed on methods for finding these facets for different types of combinatorial optimization problems, under the framework of polyhedral combinatorics （Aardal & Weismantel 1997）.

The related branch and cut method combines the cutting plane and branch and bound methods. In any subproblem, it runs the cutting plane method until no more cutting planes can be found, and then branches on one of the remaining fractional variables.

参见

• Fractional coloring, a linear programming relaxation of graph coloring.
• Randomized rounding, for obtaining a solution to the original problem from a solution to the relaxation.

参考文献

• Aardal, Karen; Weismantel, Robert, Polyhedral combinatorics: An annotated bibliography, Annotated Bibliographies in Combinatorial Optimization (PDF), Wiley, 1997 .
• Agmon, Shmuel, The relaxation method for linear inequalities, Canadian Journal of Mathematics, 1954, 6: 382–392 .
• Dantzig, George; Fulkerson, D. R.; Johnson, Selmer, Solution of a large-scale traveling-salesman problem, Journal of the Operations Research Society of America, 1954, 2 (4): 393–410, doi:10.1287/opre.2.4.393 .
• Feige, Uriel, A threshold of ln n for approximating set cover, Journal of the ACM, 1998, 45 (4): 634–652, doi:10.1145/285055.285059 .
• Gomory, Ralph E., Outline of an algorithm for integer solutions to linear programs, Bulletin of the American Mathematical Society, 1958, 64: 275–278, doi:10.1090/S0002-9904-1958-10224-4 .
• Lovász, László, On the ratio of optimal integral and fractional covers, Discrete Mathematics, 1975, 13: 383–390, doi:10.1016/0012-365X(75)90058-8 .
• Motzkin, T. S.; Schoenberg, I. J., The relaxation method for linear inequalities, Canadian Journal of Mathematics, 1954, 6: 393–404 .
• Raghavan, Prabhakar; Thompson, Clark D., Randomized rounding: A technique for provably good algorithms and algorithmic proofs, Combinatorica, 1987, 7 (4): 365–374, doi:10.1007/BF02579324 .
• Young, Neal E., Randomized rounding without solving the linear program, Proc. 6th ACM-SIAM Symp. Discrete Algorithms (SODA): 170–178, 1995 .