首页 / 算法 / 干货 | 10分钟掌握branch and cut（分支剪界）算法原理附带C++求解TSP问题代码

干货 | 10分钟掌握branch and cut（分支剪界）算法原理附带C++求解TSP问题代码

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了干货 | 10分钟掌握branch and cut（分支剪界）算法原理附带C++求解TSP问题代码，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6003字，纯文字阅读大概需要9分钟。

内容图文

00 前言

branch and cut其实还是和branch and bound脱离不了干系的。所以，在开始本节的学习之前，请大家还是要务必掌握branch and bound算法的原理。

01 应用背景

Branch and cut is a method of combinatorial optimization for solving integer linear programs (ILPs), that is, linear programming (LP) problems where some or all the unknowns are restricted to integer values. Branch and cut involves running a branch and bound algorithm and using cutting planes to tighten the linear programming relaxations. Note that if cuts are only used to tighten the initial LP relaxation, the algorithm is called cut and branch.[1]

02 总体描述

前面说过，branch and cut其实还是和branch and bound脱离不了干系。其实是有很大干系的。在应用branch and bound求解整数规划问题的时候，如下图（好好复习一下该过程）：

干货 | 10分钟掌握branch and cut（分支剪界）算法原理附带C++求解TSP问题代码 - 文章图片

假如，我们现在求一个整数规划最大化问题，在分支定界过程中，求解整数规划模型的LP松弛模型得到的非整数解作为上界，而此前找到的整数解作为下界。 如果出现某个节点upper bound低于现有的lower bound，则可以剪掉该节点。否则，如果不是整数解继续分支。

此外，在求解整数规划模型的LP松弛时，If cutting planes are used to tighten LP relaxations。那么这时候的branch and bound就变成了branch and cut。

那么，什么是cutting planes呢？如下图：
干货 | 10分钟掌握branch and cut（分支剪界）算法原理附带C++求解TSP问题代码 - 文章图片

红色部分是整数规划的可行解空间。
蓝色部分是整数规划的LP松弛可行解空间。
在求解LP松弛时，加入橙色的cut，缩小解空间，同时又不影响整数解的解空间，可使解收敛得更快。

这就是branch and cut的过程了。比branch and bound高明之处就在于多了一个cutting planes，可能使branch and bound的效率变得更高。

03 举个例子

为了让大家更好了解到branch and cut的精髓，必须得举一个简单的例子。对于同一个问题：
干货 | 10分钟掌握branch and cut（分支剪界）算法原理附带C++求解TSP问题代码 - 文章图片

branch and cut（左）和branch and bound（右）求解过程如下：

干货 | 10分钟掌握branch and cut（分支剪界）算法原理附带C++求解TSP问题代码 - 文章图片

可以看到，两者的不同之处就在子问题P2的处理上。

  • 对于branch and bound来说，求解线性松弛得到的Z = -29.5 < Z = -28。可知该支是可能隐含有更优解的，于是二话不说分支。无奈，分了两支以后发现居然没更优解，这种付出了却没有回报的感觉就像是受到了欺骗一样。

  • 对于branch and cut来说，在求解线性松弛得到的Z = -29.5 < Z = -28时，并没有被兴奋冲昏头脑，它尝试着在线性松弛的解空间上砍下一块，但又不能影响到整数解的解空间范围。琢磨半天终于找到一块能砍的，于是Add cut: 2x1 + x2 <= 7。砍下来以后，形成新的子问题P3，赶紧看看P3的最优解是多少。在P3中，Z=-27.8 > -28，握草，这一支果然不可取。

从上面的算法过程我们可以看到，求解同一个问题，branch and cut只用了3步，而branch and bound却用了4步。

There are many methods to solve the mixed-integer linear programming. Gomory Cutting Planes is fast, but unreliable. Branch and Bound is reliable but slow. The Branch and cut combine the advantages from these two methods and improve the defects. It has proven to be a very successful approach for solving a wide variety of integer programming problems. We can solve the MILP by taking some cutting planes before apply whole system to the branch and bound, Branch and cut is not only reliable, but faster than branch and bound alone. Finally, we understand that using branch and cut is more efficient than using branch and bound.[2]

04 算法过程

关于branch and cut的过程，可以总结如下：[1]
干货 | 10分钟掌握branch and cut（分支剪界）算法原理附带C++求解TSP问题代码 - 文章图片

相比branch and bound，其多了一个Cutting Planes的过程，先用Cutting Planes tighten LP relaxations，然后求解LP relaxations再判断是否有分支的必要。

其伪代码如下：
C++ // ILP branch and cut solution pseudocode, assuming objective is to be maximized ILP_solution branch_and_cut_ILP(IntegerLinearProgram initial_problem) { queue active_list; // L, above active_list.enqueue(initial_problem); // step 1 // step 2 ILP_solution optimal_solution; // this will hold x* above double best_objective = -std::numeric_limits<double>::infinity; // will hold v* above while (!active_list.empty()) { // step 3 above LinearProgram& curr_prob = active_list.dequeue(); // step 3.1 do { // steps 3.2-3.7 RelaxedLinearProgram& relaxed_prob = LP_relax(curr_prob); // step 3.2 LP_solution curr_relaxed_soln = LP_solve(relaxed_prob); // this is x above bool cutting_planes_found = false; if (!curr_relaxed_soln.is_feasible()) { // step 3.3 continue; // try another solution; continues at step 3 } double current_objective_value = curr_relaxed_soln.value(); // v above if (current_objective_value <= best_objective) { // step 3.4 continue; // try another solution; continues at step 3 } if (curr_relaxed_soln.is_integer()) { // step 3.5 best_objective = current_objective_value; optimal_solution = cast_as_ILP_solution(curr_relaxed_soln); continue; // continues at step 3 } // current relaxed solution isn't integral if (hunting_for_cutting_planes) { // step 3.6 violated_cutting_planes = search_for_violated_cutting_planes(curr_relaxed_soln); if (!violated_cutting_planes.empty()) { // step 3.6 cutting_planes_found = true; // will continue at step 3.2 for (auto&& cutting_plane : violated_cutting_planes) { active_list.enqueue(LP_relax(curr_prob, cutting_plane)); } continue; // continues at step 3.2 } } // step 3.7: either violated cutting planes not found, or we weren't looking for them auto&& branched_problems = branch_partition(curr_prob); for (auto&& branch : branched_problems) { active_list.enqueue(branch); } continue; // continues at step 3 } while (hunting_for_cutting_planes /* parameter of the algorithm; see 3.6 */ && cutting_planes_found); // end step 3.2 do-while loop } // end step 3 while loop return optimal_solution; // step 4 }

相关代码

关于branch and cut 求解TSP问题的代码，请关注公众号【程序猿声】，在后台回复【bctsp】不包括【】即可获取。
干货 | 10分钟掌握branch and cut（分支剪界）算法原理附带C++求解TSP问题代码 - 文章图片

reference

内容总结

以上是互联网集市为您收集整理的干货 | 10分钟掌握branch and cut（分支剪界）算法原理附带C++求解TSP问题代码全部内容，希望文章能够帮你解决干货 | 10分钟掌握branch and cut（分支剪界）算法原理附带C++求解TSP问题代码所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/737435.html

来源：【匿名】