线性规划的松弛

在数学中，的线性规划的松弛是这样的问题：把每个变量必须为0或1的约束，替换为较弱的每个变量属于区间[0,1]的约束。 也就是说，对于原整数规划的每个下列形式的约束： 我们转而使用一对线性约束来代替： 这样产生的松弛是线性规划，因此得名线性规划的松弛。这种把NP难的最优化问题（整数规划）转化为一个相关的多项式时间可解的问题（线性规划）。我们可以用松弛后的线性规划的解来获得关于原整数规划的解的信息。