线性规划的松弛

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，且所有集合的总权值最小。

对精确解的分支定界

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

割平面方法

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

参考文献

• Aardal, Karen; Weismantel, Robert, Polyhedral combinatorics: An annotated bibliography, Annotated Bibliographies in Combinatorial Optimization (PDF), Wiley, 1997 [2011-05-09], （原始内容 (PDF)存档于2016-03-03） .
• Agmon, Shmuel, The relaxation method for linear inequalities, Canadian Journal of Mathematics, 1954, 6: 382–392 [2011-05-09], （原始内容存档于2012-02-24） .
• 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 [2011-05-09], （原始内容存档于2012-02-24） .
• 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 .