分支切割法

分支策略

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

最不可行分支

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

伪成本分支

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

强健分支

该策略在实际分支前将对变量进行测试，以确定哪个变量对目标函数的变化影响最大。完全强健分支会测试所有候选变量，计算成本很高。可以通过只考虑一部分候选变量，并不完全解出所有对应的LP 松弛，来降低计算成本。
除了以上几种策略外，还存在大量其他的分支策略，比如伪成本分支所需的信息不足时先采用强壮分支，在获得足够的分支历史后切换到伪成本分支。