分支与边界算法 - 10 分钟内掌握概念
前言
- New Arrival -
之前一直做启发式算法,最近突然对精确算法感兴趣了。但是这玩意儿说实话是真的难,刚好boss又叫我学学column generation求解VRP相关的内容。
一看里面有好多知识需要重新把握,所以这段 时间就打算好好学学精确算法。届时会把学习过程记录下来,也方便大家学习!
01 什么是branch and bound?
1.1 |
官方一点[1] |
---|
Branch and bound (BB, B&B, or BnB) is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root.
The algorithm explores branches of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm.
The algorithm depends on efficient estimation of the lower and upper bounds of regions/branches of the search space. If no bounds are available, the algorithm degenerates to an exhaustive search.
1.2 |
通俗一点 |
---|
分支定界算法始终围绕着一颗搜索树进行的,我们将原问题看作搜索树的根节点,从这里出发,分支的含义就是将大的问题分割成小的问题。
大问题可以看成是搜索树的父节点,那么从大问题分割出来的小问题就是父节点的子节点了。
分支的过程就是不断给树增加子节点的过程。而定界就是在分支的过程中检查子问题的上下界,如果子问题不能产生一比当前最优解还要优的解,那么砍掉这一支。直到所有子问题都不能产生一个更优的解时,算法结束。
02 原理解析
为了让大家更好理解分支定界的原理,这里小编举一个求解整数规划的例子来给大家演示分支定界算法的具体过程。
首先,对于一个整数规划模型:
因为求解的是最大化问题,我们不妨设当前的最优解BestV为-INF,表示负无穷。
1) 首先从主问题分出两支子问题:
通过线性松弛求得两个子问题的upper bound为Z_LP1 = 12.75,Z_LP2 = 12.2。由于Z_LP1 和Z_LP2都大于BestV=-INF,说明这两支有搞头。继续往下。
2) 从节点1和节点2两个子问题再次分支,得到如下结果:
子问题3已经不可行,无需再理。子问题4通过线性松弛得到最优解为10,刚好也符合原问题0的所有约束,在该支找到一个可行解,更新BestV = 10。
子问题5通过线性松弛得到upper bound为11.87>当前的BestV = 10,因此子问题5还有戏,待下一次分支。而子问题6得到upper bound为9<当前的BestV = 10,那么从该支下去找到的解也不会变得更好,所以剪掉!
3) 对节点5进行分支,得到:
子问题7不可行,无需再理。子问题8得到一个满足原问题0所有约束的解,但是目标值为4<当前的BestV=10,所以不更新BestV,同时该支下去也不能得到更好的解了。
4) 此时,所有的分支遍历都完成,我们最终找到了最优解。
03 算法框架
分支定界法(branch and bound)是一种求解整数规划问题的最常用算法。这种方法不但可以求解纯整数规划,还可以求解混合整数规划问题。
上面用了求解整数规划的例子,这虽然有助于我们更好理解这个算法,但是针对整数规划这一特定问题的过程描述,有可能会对我们的思维带来局限性。而不能更好的理解该算法的精髓。
所以小编决定,在这一节里面,将一个更通用的算法框架呈现出来,以便大家能更好的了解分支定界算法的真正精髓所在。
假设我们求的是最小化问题 minimize f(x)。branch and bound的过程可以描述如下:[1]
1. Using a heuristic, find a solution xh to the optimization problem. Store its value, B = f(x_h). (If no heuristic is available, set B to infinity.) B will denote the best solution found so far, and will be used as an upper bound on candidate solutions.
2. Initialize a queue to hold a partial solution with none of the variables of the problem assigned.
3. Loop until the queue is empty:
3.1. Take a node N off the queue. 3.2. If N represents a single candidate solution x and f(x) < B, then x is the best solution so far. Record it and set B ← f(x). 3.3. Else, branch on N to produce new nodes Ni. For each of these:
3.3.1. If bound(N_i) > B, do nothing; since the lower bound on this node is greater than the upper bound of the problem, it will never lead to the optimal solution, and can be discarded. 3.3.2. Else, store Ni on the queue.
其实代码该过程描述也很明了了。第1步可以用启发式找一个当前最优解B出来,如果不想也可以将B设置为正无穷。对于一个最小化问题而言,肯定是子问题的lower bound不能超过当前最优解,不然超过了,该子问题就需要剪掉了。
第2第3步主要是用队列取构建一个搜索树进行搜索,具体的搜索方式由queue这个数据结构决定的。
前面我们讲了,B&B是围绕着一颗搜索树进行的,那么对于一棵树而言就有很多种搜索方式:
Breadth-first search (BFS):广度优先搜索,就是横向搜索,先搜索同层的节点。再一层一层往下。这种搜索可以用FIFO queue实现。
Depth-first search (DFS):深度优先搜索,就是纵向搜索,先一个分支走到底,再跳到另一个分支走到底。这种搜索可以用LIFO queue也就是栈实现。
Best-First Search:最佳优先搜索,最佳优先搜索算法是一种启发式搜索算法(Heuristic Algorithm),其基于广度优先搜索算法,不同点是其依赖于估价函数对将要遍历的节点进行估价,选择代价小的节点进行遍历,直到找到目标点为止。这种搜索可以用优先队列priority queue来实现。
04 伪代码描述[1]
按照上述框架的过程,下面提供了一个很详细的C++伪代码:
// C++-like implementation of branch and bound, // assuming the objective function f is to be minimizedCombinatorialSolution branch_and_bound_solve( CombinatorialProblem problem, ObjectiveFunction objective_function /*f*/, BoundingFunction lower_bound_function /*g*/) { // Step 1 above double problem_upper_bound = std::numeric_limits<double>::infinity; // = B CombinatorialSolution heuristic_solution = heuristic_solve(problem); // x_h problem_upper_bound = objective_function(heuristic_solution); // B = f(x_h) CombinatorialSolution current_optimum = heuristic_solution; // Step 2 above queue<CandidateSolutionTree> candidate_queue; // problem-specific queue initialization candidate_queue = populate_candidates(problem); while (!candidate_queue.empty()) { // Step 3 above // Step 3.1 CandidateSolutionTree node = candidate_queue.pop(); // "node" represents N above if (node.represents_single_candidate()) { // Step 3.2 if (objective_function(node.candidate()) < problem_upper_bound) { current_optimum = node.candidate(); problem_upper_bound = objective_function(current_optimum); } // else, node is a single candidate which is not optimum } else { // Step 3.3: node represents a branch of candidate solutions // "child_branch" represents N_i above for (auto&& child_branch : node.candidate_nodes) { if (lower_bound_function(child_branch) <= problem_upper_bound) { candidate_queue.enqueue(child_branch); // Step 3.3.2 } // otherwise, g(N_i) > B so we prune the branch; step 3.3.1 } } } return current_optimum;}
有了伪代码加持,相信大家对上面的过程以及branch and bound 算法也有了一个透彻的了解。后面我们还会推出关于branch and bound的相关代码实现,包括各种数据结构实现的各种搜索方式等等,请关注我们的公众号以获取最新的
05 reference
[1] https://en.wikipedia.org/wiki/Branch_and_bound
[2] OR-Wayne Winston
END
上一篇: 整数编程的求解方法有哪些
下一篇: 整数编程算法设计与分析笔记
推荐阅读
-
[数学建模算法] (4) 整数程序设计的基本概念和常规算法:分支与边界法
-
分支与边界算法 - 10 分钟内掌握概念
-
干货|10 分钟掌握分支和价格(分支定价)算法超详细原理分析
-
反传销网8月30日发布:视频区块链里的骗子,币里的韭菜,杜子建骂人了!金融大V周召说区块链!——“一小帮骗子玩一大帮小白,被割韭菜,小白还轮流被割,割的就是你!” 什么区块链,统统是骗子 作者:周召(知乎金融领域大V,毕业于上海财经大学,目前任职上海某股权投资基金合伙人) 有人问我,区块链现在这么火,到底是不是骗局? 我的回答是: 是骗局。而且我并不是说数字货币是骗局,而是说所有搞区块链的都是骗局。 -01- 区块链是一种鸡肋技术 人类社会任何技术的发明应用,本质都是为了提高社会的生产效率。而所谓区块链技术本质不过是几种早已成熟的技术的大杂烩,冗余且十分低效,除了提高了洗钱和诈骗的效率以外,对人类社会的进步毫无贡献。 真正意义上的区块链得包含三个要素:分布式系统(包括记账和存储),无法篡改的数据结构,以及共识算法,三者互为基础和因果,就像三体世界一样。看上去挺让人不明觉厉的,而经过几年的瞎折腾,稍微懂点区块链的碰了几次壁后都已经渐渐明白区块链其实并没有什么卵用,区块链技术已经名存实亡,沦为了营销工具和传销组织的画皮。 因为符合上述定义的、以比特币为代表的原教旨区块链技术,是反效率的,从经济学角度来说,不但不是一种帕累托改进,甚至还可以说是一种帕累托倒退。 原教旨区块链技术的效率十分低下,因为要遍历所有节点,只能做非常轻量级的数据应用,一旦涉及到大量的数据传输与更新,区块链就瞎了。 一方面整条链交易速度会极慢,另一方面数据库容量极速膨胀,考虑到人手一份的存储机制,区块链其实是对存储资源和能源的一种极大的浪费。 这里还没有加上为了取得所谓的共识和挖矿消耗的巨大的能源,如果说区块链技术是屎,那么这波区块链投机浪潮可谓人类历史上最大规模的搅屎运动。 区块链也验证不了任何东西。 所谓的智能合约,即不智能,也非合约。我看有人还说,如果有了智能合约,就可以跟老板签一份放区块链上,如果明年销售业绩提升30%,就加薪10%,由于区块链不能篡改,不能抵赖,所以老板必须得执行,说得有板有眼,不懂行的愣一看,好像还真是那么回事。 但仔细一想,问题就来了。首先,在区块链上如何证明你真的达到了30%业绩提升?即便真的达到老板耍赖如何执行? 也就是说,如果区块链真这么厉害,要法院和仲裁干什么。 人类社会真正的符合成本效益原则的是代理制度。之前有人说要用区块链改造注册会计师行业,我不知道他准备怎么设计,我猜想他思路大概是这样的,首先肯定搞去中心化,让所有会计师到链上来,然后一个新人要成为注册会计师就要所有会计师同意并记录在链上。 那我就请问了,我每天上班累死累活,为什么还要花时间去验证一个跟我无关的的人的专业能力?最优做法当然是组织一个委员会,让专门的人来负责,这不就是现在注册会师协会干的事儿吗?区块链的逻辑相当于什么事情都要拿出来公投,这个绝对是扯淡的。 当然这么说都有点抬举区块链了,区块链技术本身根本没有判断是非能力,如果这么高级的人工智能,靠一个无脑分布式记账就能实现的话,我们早就进入共产主义社会了。 虽然EOS等数字货币采用了超级节点,通过再中心化的方式提高效率,有点行业协会的意思,是对区块链原教旨主义的一种修正,但是依然无法突破区块链技术最本质的局限性。有人说,私有链和联盟链是区块链技术的未来,也是扯淡,因为区块链技术没有未来。如果有,说明他是包装成区块链的伪区块链技术。 区块链所涉及的所有底层技术,不管是分布式数据库技术,加密技术,还是点对点传输技术等,基本都是早已存在没什么秘密可言的技术。 比特币系统最重要的特性是封闭性和自洽性,他验证不了任何系统自身以外产生的信息的真实性。 所谓系统自身产生的信息,就是数据库数据的变动信息,有价值的基本上有且只有交易信息。所以说比特币最初不过是中本聪一种炫技的产物,来证明自己对几种技术的掌握,你看我多牛逼,设计出了一个像三体一样的系统。因此,数字货币很有可能是区块链从始至终唯一的杀手应用。 比特币和区块链概念从诞生到今天已经快10年了,很多人说区块链技术在爆发的前夜,但这个前夜好像是不是有点过长了啊朋友,跟三体里的长夜有一拼啊。都说区块链技术像是90年代初的互联网,可是90年代初的互联网在十年发展后,已经出现了一大批伟大的公司,阿里巴巴在99年都成立了,区块链怎么除了币还是币呢? 正规的数字货币未来发展的形式无外乎几种,要么就是论坛币形式,或者类似股票的权益凭证等。问题是论坛币和股票之前,本来也都电子化了,区块链来了到底改变了什么呢? 所有想把TOKEN和应用场景结合起来的人最后都很痛苦,最后他们会发现区块链技术就是脱裤子放屁,自己辛苦搞半天,干嘛不自己作为中心关心门来收钱?最后这些人都产生了价值的虚无感,最终精神崩溃,只能发币疯狂收割韭菜,一边嘴里还说着我是个好人之类的奇怪的话。 因此,之前币圈链圈还泾渭分明,互相瞧不起,但这两年链圈逐渐坐不住了,想着是不是趁着泡沫没彻底破灭之前赶快收割一波,不然可能什么都捞不着了。 前段时间和一个名校毕业的链圈朋友瞎聊天,他说他们“致力于用区块链技术解决数字版权保护问题”,我就问他一个问题,你们如何保证你链的版权所有权声明是真实的,万一盗版者抢先一步把数据放在链上怎么办。他说他们的解决方案是连入国家数字版权保护中心的数据库进行验证…… 所以说区块链技术就是个鸡肋,研究到最后都会落入效率与真实性的黑洞,很多人一头扎进链圈后才发现,真正意义上的区块链技术,其实什么都干不了。 -02- 不是蠢就是坏的区块链媒体 空气币和区块链的造富神话,让区块链自媒体也开始迎风乱扭。一群群根本不知道区块链为何物的妖魔鬼怪纷纷进驻区块链自媒体战场,开始大放厥词胡编乱造。 任何东西,但凡只要和区块,链,分,分布式,记账,加密,验证,可追溯等等这些个关键词沾到哪怕一点点,这些所谓的区块链媒体人就会像狗闻到了屎了一样疯狂地把区块链概念往上套。 这让我想起曾经一度也是热闹非凡的物联网,我曾经去看过江苏一家号称要改变世界的“物联网”企业,过去一看是生产路由器的,我黑人问号脸,对方解释说没有路由器万物怎么互联,我觉得他说得好有道理,竟无言以对。 好,下面让我们进入奇葩共赏析时间,来看看区城链媒体经常有哪些危言耸听的奇谈怪论 区块链(分布式记账)的典型应用是*?? 正如前面所说,真正意义上的区块链分布式记账,不光包括“记”这个动作,还包括分布式存储和共识机制等。而*诞生远远早于区块链这个词的出现,勉强算是“分布式编辑”吧,就被很多区块链媒体拿来强行充当区块链技术应用的典范。 其实事实恰恰相反,*恰恰是去中心化失败的典范,现在如果没有精英和专业人士的编辑和维护,*早就没法看了。 区块链会促进社会分工?? 罗振宇好像就说过类似的话,虽然罗振宇说过很多没有逻辑的话,但这句话绝对是最没逻辑思维的。很多区块链自媒体也常常用这句话来忽悠老百姓,说分工代表效率提高社会进步,而区块链“无疑”会促进分工,他们的理由仅仅是分工和分布式记账都共用一个“分”字,就强行把他们扯到一起。 实际情况恰恰相反,区块链是逆分工的,区块链精神是号召所有人积极地参与到他不擅长也不想掺合的事情里面去。 区块链不能像上帝一样许诺他的子民死后上天国,只能给他们许诺你们是六度人脉中的第一级,我可以赚后面五级人的钱,你处于金字塔的顶端。
-
干 | 11 分钟完全掌握分支和绑定算法 - 概念(下一步)
-
干货 | 10分钟带你全面掌握branch and bound(分支定界)算法-概念篇