Branch and Cut、Branch and Price、Lagrange Relaxation求解TSP
Branch and Cut、Branch and Price、Lagrange Relaxation求解TSP
在boss的吩咐下，小编在这几天恶补了Branch and Cut、Branch and Price、Lagrange Relaxation这三个算法（其中Branch and Cut、Branch and Price是精确算法，Lagrange Relaxation可以用于求下界），并拜读了西北工业大学薛力教授使用这些算法编写的求解TSP的教学代码。看完后感觉受益匪浅（怀疑人生），所以写成推文，在整理学习成果的同时，也希望对大家有所帮助。
（本文的参考文献都会在文末给出）
01
Branch and Cut
Branch and Cut和Branch and Bound都是以分支定界算法（Branch and Bound）为基础的。这部分知识还没有掌握的小伙伴可以先去看看下面这几篇介绍分支定界算法的推文：
干货 | 10分钟带你全面掌握branch and bound（分支定界）算法-概念篇
干货 | 10分钟搞懂branch and bound算法的代码实现附带java代码
干货 | 10分钟教你用branch and bound（分支定界）算法求解TSP旅行商问题
Branch and Cut是一种用于求解整数线性规划（ILP）的组合优化方法，即线性规划（LP）问题，其中部分或全部未知数限制为整数值。Branch and Cut涉及Branch and Bound算法，并使用切割平面来收紧线性规划松弛。
对Branch and Cut算法的详细介绍请参考以下这篇推文，小编在这里就不再赘述。
干货 | 10分钟掌握branch and cut算法原理附带C++求解TSP问题代码
下面我们就直接来看Branch and Cut实际求解TSP时的详细过程。
大家对于Traveling-Salesman Problem，想必都已经非常熟悉了。小编认为，求解TSP，最大的难点之一就在于对子环的处理。
子环（subtour）：没有包含所有节点的一条闭环。子环首先是一个封闭的环；其次，这个环中被访问的节点集合是所有节点集合的一个真子集。这就导致与TSP想要得到的单环解矛盾，如下图所示的情况。
在模型中，是用来消除子环的约束。其中表示任意一个点的子集集合中点的个数大于等于2个，小于CityNum个）。上式中和在集合中遍历。表示对应子图中边的数量。当该子图构成一个环时，边的个数等于点的个数。因此，添加该约束能够保证任意子图不存在子环，从而保证所有点形成一个连通块。
但是，这个约束带来的缺陷是，随着数据规模增大会导致的规模呈指数级上升，且在程序中不易进行表示。
在Branch and Cut算法中，在一开始并没有考虑这一条约束，即先用下面这个模型进行分支定界，
求解0-1整数规划模型的LP松弛模型得到的非整数解作为下界（最小化问题），而此前找到的0-1整数解作为上界。在求解整数规划模型的LP松弛时，如果在解中找到违背上述子环约束的情况，则添加valid inequalities以排除这种不可行的情况。此时，这个valid inequalities起到了tighten LP relaxations的作用，即是我们所说的cut。这时，Branch and Bound就变成了Branch and Cut。
在求解LP松弛时，加入Cut，缩小解空间，同时又不影响整数解的解空间，可使解收敛得更快，效率更高。具体过程如下图所示：
了解了Branch and Cut的流程后
我们就可以学习一下如何写代码啦~
很多小细节也只有在编写代码的时候才会显现出来
02
Branch and Price
简单来说，Branch and Price算法就是Branch and Bound和Column Generation的结合体。所以在学习分支定价算法前，需要的同学可以先回顾以下介绍列成生推文：
干货 | 10分钟带你彻底了解Column Generation（列生成）算法的原理附java代码
运筹学教学|列生成（Column Generation）算法（附代码及详细注释）
干货 | 从下料问题看整数规划中的列生成方法(Python2.7调用gurobi进行求解，附代码)
下面我们详细讲讲用Branch and Price算法求解TSP的具体过程（只是示例，经典Branch-and-Price其实并不适合TSP）。
干货 | 10分钟带你掌握branch and price（分支定价）算法超详细原理解析
分支定价求解TSP
1 在Branch and Cut算法中，我们使用的是这个模型：
但是对于一般问题而言，如果要用列生成求解，一般需要重新建模成set covering model或者set partition model，对于TSP来说就是如下模型。建模成set partition model以后的问题就是master problem了。
其中，为可行路径集，表示路径 被选中 (= 1) 或没有被选中 (= 0) 。例如当=4时：
如果我们用Branch and Bound算法来求解的话，集合的规模会随着city的数量n的增加呈指数级增长。因此，这会导致评估搜索树节点的线性规划包含太多的变量而无法求解。想到这里我们会很容易地考虑到，可以使用列生成技术进行处理，从而将Branch and Bound转换为Branch and Price。
2 MP的线性松弛模型（LMP）如下。
3 把上述问题限制（restrict）到一个规模更小（即变量数比原问题少的）的问题P，用单纯形法求解P的最优解，此时求得了受限的松弛问题（线性规划) 的最优解。如果是Branch and Bound算法，这时就已经完成了Bound操作了，但对于Branch and Price算法来说，因为是受限的问题，所以需要证明此时已经不存在reduced cost<0的解，才能得到一个lower bound。否则，就需要求解Pricing Problem，并将reduced cost<0的列加入到集合中，即列生成。具体流程如下图：
4 对于TSP，Pricing Problem如下。
其中π通过求解RLMP对偶问题得到，在此不再赘述。
Pricing Problem可以看成最短路问题，通过label setting算法求解，有困惑的小伙伴可以参考以下推文：
标号法(label-setting algorithm)求解带时间窗的最短路问题
定价子问题要做的就是找一条路使得reduced cost<0，并将找到的列加入到RLMP中。
子节点的RMP重新添加column，再次求解的过程就是节点的Bound操作了。之后根据求得的解是否满足0-1整数规划进而分支或剪支的操作，和Branch and Bound差不多，考虑到篇幅问题，小编就直接贴上一张bp算法的流程图供大家参考：
跟Branch and Cut算法相比
Branch and Price算法涉及到的基础知识更多
也有很多细节需要注意
没看太懂的小伙伴可以多看几遍
或者自己去找些更详细的资料来看看~
（参考文献在文末给出）
03
Lagrange Relaxation
终于！到我们的拉格朗日松弛算法了！
别看这名字听着就挺高大上挺难的
实际上它也的确充满了智慧
不过在小编看来比Branch and Price算法要容易一点点
（小编菜得安详了...）
与前面两个精确算法不同，Lagrange Relaxation在TPS中只是用于快速求解IP问题，得到lower bound。当遇到一些很难求解的模型，但又不需要去求解它的精确解，只需要给出一个次优解或者解的上下界，这时便可以考虑采用松弛模型的方法加以求解。
对于一个整数规划问题，拉格朗日松弛放松模型中的部分约束。这些被松弛的约束并不是被完全去掉，而是利用拉格朗日乘子在目标函数上增加相应的惩罚项，对不满足这些约束条件的解进行惩罚。
拉格朗日松弛通过将困难约束放入目标函数，将其转换为一个简单问题，有时甚至可以得到比线性松弛更好的上下界。通过次梯度法求解，就可以得到一个lower bound 。
对于拉格朗日松弛，下面这篇推文介绍得挺详细的了，小编这就安利给大家~
下图是Lagrange Relaxation的具体流程
下面我们来讲讲如何将Lagrange Relaxation运用到TSP求解中。
如上图，我们将第一条约束作为惩罚项放入目标函数中，其中π是拉格朗日乘子（刚刚提到的推文中有介绍），这样就简化了问题。
其实简单来说，拉格朗日松弛用于求解TSP就是改进了LB的求法。
除此之外，代码还涉及到了1-tree的相关知识。熟悉TSP的小伙伴应该都知道，TSP的可行解是1-tree的一种，因此最小权值1-tree (minimum weight 1-tree)可以作为TSP的一个下界，因此可以利用这个性质来作为定界的标准。minimum weight 1-tree作为最小生成树的变体，可以通过在顶点集{2，…，n}上构造一棵最小生成树，然后在顶点1处邻接两条最小权值的边来构造。而Minimal 1-tree problem 可以有效地被Spanning tree greedy algorithm求解。对这一部分有疑问的小伙伴可以参考一下这篇推文：
对比实验
学了那么久的理论
当然要用一下啦~
下面我们就来对比一下以上的算法求解TSP的效果如何。但是在这里我们没有用Branch and Price来解TSP，因为经典Branch and Price其实并不适合求解TSP，相当于把一个最短路问题转换为了另一个最短路问题，但是对于VRP就不一样了。我们用TSP来做示例，是因为TSP比较简单，好理解。所以小编就对比了Branch and Cut和Lagrange Relaxation求解同一算例的运行时间。如下图：
整体来看，两种算法求解所需时间都随着数据规模的增大而增加。可以发现，Lagrange Relaxation的求解速度基本上要快于Branch and Cut，且随着数据规模的增加，差距越来越明显。
总 结
最后，我们对以上三种算法做个清楚明了的总结：
算法 | 算法结构 | 主问题 | 子问题 |
|---|---|---|---|
Branch-and-Cut | 利用一些可行解必须满足的条件构建Cut -> 提高 LB | LP （线性松弛） | Separation of inequalities 快速寻找cut |
Lagrange Relaxation | 将困难约束放入目标函数 -> 转换为一个简单问题 Sub-gradient method -> 得到一个LB | MIP （整数规划） | 快速求解松弛后的 简单IP问题 |
Branch-and-Price | 利用解的特殊结构构建一个更好的LB结构 | LP （线性松弛） | Column Generation 求解LB |
呼~推文到这里差不多就要结束啦。
实不相瞒，这几天小编真的被这些算法和代码折磨得怀疑人生了，也让小编意识到，自己在运筹优化的学习方面还有漫漫长路需要跋山涉水前行。不过高压之下带来的收获也颇多，总之大家和小编就一起努力吧！
欲下载本文相关代码，请移步留言区
「参考文献」
1. "A Branch-and-cut Algorithm for the Two-echelon Capacitated Vehicle Routing Problem with Grouping Constraints", Tian Liu, Zhixing Luo*, Hu Qin and Andrew Lim, European Journal of Operational Research, Volume 266, Issue 2, 16 April 2018, Pages 487-497.
2. "The Traveling-Salesman Problem and Minimum Spanning Trees" , Michael Held and Richard M. Karp,[J] Operations Research, Volume 18, November - December 1970, Pages 1138-1162.
3. "A Tutorial on Column Generation and Branch-and-price for Vehicle Routing Problems", D Feillet, 4OR, 4 August 2010 , Pages 407-424.
4. "Branch-price-and-cut for vehicle routing", Desaulniers G, 2014.
- END -
文案：胡心瑶（华中科技大学管理学院本科二年级）
指导老师：秦虎老师（华中科技大学管理学院）
排版：程欣悦（荆楚理工学院本科四年级）
审稿：周航（华中科技大学管理学院本科二年级）
如对文中内容有疑问，欢迎交流。PS：部分资料来自网络。
如有需求，可以联系：
秦虎老师（华中科技大学管理学院：tigerqin1980@qq.com）
胡心瑶（华中科技大学管理学院本科二年级：1603945923@qq.com）
程欣悦（荆楚理工学院本科四年级：1293900389@qq.com）