离散优化模型的松弛模型

在分支定界算法中（常用来求解离散优化问题），我们求节点问题的最优界时，往往需要求解节点问题的松弛问题的最优解，那么这个所谓的松弛问题是什么呢？

顾名思义，就是将原问题的部分约束条件进行丢弃或放宽，而对离散优化模型而言，口头上的松弛问题常常指的是线性松弛问题，即将整数规划问题中的约束条件中的整数要求放宽，整数变量改为实数变量，将原整数规划问题转化为一个线性规划问题。

$$\begin{gathered} \min cx \\ s.t.Ax=b \\ x\in Z\to R \end{gathered}$$

此时的松弛问题的可行解集虽然扩大了，但包含了原问题中的所有的可行解，因此也包含了原问题的最优解，此时松弛问题的最优解不会比原问题的最优解更差，此时其就作为原问题的一个最优界。假若松弛问题的最优界同时满足原问题已被松弛掉的约束（即整数解要求），则松弛问题的最优界同时为原问题的最优解。

同时我们可以发现，松弛问题是原问题的一个更有可能找到更优解的问题，因此，如果松弛问题不可行，或者松弛问题的最优解不能令人满意，那原问题也将不可行，或者得到的解不会比松弛问题更令人满意（这也是B&B当中的减支逻辑）。

相对于整数规划而言，线性规划的求解复杂度大大降低，由于其可行域的凸性，使得问题的最优解一定在可行域边界上，这节省了大量的内部搜索，或者说从内部开始的算法会非常快地逼近最优解（内点法）。