查看“︁分支切割法”︁的源代码

{{disputed|time=2017-09-09T01:12:41+00:00}}
{{roughtranslation|time=2017-09-09T01:12:41+00:00}}
'''分支切割法'''<ref>{{Cite journal|title=A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems|last=Padberg, M.|last2=Rinaldi, G.|journal=Siam Review|doi=10.1137/1033004|year=1991|pages=60–100|lastauthoramp=yes}}</ref>是用于解决[[线性规划|整数线性]]问题（ILPs），即部分或全部未知数为整数值的[[线性规划]]（LP）的问题的[[组合优化]]方法。<ref>{{Cite journal|title=Branch-and-Cut Algorithms for Combinatorial Optimization Problems|last=John E.|first=Mitchell|journal=Handbook of Applied Optimization|year=2002|pages=65–77}}</ref>该方法在[[分支定界法]]的基础上，使用[[切割平面]]以收紧线性规划松弛。如果切割平面仅用来收紧初始的 LP 松弛，则改称为'''切割分支法'''。

== 算法描述 ==

以下假设 ILP 问题为最大化问题。

该方法首先使用[[单纯形法]]解决无整数约束的线性问题。获得最优解后，如果有约束为整数的变量取了非整数值，该算法会使用切割平面法以寻找进一步的线性约束：所有可行的整数点满足该约束，但目前的最优解不满足该约束。随后这些约束不等式可以加入线性问题中，使得下次求解可以获得「更接近整数」的结果。

在此基础上，算法使用[[分支定界法]]，将该问题分割为多个（通常为两个）子问题。随后使用单纯形法求解新的子问题，重复该过程。在分支定界的过程中，LP 松弛问题的非整数解为解的上限，整数解为解的下限。如果一个子问题的上限低于当前的全局下限，则可以除去该子问题。此外，在求解 LP 松弛问题时，可能产生其他切割平面。这些平面既可能是'''全局切割'''，即适用于所有可行的整数解的切割；或'''局部切割'''，即适用于当前分支定界子树下所有满足边界约束的解的切割。

算法概括如下：
# 将原 ILP 问题加入活跃问题列表 <math>L</math> 中。
# 取 <math>x^* = \text{null}</math> , <math>v^* = -\infty</math>。
# 当 <math>L</math> 非空时
## 从 <math>L</math> 中选择一个问题，并将其移出 L 。
## 解该问题的 LP 松弛问题。
## 如果该解不可行，返回第 3 步重新开始。如果该解可行，获得解 <math>x</math> 及目标函数值 <math>v</math>。
## 如果 <math>v\le v^*</math>, 返回第 3 步。
## 如果 <math>x</math> 为整数，令 <math>v^*\leftarrow v, x^* \leftarrow x</math> ，返回第 3 步。
## 如有需要，寻找使 <math>x</math> 不满足约束的切割平面。如果能找到相应平面，则将其加入 LP 松弛问题中，返回第 3.2 步。
## 进行分支，使得原问题分为可行空间更小的子问题。将这些问题加入 <math>L</math> 中，返回第 3 步。
# 返回 <math>x^*</math> 值。

== 分支策略 ==

分支策略是分支切割算法中的重要一步。在这一步中，可以使用多种启发式分支策略。下述分支策略都包含'''在变量上分支'''。<ref>{{Cite journal|title=Branching rules revisited|url=http://linkinghub.elsevier.com/retrieve/pii/S0167637704000501|last=Achterberg|first=Tobias|last2=Koch|first2=Thorsten|journal=Operations Research Letters|issue=1|doi=10.1016/j.orl.2004.04.002|volume=33|pages=42–54|last3=Martin|first3=Alexander|access-date=2017-09-08|archive-date=2019-06-07|archive-url=https://web.archive.org/web/20190607165520/https://linkinghub.elsevier.com/retrieve/pii/S0167637704000501|dead-url=no}}</ref>在变量上分支的大致过程为：如果变量 <math>x_{i}</math> 在当前的 LP 松弛问题的最优解中为分数 <math>x_{i}'</math> ，则向松弛问题中加入约束 <math>x_{i}\leq \lfloor x_{i}'\rfloor</math> ， <math>x_{i}\geq \lceil x_{i}'\rceil</math> 。

===最不可行分支===
该策略优先选择小数部分最接近 0.5 的变量。

===伪成本分支===
该策略的基本思想是当变量 <math>x_{i}</math> 被选作分支变量时，追踪目标函数的变化。基于过去的变化情况，该策略会选择预计对目标函数产生最大变化的变量作为分支变量。注意，在最初分支时，只有几个变量进行过分支，该策略会面临所需信息不足的情况。

===强健分支===
该策略在实际分支前将对变量进行测试，以确定哪个变量对目标函数的变化影响最大。'''完全强健分支'''会测试所有候选变量，计算成本很高。可以通过只考虑一部分候选变量，并不完全解出所有对应的 LP 松弛，来降低计算成本。

除了以上几种策略外，还存在大量其他的分支策略，比如伪成本分支所需的信息不足时先采用强壮分支，在获得足够的分支历史后切换到伪成本分支。

== 外部链接 ==
* [https://web.archive.org/web/20050901073653/http://www.cs.sandia.gov/opt/survey/mip.html Mixed Integer Programming]
* [http://scip.zib.de/ SCIP] {{Wayback|url=http://scip.zib.de/ |date=20061002132048 }} Branch-cut-and-price 框架，及混合整数规划求解器
* [https://web.archive.org/web/20171002101301/http://www.informatik.uni-koeln.de/abacus/ ABACUS - A Branch-And-CUt System] 开源软件
* [https://web.archive.org/web/20131117054948/https://projects.coin-or.org/Cbc COIN-OR Cbc] 开源软件

== 参考文献 ==
{{Reflist}}
[[Category:组合优化]]