分支定界算法 (Branch and Bound) 作为求解一般的混合整数线性规划中最常见，最有效的方法，受到了广泛的关注。目前主流的优化求解器均采用 分支定界算法的框架来求解混合整数线性规划问题。
分支定界算法由几个关键模块：
预求解模块(Presolving); 分支 (Branching); 节点选择(Node selecion); Linear Programming 求解； 割平面(Cuts); 原始启发式算法 (Primal heuristics), 以上模块均在上图中有所体现，正是他们构成了优化求解器中基于分支定界算法的求解框架。
考虑如下的混合整数线性规划问题：
我们在使用分支定界算法求解上述问题的过程中，得到其线性规划松弛问题的最优解为 ，这个 中如果存在非整数值的话，就需要对那些非整数值的变量进行分支。根据如上定义，我们给出预备分支变量的集合：
那么分支要做的事情就是在集合 中选择一个合适的变量来进行分支操作。显然选择哪个变量进行分支对整个分支定界算法有着非常大的影响。
一般在优化求解器中我们会定义出一个打分函数来确定出到底应该选择哪个变量进行分支，那么这个打分函数可以用来评价每个预备分支变量的好坏，打分高的变量就表示采用该变量分支的话就对整个分支定界算法效果好，反之亦然。打分函数的定义如上所示：
其中
表示当前问题的目标函数， , 分别表示如果用变量 做分支的话形成的两个子问题的目标函数。那么上式中 就表示采用变量 分支之后左右两个子问题目标函数相对于当前问题的增加程度。
我们知道 大于等于0，这是因为子问题是在更小的可行域上求极小值，所以子问题的目标函数值只会比当前问题的目标函数更小。我们在分支定界的搜索过程中总是希望得到的松弛问题的目标函数值越大越好，因为这就表明下界是越大的，这对于加速我们整个分支定界算法显然有着很大的帮助。由此可得 两个值越大就表明分支的效果越好。这就是为何我们定义出式(1)形式的打分函数来评价分支。
进一步我们给出改进版本的打分函数：
改进版本和原始版本的差距增加了一个参数 ，一般我们设定 ，主要是为了防止出现0打分的情况。基于以上打分函数，我们就可以对每一个预备变量进行打分，选出打分最高的进行分支即可。
分支的策略有很多，其基本思想就是采用打分函数来对分支的好坏进行评价，我们这里介绍以下四种分支策略。
让我们回顾一下式(2)中的打分函数：
其关键问题在于获得 ，
一个简单粗暴的想法就是我们通过直接求解每一个分支变量做分支后的的2个线性松弛子问题，即可获得 。数值实验表明 Strong Branching 可以有效提升下降的改进，但是显然 Strong Branching 的计算代价太大了，每做一次分支需要求解 次线性规划，这显然是很难接受的。
Strong Branching 确实有利于提升下降，但是计算代价太大，这主要是由于我们需要求解很多的线性规划问题来估计分支变量后的效果。我们就会思考是否可以在整个 Branch and Bound 搜索过程中来对目标函数的改进进行估计，这样就无需真的求解线性规划去估计对于下降的提升，那么这种方法就是 Pseduocost Branching 方法。
其中
和 的含义 分支选择 变量后单位 引起的下界提升。当然在整个 Branch and Bound 搜索过程中，我们可能会不止一次对同一变量进行分支，我们就记录下这些分支的历史进行，用历史信息的均值去估计下降的提升，由此可得如下表达式：
上式中 表示在当前 Branch and Bound 搜索过程中，我们对变量 曾经分支过 次，那么上式右端项分子就是把历史上这 次分支引起的下界提升值求和。整个表达式就表示我们用历史上对该变量进行分支后的下界提升的均值来估计在当前节点对该变量进行分支后下界的提升。之后借用打分函数即可评估每个分支的好坏：
Pseduocost Branching 方法巧妙的利用了历史信息来对下界提升进行了估计，和 Strong Branching 相比它无需求解线性规划，其计算效率会很高。Pseduocost Branching 的缺点在于比较依赖于历史信息，在有充分多的历史样本的情况下，我们用历史的均值来估计才会比较准确。但是在 Branch and Bound 搜索的初期显然我们并没有多少历史信息来做估计，这就有可能会导致 Pseduocost Branching 算法效果变差。
前面介绍了 Strong branching 和 Pseduocost Branching, 这两种方法各有各自的优势，也各自有各自的缺点。Hybrid Branching 的思想也很简单 就是将上述两种分支方法结合，以达到却长补短的效果。我们知道 Pseduocost Branching 在搜索初期可能由于没有多少历史信息来做估计而导致算法效果变差，那么我们就考虑在 Branch and Bound 搜索初期先采用 Strong Branching 的方法，然后当搜索树的深度达到一定深度之后，再切换到 Pseduocost Branching，这就是 Hybrid Branching 的一种实现版本。
这样做的好处就是 在搜索初期 我们可以用准确性高的 Strong Branching 来收集足够的历史信息，当有了足够的历史信息后我们再启动 Pseduocost Branching，这样就可以保证 Pseduocost Branching 的准确性，同时又可以有效地降低计算量。当然 Hybrid Branching 的版本不止这一种，还会有其它的结合方式，但基本思想都逃脱不出这个框架。具体 Hybrid Branching 有哪些实现版本详情见参考文献【1】。
最后我们介绍一种非常简单的分支策略。如果说一个非整数变量的取值非常接近于0.5，那我们感觉这类非整数变量是距离整数点比较远的变量，对于整数约束来说这些变量就是 Most Infeasible 的，我们自然而然会想到首先把这些变量进行分支。基于此思想，我们给出打分函数的表达式：
实际的数值实验结果表明 Most Infeasible Branching 这类分支策略并没有明显优于随机选择的分支策略，因此该分支策略并不是一种非常有效的分支策略。
【1】 Achterberg T. Constraint integer programming[J]. 2007. 【2】Bestuzheva K, Besançon M, Chen W K, et al. The SCIP optimization suite 8.0[J]. arXiv preprint arXiv:2112.08872, 2021.
微信公众号后台回复
加群：加入全球华人OR|AI|DS社区硕博微信学术群
资料：免费获得大量运筹学相关学习资料
人才库：加入运筹精英人才库，获得独家职位推荐
电子书：免费获取平台小编独家创作的优化理论、运筹实践和数据科学电子书，持续更新中ing...
加入我们：加入「运筹OR帷幄」，参与内容创作平台运营
知识星球：加入「运筹OR帷幄」数据算法社区，免费参与每周「领读计划」、「行业inTalk」、「OR会客厅」等直播活动，与数百位签约大V进行在线交流
文章须知
文章作者：王源
微信编辑：疑疑
如需转载请在公众号后台获取转载须知
关注我们
FOLLOW US
内容中包含的图片若涉及版权问题，请及时与我们联系删除
评论
沙发等你来抢