线性规划的松弛

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

A (general) integer program and its LP-relaxation

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

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

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

例子

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

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

 

(即只允许指定的指示变量值)并且,对于每个并集F的元素ej

 

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

 

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

对精确解的分支定界

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

割平面方法

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

参考文献