优化是决策的一般形式，在我们的社会中很常见。它的应用包括从求解数独谜题到婚礼上的座次安排。同样的技术可以调度航班和机组成员，协调钢铁生产，组织铁矿从矿井到港口的运输。人力资源和材料管理上好的决策可以令企业提升上百万的盈利。同样的问题很多也在我们日常生活出现，成为决定每天送货路线，决定学校时间表，传输电力到家里等种种问题的一部分。除了它们的重要性，这些问题如果用传统的本科计算机科学方法难以求解。 这门课程为已经完成离散优化高阶篇的同学设计。 请看这门课程的宣传视频：http://www.cpr.cuhk.edu.hk/cutv/detail/988
3.3.2 混合整数线性规划
Loading...
From the course by The Chinese University of Hong Kong
离散优化算法篇 Solving Algorithms for Discrete Optimization
ratings
Explore Related Videos
At Coursera, you will find the best lectures in the world. Here are some of our personalized recommendations for you
From the lesson
混合整数线性规划
这个模块从介绍线性规划和用于解决连续线性规划优化问题的Simplex算法开始，之后展示了这个方法如何可以和分支限界法配合来解决混合整数线性规划问题。之后再进一步学习Gomory切割和分支切割法并领略它们如何提高求解速度。
Meet the Instructors
Prof. Jimmy Ho Man LeeProfessor
Department of Computer Science and Engineering
Prof. Peter James StuckeyProfessor
Computing and Information Systems
哪吒根据诸葛亮的指引攻击气场时却发现该处并无道士
原来狡猾的通天教主早已偷偷偏移气场
诸葛亮之前的妙法并不能找出如今阵中的最弱道士
哪吒就请诸葛亮重新设法找出弱点所在，诸葛亮再召出时空飞龙求助
[音乐] 哪吒根据我们的计算，他就跳到这个最优这个
顶点，然后就攻击这个道士，但是他发现了这个道士不是最弱的一个
他也不知道发生了什么事情，后来了就是观测了
一会之后呢，这个太上老君呢就发现原来好狡猾的这个
通天教主他已经暗地把这个气墙呢
移动了一点点，所以呢刚才计算出来的这个最弱的一点呢
已经不再是最弱的一点了，那当然，诸葛亮就根据我们教他的这个算法呢
再一趟再计算这个最弱的一点出来，然后呢哪吒呢就又跳到这个
一点，希望攻击在这个点上面这个道士的，但是呢他发现那里是没有人的
后来他们才发觉呢就是原来他们计算出来这个顶点呢是个非整数顶点
但是呢根据这个万仙阵所有的道士都是站在一个整数的坐标的位置点上面的
哪吒去到这个点呢就根本就没有当时可以给他攻击的，啊，所以呢现在就
问题来了，我们怎么可以找出这个最弱这个道士然后可以攻击他，然后把这个万仙阵呢
彻底地去破坏呢，好了，我们所以现在有一个气场的问题
我们因为这个通天教主他是非常狡猾的，他也知道呢
这个哪吒有我们的帮忙最后呢已经知道可以攻击最弱的这个道士
所以他暗地呢就已经把他的气墙微调了一下，然后最新的气墙它的相交点
相交的地方，最弱的地方呢它的这个顶点呢
再不是一个整数点来的，所以我们的新的任务呢
首先就是我们的模型已经改变了，因为呢这个通天教主呢已经暗地把
这个其中一个气墙它改变了，而且所以现在我们要做的任务就是在
新的气墙的相交点里面把里面所有的整数点的最弱的一点找出来
我们找到的话我们就可以攻击这个道士，就可以把这个万仙阵呢可以破坏了
好啦，所以呢根据新的气墙的相交的地方
这新的这个多面体呢我们发现求出来的最优解的是一个非整数来的
所以呢这个坐标上面当然就是没有人呢因为所以的道士都在方格的点上面，方格呢就是
在整数的点上面，那其实呢，老实说，我们之前其实也是有一点幸运，因为我们是利用一个实数
约束求解的方案来去算这个最弱的一点
我说我们是比较幸运就是因为我们刚好找出来的最优点呢它都是一个整数点
但是呢通常我们给你们一个线性规划问题呢
没有保证它的最优的解呢所有的变量都是拿到一个
整数作为它的赋值的，所以呢我们现在就需要呢问题还是在的，我们就需要
在这个网格上面所有的整数点找出最弱的一个道士
然后呢从而呢我们就可以攻击这个道士，希望可以把这个
万仙阵这个彻底地破坏，但是呢其实我们现在要解决这个问题呢已经不是
我们原来的一个线性规划问题，我们这个新的问题呢里面因为我们要找的是
整数的最优解，所以我们现在要解决的问题就是我们称之为这个混合整数线性规划问题
好啦，这个呢就是我们新的气墙，看起来了好像跟我们之前
的一个气墙是差不多，其实因为他这个通天教主呢
是把几种个气墙稍微的移动一下，稍微移动一下，所以呢其实我们发现
现在呢在这个气墙上面呢有很多点都不是整数来的
而且呢我们也可以看到了，我们利用红色来代表了就是在这个气墙里面的
整数点，这些点呢就是我们这个
混合整数线性规划问题里面的可行的解，而且呢这些解
也是每一个点上面的都有道士站在上面的
我们现在要做的就是在那么多点里面找出一个点就是<br>如果我们攻击这个道士呢，我们可以造成的破坏是最大的
最重要呢就是在新的气墙上面呢我们发现他的顶点呢
这个这里是没有这个红色的点的，而且我们也看见它的坐标它是不是一个整数来的
好了，现在我们就可以利用比较数学的方法了，来介绍一下
什么叫一个混合整数线性规划问题，其实呢，这个
混合整数线性规划问题呢跟我们之前看见这个线性规划问题呢差不多是一模一样的
只是加了一个新的条件，这个新的条件就是什么呢，我们多了一个S这样的集合
如果这个我们有一个变量 xi
如果这个 i 呢这个指数呢是属于 S 这个集合里面呢，我们也要求
这个 xi 这个变量呢它要取得赋值呢要为一个整数
所以呢，这个混合整数线性规划问题跟这个
一般的线性规划问题里面最大的分别就是我们要求我们这个问题里面的部分的
变量它们都会被这个限制为这个整数，这个就是唯一的分别
好啦，其实呢要解决这个混合整数线性规划是个NP
困难的问题，因为我们要解决一个只有
0，1整数上面的线性方程呢，也是这个 NP
完全的，我们怎么证明这一点呢，我们就可以看一看一个非常有名的 NP
完全问题，就是子集和的问题，在这个子集和的问题上面呢我们就有一个整数的集合，我们叫
S，S 里面每一个元素就是 S1 到 Sn
然后呢我们也给定了一个整数我们叫 S0
我们现在的问题呢就是问这个 S 这个集合里面我们可不可以
找到一个子集，就是 S 的子集
里面的元素呢我们要求呢它们的总和为我们刚才给定的 S0 这个数，原来呢其实这个
子集和问题呢很简单就可以把它找出一个
混合整数线性规划问题这个模型出来，我们需要就有n 个变量，n 个变量呢每一个变量呢
都是需要在0到1中间的，而且呢每一个变量我们其实也要求它为整数来的
然后呢我们就要求呢这个 S1 乘以 X1 加到
Sn 乘以 Xn 要是等于 这个 S0，就是说呢当 Xi
是唯一的时候呢我们就是在这个子集里面呢有这个 Si
这个数值在里面，Xi 为0的时候呢我们这个子集呢就没有这个
Si 这个数值在里面，我们就要看看我们可不可以找到一个子集里面的
元素加起来的总和就是我们给定的这个 S0 这个数值呢，因为我们
可以把这个子集和这个问题呢利用这个混合整数线性规划来
建模，所以呢其实我们这个要解决混合整数线性规划问题本身也是个
NP 困难的问题，那我们可以怎么去解决一个
那么困难的一个混合整数线性规划问题呢，有一个思想就是什么呢，我们如果拿到
一个混合整数线性规划问题呢，我们就先不处理这个问题，我们处理了它的线性松弛问题
什么叫它的线性松弛问题呢，就是把我们原来这个问题它对这个某些变量的整数的约束的
要求呢，把它移除，暂时移除，然后就把原来这个问题呢当为一个普通的线性规划问题呢
来求这个最优的解，然后我们希望呢，就是可以把这个它这个
线性松弛这个问题的解呢，最优的解呢，我们可以做一些操作
就可以找到我们需要解决的这个混合整数线性规划
原来这个问题呢它的最优的解，但是呢，我们可以看看下面这个例子
我们就发觉呢，这个思想呢，是行不通的，我们这个例子呢，很简单，只有两个变量
而且只有一条的约束，当然呢，对每一个变量呢，我们也是要求它是非负的
有了这个问题之后呢，当然呢我们可以利用我们之前学过这个
单纯形这个算法，又或者呢我们在中学学过的方法呢，我们都可以为这个问题呢
找到它的最优的一个解，这个最优的解呢，就是在 (1.857,<br>0)这个地方，就是呢，这个地方啦
好啦，我们现在问的问题就是，我们有没有可能利用这个我们原来这个问题的线性松弛
的问题呢，它求出来的最优的解，可以帮助我们找到，如果我们
要求X跟Y都是整数的话，这个情况之下这个混合整数线性规划问题
可不可以找到它的最优的解呢，我们可以譬如说，可不可以用取整这个操作呢
譬如说就是我们把这个1.857向上取整，那就变成了这个（2, 0）了
我们发现这个(2, 0)呢，根本就是在我们的可行的解的外面了，所以根本
就不可行，然后如果向上取整不行呢，我们可不可以向下取整呢？ 就是可以拿到(1,
0)这个最优这个解呢，但是我们发现(1, 0)这个解呢
根本就不是最优的解的，因为我们最优的解呢，其实在这个地方
所以呢我们发觉我们这个利用这个取整这个思想呢
是行不通的，我们真的是需要呢一个专门为了解决这个混合
整数线性规划问题的一个算法呢，来帮助我们去解决这一类的问题
好啦，我们去讲，怎么解决这一类的问题里面呢，我们首先，讲一讲两个的观察
第一，这个就是我们之前这个气墙的相交的这个多面体，而且呢
我们在里面呢，就利用红色的点呢，来表示这个多面体里面的
一个整数的可行的解，对于一个混合整数问题呢，它们
所有的可行的点，就是我们刚才讲这个红色的点呢，对于它这个问题的线性松弛来讲
都是可行的解，这个应该也挺容易明白的，另外一件事情就是
如果我们这个混合整数线性规划问题，它的松弛问题的解
它的最优解呢，是个整数的话呢，这个
整数的最优的解呢，也应该就是我们原来这个混合整数线性规划问题的最优的解
但是相反的话，就是说，如果我们在
我们混合整数线性规划问题里面找到一个最优的解呢，它就不一定
是它的松弛问题的最优的解，啊，这个就是两个 我们要需要利用到的一个观测。
好啦，那我们再回到 去讲啦，就是怎么解决这个混合整数线性规划问题呢，有一个笨的思路
就是我们要检查我们这个问题里面所有的整数的可行的解
这个其实大家一想就知道，这个是有问题的
因为呢，所有整数的可行的解呢，就是太多了，我们根本呢
就没有可能一个一个去检查它们的，所以呢，我们就要提出一个新的方法
出来，其实我们这个新的方法呢，就是利用我们之前学过这个
单纯形的这个算法呢，来不断的去为我们 不断的改进的这个原来这个问题的松弛问题
然后通过增加约束来进行这个分支，就是把我们原来这个
整数线性规划问题呢，我们先不处理它，先处理它的松弛问题，但是我们也利用
通过这个增加约束呢，来把这个问题呢分解，划分出这个子问题
直到呢，我们在一些子问题里面，改良过的松弛<br>问题里面呢，我们可以找出一个最优的解，这个最优的解呢
而且是一个整数呢，那就可以帮助我们去解决我们原来这个混合整数线性规划问题了
好啦，这个就是一个思想，下面呢我们就把我们这个算法呢，可以给大家去说明
我们要介绍呢，就是一个我们叫分支限界
其实呢，我们之前在解决这个离散优化问题
基于这个约束求解这个方法来做的时候，已经介绍过一个
分支限界法的这个算法了，我们这个算法呢
也是跟之前学过这个算法呢，它的思想是一样的
所以它们有同一个名字，首先呢，我们假设我们要
P就是我们要解决这个混合整数线性规划问题，然后呢，我们就为这个P它的
线性松弛问题呢，去求最优的解，假设我们求到这个解呢，就是θ
那如果我们非常幸运，求到的解这个θ呢，每一个我们要求
为这个整数的变量，它的赋值都为一个整数值的话，那我们
就非常开心了，因为这个θ呢，就是我们要原来解决这个问题的最优解了
但是如果我们没有那么幸运的，就是说，在我们的这个
最优解里面呢，我们有某一个的整数变量，譬如说我们叫它为Xi吧
如果这个Xi它的赋值为V，这个V呢 是个非整数来的，我们就可以利用这个V呢
帮助我们把我们这个P这个问题呢产生两个子问题，我们叫这两个子问题就是Pbelow
跟这个Pabove，这个Pbelow跟Pabove其实是非常简单，我们就是利用
刚才求到这个非整数的这个值V，去加进两条的约束
为我们这个原来的P这个问题产生两个子问题，第一个子问题我们叫Pbelow呢，就是
原来的P这个问题呢，加上一条Xi小于V的floor，就是向下取整
这个约束，Pabove呢就是在P这个原来这个问题加上Xi大于
V的ceiling，就是向上取整，为这个V向上取整
我们利用这两条这个很简单的约束呢，我们就产生两个子问题了
有了两个子问题之后，我们就可以利用这个递归的方法呢，去解决，分别去解决
每一个的子问题，然后呢，我们为这个Pbelow找到最优的解
为这个Pabove也找到最好的，最优的解，然后我们原来这个问题P呢
它的最优的解呢，其实就是两个子问题Pbelow跟Pabove当中更好的一个
就是我们原来这个问题P它的最优的解了，所以这个分支限界
法呢，是非常，因为它是利用这个递归，所以非常容易去明白它的运作的
好啦，在下面呢，我们就利用这个分支限界法呢，去帮助我们解决
我们在故事里面这个问题，我们首先呢就为我们原来这个混合
整数线性规划问题呢，求它的线性松弛的
一个最优的解，我们发现呢，它出来的解呢，是非整数的
但是呢，在上面呢，我们有两个非整数，就是x的值跟
这个z的值，所以呢，我们就可以随便选取其中一个变量
来帮助我们做这个分支，就譬如说我们选取x这个变量吧，所以呢，我们就可以
而且呢，这个刚好这个最优的解呢，这个点就是在
这个地方的，然后选取这个x这个变量之后呢，我们就要
加入，引入一个新的限制，就是x小于
等于7，这个7呢，就是7.777的它的向下的取整
就好像呢，我们要求这个哪吒呢，就
来一个大的切割就是把我们原来的问题呢分开了 两个子问题。
在这里呢我们要大家小心一点呢就是在这个地方其实呢
我们因为切割的地方是切在这里，这个就是原来的一个面，所以呢我们现在的多面体呢
多了一个面的，这个就是切割之后我们出来的一个新的子问题。
好了，有了新的子问题呢，我们当然有可以利用我们的求解的方法呢找出一个最优
的解，我们这个最优的解呢就是在下面这个，就是呢在这一点。
来到这一点之后呢，我们还是发现 z 的赋值呢还是
一个非整数来的，所以我们还是需要产生两个子问题。
第一个子问题呢就是我们要再增加 z≤4,就是呢这个 4.8333
这个向下的取整的出来的结果，就是好像这个哪吒又再来一个大的切割。
然后呢，利用这个切割之后呢我们有一个新的问题，然后我们
再利用这个我们之前学过的算法去找出一个新的最优的解。
这个新的最优的解呢就是在这里。
这个新的最优的解y下面呢还不是一个整数来的，所以我们还是需要继续的
去把我们的问题划分为这个更多的子问题。
现在我们选取这个 y 这个变量，我们需要增加的约束就是
y≤1，所以哪吒就要再做一个大的切割。
有了这个切割之后，我们呢就可以求到它一个新的最优的解了。
这个新的最优的解，在这个角落这个顶点上面。
而且最重要的就是什么，这个是一个整数值来的，就是说我们成功的找到第一个的<br>整数的最优解。
好了，找到这个之后呢我们就要这个到目前为止最好的一个目标值为这个34把它记住了。
我们处理了第一个的子问题之后，我们就可以去回溯去处理另外一个子问题。
另外的子问题呢我们要加的这个切割呢，这个平面就不一样了。
所以呢我们就要求这个哪吒再来一个大的切割就然后得到这个子问题。
其实呢我们再求解呢，把它最的优解找了出来，其实就是在这一点的。
但是我们发现呢，这个最优解呢还是有这个变量，它的赋值是非整数来的。
好了，下面因为空间的问题，也是因为时间的问题呢，我们就利用
把整个我们利用这个分支限界法整棵的这个决策树都显示出来。
我们重新再来好不好？我们在这个问题的顶点，就是我们原来要解决这个问题。
原来要解决这个问题，我们发现求得一个解之后呢，出来的解的不是完全是整数，所以我们就利用
x 这个变量来做一个分支。
然后再求一个解发现还是不是整数，所以我们利用这个 z 这个变量来做分支。
然后呢 找出来这个解还是不是整数，我们需要利用 y 这个变量来做这个分支。
然后我们就找到一个整数的最优的解了，然后我们就要记住利用目前最好的目标值为
34，因为我们需要这个 34 在未来为我们限界。
好了，找到一个最好的整数的解之后呢，我们就需要回溯，回到这一点。
我们刚才就是在这里就去停的，我们继续下去，我们就利用这个
变量来做分支，然后发现在下面在还是需要利用
y 来做分支，但是在来到这个节点，我们也找到一个 整数的解了。
但是这个整数的解它出来的目标函数的值只是
32，比我们目前最好的34为差劲。
所以呢，我们还是要回溯的。
我们继续回溯，到这个点呢我们发现还是有分支，然后我们就可以找到一个整数的
最优解，但是它的目标函数值是31，当然呢
给我们这个34 呢，比这个 34 呢不够好，所以呢我们还是要回溯
到这个点，然后呢我们继续往下走，往下走我们有再
找到一个整数的这个解出来，然后呢它的目标函数值只是 30，
所以也是不够这个34，所以我们需要
回溯到这个地方，发现我们还是没有整数的解，所以我们又继续往下走。
这里有...，因为我们这个决策树太大了，
我们暂时，我也可以保证在下面我们不会找到更好的解出来的。
所以呢 我们看完下面的地方呢，我们回溯到这个点，这个点我们发现
出来的根本就不可以满足的，所以我们需要回溯。
回溯呢，往下面走，也是不满足的，我们需要回溯。
一回溯呢就到了这个点了，虽然有一个整数的解，但是它出来的目标函数值呢是
32，也是比我们目前为止最好的差劲，所以我们还是要回溯，回溯到这一点。
回溯到这一点呢，当然我们可以继续去 看看检查这个数的其他地方。
但是我们经过更多的步骤之后呢，我们发现下面还是找不到比现在我们目前为止找到最好的目标值的这一个解的。
所以我们要回溯到这一个点，这一个节点呢，我们一求解发现的出来的一个解也是一个整数的解。
而且呢它的目标函数的值是 36。
比我们刚才的 34 为好，所以呢我们呢就要把我们最好的目标值要改变了。
到了这里呢，我们发现我们已经把整个的决策树也已经检查过，
而且我们也已经找到一个最好的、 最优的为我们原来这个混合
整数线性规划问题找到一个最好的解出来，就是（8,0,4）这个点。
好了，我们可以看见在我们原来这个问题，我们刚才找到最好的点呢就是（8,0,4）
这个地方，就是刚好在我们一个顶点的旁边来的。
而且它的目标函数的值是 36。
这个就是我们利用这个分支限界法，可以帮助我们把这样子的
一个混合整数线性规划问题的最优的解找出来。
好了，刚才你们也可能会觉得：哇，我们这个决策树也挺大的。
我们需要去做这个分支做了好多趟， 做了很多的回溯，才终于找到我们的最优的解出来。
但是其实我们现在又介绍的是一个所谓是叫探明的一个概念。
这个"探明"的概念就是告诉我们呢，其实我们到了这个决策树的每一个节点呢，不是它下面的每一个
子问题呢我们都需要深入的去探索的。
好了，我们其实可以看看 我们每到每一个节点，其实呢有三个可能性呢我们不需要
再往下走的，不需要再探索下面的子问题的。
如果我们 到了一个节点，根本这个节点上面这个问题是不可以满足的。
约束也不可以满足的话，我们根本下面就没有子问题要探索了。
第二个可能性呢就是我们发现现在这个节点 里面最优的这一个解呢就是一个整数的值。
那我们下面也是没有这个子问题的。
我们也需要做的就是看看，比较 一下这个整数值的，它的目标函数的值跟我们目前找到最好的
值是好啊，或是比较差，好的话我们就要
把目前最好的值呢改为我们现在最新找到这个
目标函数值，然后我们就要继续的搜索下去，但是就不需要往下走了。
但是第三个可能性是什么呢？我们到了一个节点，它的松弛的问题的最优的解呢
有可能还是非整数的，但是它出来的最优的
这个解它的目标函数的值比我们目前找到整数
整数解的最优的解的它的目标函数的值
如果是比它更差劲的话，我们发现呢我们还是不需要去探索这个
松弛问题下面的子问题的。
为什么呢？ 因为探明这个概念就是告诉我们呢
在这个情况之下，就算我们往下走，如果我们已经
找到一个实数的最优解，然后我们把这个实数再划分为子的
问题呢，我们的子问题找到出来的就算是整数的最优解呢，它出来的
这个目标函数的值呢肯定也不会比我们这个实数的最优解的目标函数的值为好的。
所以如果我们这个松弛问题的最优解，它的目标函数已经比我们当前的最优
当前的最好的一个目标函数的值的话，往下走
无论我们怎么去搜索呢，找到的，就算找到这个整数的最优解呢
出来的结果它们的目标函数的值都不会比我们当前的最好的这个目标函数呢
为好的，所以我们往下探索下去也是没有用的，所以呢我们就可以
就停止我们的搜索了。
所以呢我们其实刚才呢这个问题呢
我们不需要搜索那么大的一棵的这个决策树的，我们记得我们
来到这个地方，来到这个地方呢我们呢就有一个整数的最优解，而且呢它的目标值为
34，所以我们就回溯到这一个点，这个点呢我们找出来的是个实数的
非整数的最优解，但是我们也要看一看它的目标函数的值只是
33.5，这个 33.5 比 34 为差的，所以根本我们就不需要去往下去
探索它的子问题，我们就可以从这一点呢开始回溯了。
所以下面呢的子问题不需要探索。
然后呢我们来到这一点，我们发现呢它也是一个非整数的最优解，但是呢，它出来的
目标函数的值也是 34， 34不是比
34 好，所以呢，我们再探索下去呢，就算我们找到一些整数的最优解
我们可以保证它的目标函数的值呢肯定比这个 34
为差的，所以我们探索下去也是没有用，所以呢我们就可以在这一点回溯。
然后呢，我们再可以回溯到这一点，然后再往上走<br>再往上走，就可以来到这一点呢，我们就可以找到我们这个问题
的最优的一个解了，而且是一个 整数的解，它的目标值呢为 36。
好了，其实呢我们这个
算法看起来挺简单，但是其实有两个非常重要的决策我们没有好好地讨论过的。
就是当我们求到一个非整数的
非整数的最优解的时候，为我们这个线性松弛问题找到这样子的一个最优
解的时候，如果在这个最优解上面，我们有多于一个变量，本来我们是，要求它是
要我们叫这一类的变量，就是整型的变量，就是说这些变量呢我们要求它是整数，但是呢
它的赋值呢当时是为一个非整数的。
如果我们有多于一个这样子的整型的变量的话 我们应该选择哪一个变量来进行分支呢？
另外一个问题呢就是，我们选择了这样子的一个变量作为一个分支，分支了之后我们其实有两个子问题嘛
有一个 Pbelow 跟一个 Pabove，那我们 应该先去访问去处理哪一个子问题呢？
这个就是我们需要回答的问题，这个就是我们的所谓是分支的策略。
有一个思想就是说，啊，我们应该
选择哪一个整数的变量呢？就是选择一个变量，整数的变量，它的
取的赋值就刚好在两个整数的最
接近中间的变量，那看起来就是一个挺合理的一个思想。
但是实际上呢，如果我们这样子去选择这个变量，得到出来的结果是非常糟糕的。
其实呢如果我们要去寻找一个最好的整数变量来进行分支呢，这个问题
本身就是一个 NP 困难的一个问题，所以呢有很多不同的
启发式的策略呢已经开发了出来，帮助我们去
选取一个好的整数变量呢来进行一个分支。
好了，假设我们已经找到这样子的变量，我们要利用它来进行分支，我们有两个子问题，一个
P below，一个 P above，那我们应该先访问哪
一个问题呢？有一个思想呢就是所谓是强分支。
强分支就是什么呢？我们就两个子问题都先去
把它处理，也把它最优的解也找出来，找了出来之后呢，我们呢
就去访问一个子问题，它出来目标函数的值是提升最多的一边。
这个就是呢所谓是强分支。
那但是当然大家也可以觉得呢，这个强分支呢
是一个挺贵的一个分支方法，因为我们需要把两个子问题都先把它最优的
目标值呢求出来，然后我们才决定我们先访问哪一个子问题。
所以呢也有人提出了所谓是伪费用这个分支。
这个伪费用这个分支呢其实跟这个强分支是很像
就是呢我们就是对两个子问题呢它有可能对这个目标
值的提升呢，我们不去真正的去计算，我们去估计，然后利用<br>这个估值呢来决定我们需要去访问
P below 或者是 P above，所以这个
伪费用这个分支方法呢是比较便宜一点，那当然呢也 没有这个强分支那么准确的。
如果我们看看现代的混合整数线性规划
的求解器呢，我们发现呢它们的效能效率呢是非常高的，往往它们可以处理呢
上百万个条的约束，上百万个的变量的。
其实在里面呢 它们除了利用我们刚才介绍的分支限界算法之外呢，它们还有其它
不同的技术呢可以帮助这个搜索呢，提升这个搜索的效率的。
包括这个割平面法，这个就是我们下一节课呢将会要提到的一个技术。
这个割平面法呢就是在求解这个过程
里面呢，我们要产生一些冗余的约束，利用这个冗余的约束呢
把我们要搜索的这个范围呢收窄。
它们其实也开发了一批呢 基于这个启发式的算法，这个启发式的算法呢
可以帮助它们比较快速地找到一个比较好的解。
因为在一个分支限界的这个算法里面呢，我们往往是希望就是
先把一个比较好的解可以求出来，然后这个好的解呢可以帮助
我们把往后我们搜索的，要搜索的范围呢，可以把它大大地收窄的。
它们也利用很多不同的智能的自动化的搜索的方案
它们就有办法呢可以集中在可以有机会发现好的解的地方来搜索的。
而且呢它们有，也有跟我们约束编程的这个求解的技术
里面取经，就是包括它们也做一部分的传播了，当然
它们做的传播呢就是线性的传播，因为在我们这一类的问题里面所有的约束呢都是线性的。
它们也尽量去希望在问题里面看看呢有没有可能发现一个特殊的 线性的结构。
譬如说，会不会这个大的问题里面
里面有一个子问题呢是一个背包的问题，如果有的话，我们就可以利用一些
专门的算法呢来帮助我们解决，解决我们这个大问题里面这个子问题的一个解了。
其实呢这个技术呢就好像我们的全局 约束这个技术，是有一点像的。
好了，我们可以来一个总结。
在这一节课里面呢，我们针对的就是所谓叫混合整数线性规划问题。
这一类的问题呢是，一类非常常见的离散优化问题，所以它们呢是非常重要。
而且呢我们也介绍了一个分支限界的算法呢，来帮助我们解决这个混合
整数线性规划问题。
在这个分支限界这个算法里面呢
虽然在我们的演示当中呢，我们就说在每一个节点呢，我们都是利用我们之前讲过这个单纯形算法呢
来为每一个线性松弛问题呢来求这个最优的解。
但是在现实当中呢，其实我们应用，调用的这个算法呢，是一个叫
对偶单纯形这个算法，那这个对偶单纯形这个算法呢其实就是
简单的单纯形这个算法的一个变种，但是对偶单纯形这个算法呢
是它的这个递增性的性能呢是比我们的 单纯形的算法它是比较好。
为什么需要这样子的一个算法呢？是因为
我们利用分支限界这个方法的时候呢，我们是不断去添加新的约束
到我们的问题里面去产生我们的子问题的，所以我们就需要一个算法它的递增性呢
的性能呢是比较高，比较好一点的，所以在现实当中我们是采用对偶单纯形的这个算法的。
我们也看到呢其实现代的混合线性规划问题的求解器呢，它们的效率是非常高的。
是因为它们有很多不同的技术，特别呢它们就是好像是知道在这个整棵的求解
这个决策树上面呢哪里有好的解，如果我们可以一开始的时候就求得好的解呢
就可以帮助我们在未来的搜索呢，就可以把这个搜索的范围呢可以大大地收窄。
而且呢 我们知道我们要解决的这一类的问题呢，它们的是
NP 困难的，所以就算我们不可以把它的最优的整数的解找出来呢，其实它们也有这个技术呢
把这个问题的目标函数的值，它的好的上界跟好的下界呢可以求出来。
对于这个混合整数线性规划问题呢，其实还有很多不同的技术我们需要是学习的。
在未来的节呢，我们下一节课呢，我们也有一个新的技术要介绍给大家。
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2019 Coursera Inc. All rights reserved.
