本文主要是介绍离散优化模型的松弛模型，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
在分支定界算法中（常用来求解离散优化问题），我们求节点问题的最优界时，往往需要求解节点问题的松弛问题的最优解，那么这个所谓的松弛问题是什么呢？
顾名思义，就是将原问题的部分约束条件进行丢弃或放宽，而对离散优化模型而言，口头上的松弛问题常常指的是线性松弛问题，即将整数规划问题中的约束条件中的整数要求放宽，整数变量改为实数变量，将原整数规划问题转化为一个线性规划问题。
min c x s . t . A x = b x ∈ Z → R \min cx\\s.t. Ax=b\\ x\in Z\rightarrow R mincxs.t.Ax=bx∈Z→R
此时的松弛问题的可行解集虽然扩大了，但包含了原问题中的所有的可行解，因此也包含了原问题的最优解，此时松弛问题的最优解不会比原问题的最优解更差，此时其就作为原问题的一个最优界。假若松弛问题的最优界同时满足原问题已被松弛掉的约束（即整数解要求），则松弛问题的最优界同时为原问题的最优解。
同时我们可以发现，松弛问题是原问题的一个更有可能找到更优解的问题，因此，如果松弛问题不可行，或者松弛问题的最优解不能令人满意，那原问题也将不可行，或者得到的解不会比松弛问题更令人满意（这也是B&B当中的减支逻辑）。
相对于整数规划而言，线性规划的求解复杂度大大降低，由于其可行域的凸性，使得问题的最优解一定在可行域边界上，这节省了大量的内部搜索，或者说从内部开始的算法会非常快地逼近最优解（内点法）。
这篇关于离散优化模型的松弛模型的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
