标签：#松弛方法

线性规划的松弛

and its LP-relaxation]] 在数学中，0-1整数规划的线性规划的松弛是这样的问题：把每个变量必须为0或1的约束，替换为较弱的每个变量属于区间[0,1]的约束。 也就是说，对于原整数规划的每个下列形式的约束： :x_i\in\{0,1\} 我们转而使用一对线性约束来代替： :0 \le x_i \le 1. 这样产生的松弛是线性规划，因此得名线性规划的松弛。这种松弛技术把NP难的最优化问题（整数规划）转化为一个相关的多…