分支切割算法

分支切割算法（Branch and Cut）是在分支定界算法基础上的改进算法。

有效不等式与凸包

问题描述

首先考虑整数规划（IP）问题。记显式可行域

则 IP 可写为集合形式

或与上等价的展开形式

下文在分支、割平面与凸包等叙述中，为简短仍多用 指代该域（及其在分支节点上的交、限制）。 表示 且分量为非负整数的任一可行解。

凸包定理（Wolsey, 1998）

定理：IP 的所有整数可行解构成的可行域（离散的点）的凸包 是一个多面体。其中， 表示可行域 的凸包（Convex Hull）。 精确地刻画出了可行域 的凸包。

核心思想

对于 IP 来讲，最优整数解一定在凸包中，因此在可行域内搜索最优解和在凸包内搜索最优解是等价的。根据这一点，我们可以将原问题重新建模成下面的线性规划：

并且，对于所有的 （也就是任意线性目标函数），LP 的最优极点就是 IP 的最优解。对于混合整数规划，该结论也成立。

逼近凸包

既然凸包对应的 LP 的最优极点就是 IP 的最优解，那我们只要找到 IP 的所有可行解的凸包，然后求解一个线性规划就可以完美地解决整数规划了。对于最小生成树问题和指派问题来讲，凸包的刻画比较容易，这两类问题都不是 NP-hard 问题。但是对于 NP-hard 问题，找到它们的凸包的清晰刻画基本是不可能的。因此，只能采取一些办法去逼近它们的凸包。有效不等式（Valid Inequality）以及割平面，就是来完成这一任务的。它们的功能就是不断地切割可行域，不断地逼近凸包。

算法思想

分支切割算法就是在分支定界算法的基础上，在分支的同时，根据节点的解的信息以及其他有用信息（例如一些问题特性等），给节点对应的子问题构造并添加割平面（Cutting plane），在缩小子问题的可行域的同时，又不排除任何可行整数解，从而更快地找到最优解的一种高效的算法。也正是由于加入的割平面没有割去任何可行整数解，所以分支切割算法也是可以保证最优性的。

核心概念

割平面（Cutting Plane）

割平面是一种线性不等式约束，用于切割掉当前线性松弛解中的非整数部分，同时保留所有可行的整数解。

割平面的特点

• 缩小可行域范围，提高求解效率
• 不割除任何可行整数解，保证最优性
• 迭代添加，逐步逼近整数最优解

算法流程

分支切割算法结合了分支定界和割平面两种技术：

▶ 分支切割算法步骤

1. 求解线性松弛

求得当前节点的线性松弛最优解。

2. 判断是否满足整数条件

如果解满足整数条件，更新全局最优解；如果不满足，继续下一步。

3. 尝试添加割平面

根据当前解的信息，尝试构造有效的割平面：

• 如果找到有效割平面，添加后重新求解线性松弛
• 如果没有找到有效割平面，进行分支操作

4. 分支或继续切割

• 切割：添加割平面后，可行域缩小，继续求解
• 分支：当无法找到有效割平面时，按照分支定界的方法进行分支

5. 迭代直至收敛

重复上述过程，直到找到最优整数解或证明无解。

常用割平面类型

Gomory 割平面

最经典的割平面方法，从单纯形表最后一行构造，保证能切割掉当前非整数解。

覆盖割平面（Cover Cuts）

针对背包约束等特殊结构设计的割平面。

流割平面（Flow Cuts）

针对网络流问题设计的特殊割平面。