Linear Relaxation

　　线性松弛是指将(混合)整数线性规划问题中的整数约束去掉。例如,在0-1整数规划中，所有的约束的形式为\[x_i\subset\{0,1\}\] 　　则原问题的线性送至为一系列线性约束：\[0 \leq x_i \leq1\] 　　松弛后的结果为线性规划。该方法将一个NP-hard最优化问题(整数规划问题)转换成一个相关联的可在多项式时间解决的问题(线性规划问题)。