跳转到内容

分支切割法

维基百科,自由的百科全书

分支切割法[1]是用于解决整数线性问题(ILPs),即部分或全部未知数为整数值的线性规划(LP)的问题的组合优化方法。[2]该方法在分支定界法的基础上,使用切割平面以收紧线性规划松弛。如果切割平面仅用来收紧初始的 LP 松弛,则改称为切割分支法

算法描述

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

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

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

算法概括如下:

  1. 将原 ILP 问题加入活跃问题列表  中。
  2. 取  , 
  3. 当  非空时
    1. 从  中选择一个问题,并将其移出 L 。
    2. 解该问题的 LP 松弛问题。
    3. 如果该解不可行,返回第 3 步重新开始。如果该解可行,获得解  及目标函数值 
    4. 如果 , 返回第 3 步。
    5. 如果  为整数,令  ,返回第 3 步。
    6. 如有需要,寻找使  不满足约束的切割平面。如果能找到相应平面,则将其加入 LP 松弛问题中,返回第 3.2 步。
    7. 进行分支,使得原问题分为可行空间更小的子问题。将这些问题加入  中,返回第 3 步。
  4. 返回  值。

分支策略

分支策略是分支切割算法中的重要一步。在这一步中,可以使用多种启发式分支策略。下述分支策略都包含在变量上分支[3]在变量上分支的大致过程为:如果变量 在当前的 LP 松弛问题的最优解中为分数 ,则向松弛问题中加入约束

最不可行分支

该策略优先选择小数部分最接近 0.5 的变量。

伪成本分支

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

强健分支

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

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

外部链接

参考文献

  1. ^ Padberg, M. & Rinaldi, G. A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems. Siam Review. 1991: 60–100. doi:10.1137/1033004. 
  2. ^ John E., Mitchell. Branch-and-Cut Algorithms for Combinatorial Optimization Problems. Handbook of Applied Optimization. 2002: 65–77. 
  3. ^ Achterberg, Tobias; Koch, Thorsten; Martin, Alexander. Branching rules revisited. Operations Research Letters: 42–54. [2017-09-08]. doi:10.1016/j.orl.2004.04.002. (原始内容存档于2019-06-07).