九、分枝切割算法

1、Gomory切割的算法原理

\qquad 考虑有一个等式的形式如下所示：
$$IL+F=f$$
\qquad 其中各项满足以下性质：

• $IL$是一个整数值的表达式
• $F$是一个严格正分数的和
• $f<1$是一个严格正的分数
  \qquad 从而可以得出一个结论：$F\ge$ f。从而在拿到任意一个等式之后，可以将等式中的项分别凑到$IL$，$F$和$f$三项中，之后根据$F\ge$ f 便可以得到有效的Gomory不等式。将Gomory不等式加到混合整数线性规划问题的线性松弛问题中之后，可以保证：
• 切割掉一部分原本线性松弛问题的最优解
• 同时保证所有原本混合整数线性规划的可行解都被保留
  \qquad 对于一个单纯型表形式的非整数解里面，必然有一个横行，
  $$x_i=b+f-\sum _j{a}_j{x}_j(1)$$
  \qquad 其中$b$是整数且分数$f$满足$0\le f<1$，将上等式(1)改写为：
  $$\begin{gathered} x_i+\sum _j{a}_j{x}_j=b+f \\ {x}_i+\sum _{j}floor(a_j)x_j-b+\sum _j(a_j-floor(a_j))x_j=f \end{gathered}$$
  \qquad 则在任意整数解里，有下式(2)满足
  $$\sum _j(a_j-floor(a_j))x_j\ge f(2)$$
  \qquad 不等式(2)即为Gomory不等式的一般形式。
  \qquad 除了Gomory不等式之外，还有其他一般性的不等式，如mixed integer roundin不等式和lift and project不等式；其他结构性的割约束，如knapsack cover不等式和Clique不等式。在分枝切割算法中，将不等式的添加和分枝策略进行结合，从而避免单纯割平面算法中系数爆炸的问题。

2、分枝切割算法

\qquad 分枝切割算法的流程如下所示：

\qquad 从上述流程可以看出，分枝切割算法和分枝定界算法的流程基本相似，知识在分枝之前，首先需要检查当前分数结点中有没有可以添加的有效不等式，讲这些不等式进行添加到线性规划模型中提升模型的下界。

THE END