基于线性规划的图最大团问题的分支切割法求解示例
我将为你讲解如何使用分支切割法求解图最大团问题（Maximum Clique Problem）。我会从问题描述开始，逐步讲解建模、线性规划松弛、切割平面添加以及分支定界过程，确保每个步骤都清晰易懂。
1. 问题描述
定义：
给定一个无向图 \(G = (V, E)\)，其中 \(V\) 是顶点集合，\(E\) 是边集合。一个团（Clique） 是图的一个顶点子集 \(C \subseteq V\)，使得 \(C\) 中任意两个顶点之间都有边相连（即 \(C\) 的导出子图是完全图）。最大团 是指包含顶点数最多的团。
例子：
考虑下图：
顶点：1, 2, 3, 4
边： (1,2), (1,3), (2,3), (2,4)
- 集合 {1,2,3} 是一个团（因为1-2、1-3、2-3都有边）。
- 集合 {2,4} 不是一个团（因为需要边2-4，但图中没有）。
- 最大团是 {1,2,3}，大小为3。
目标：找到图 \(G\) 的最大团大小（或顶点集合）。
2. 整数规划建模
决策变量：
对每个顶点 \(i \in V\)，定义二进制变量：
\[x_i = \begin{cases} 1 & \text{如果顶点 } i \text{ 在团中} \\ 0 & \text{否则} \end{cases} \]
目标函数：
最大化团中的顶点数：
\[\max \sum_{i \in V} x_i \]
约束条件：
- 边约束（保证团内任意两点有边）：对每一对不相邻的顶点 \(i, j \in V\)，如果 \((i,j) \notin E\)，则它们不能同时被选入团中：
\[ x_i + x_j \leq 1 \quad \forall (i,j) \notin E \]
（注意：这是对非边的约束；如果两个顶点没有边，它们不能同时为1。）
- 变量类型：
\[ x_i \in \{0,1\} \quad \forall i \in V \]
示例模型（对上图）：
- 顶点集 \(V = \{1,2,3,4\}\)
- 非边集合：\((1,4) \notin E\), \((3,4) \notin E\)（因为图中没有边1-4和3-4）
- 整数规划：
\[ \begin{align*} \max \quad & x_1 + x_2 + x_3 + x_4 \\ \text{s.t.} \quad & x_1 + x_4 \leq 1 \quad (\text{因为 } (1,4) \notin E) \\ & x_3 + x_4 \leq 1 \quad (\text{因为 } (3,4) \notin E) \\ & x_i \in \{0,1\}, \quad i=1,2,3,4 \end{align*} \]
3. 线性规划松弛
松弛方法：
将整数约束 \(x_i \in \{0,1\}\) 替换为连续约束 \(0 \leq x_i \leq 1\)。这得到一个线性规划（LP）松弛问题：
\[\begin{align*} \max \quad & \sum_{i \in V} x_i \\ \text{s.t.} \quad & x_i + x_j \leq 1 \quad \forall (i,j) \notin E \\ & 0 \leq x_i \leq 1 \quad \forall i \in V \end{align*} \]
为什么松弛？：
- LP可以在多项式时间内求解（例如使用单纯形法或内点法）。
- LP的最优值提供了原整数规划最优值的上界（因为可行域扩大了）。
- 如果LP的解恰好是整数（所有 \(x_i\) 为0或1），那么它就是整数最优解。
示例求解：
对上面例子求解LP松弛：
- 约束：\(x_1 + x_4 \leq 1\), \(x_3 + x_4 \leq 1\), 且 \(0 \leq x_i \leq 1\)。
- 观察：为了最大化 \(x_1 + x_2 + x_3 + x_4\)，我们希望让 \(x_1, x_2, x_3, x_4\) 尽可能大。但约束限制了 \(x_4\)：从 \(x_1 + x_4 \leq 1\) 和 \(x_3 + x_4 \leq 1\)，如果 \(x_4 = 1\)，则 \(x_1 = 0\) 且 \(x_3 = 0\)，但 \(x_2\) 不受影响（因为2-4不是非边，所以没有约束 \(x_2 + x_4 \leq 1\)）。然而，注意团的要求是所有点对都要有边，但我们的约束只对非边进行了限制。LP松弛的解可能不是团！
- 实际上，LP松弛可能给出分数解。例如：设 \(x_1 = 0.5\), \(x_2 = 1\), \(x_3 = 0.5\), \(x_4 = 0.5\)。检查约束：
- \(x_1 + x_4 = 0.5 + 0.5 = 1 \leq 1\)（满足）
- \(x_3 + x_4 = 0.5 + 0.5 = 1 \leq 1\)（满足）
- 目标值：\(0.5+1+0.5+0.5=2.5\)。
- 这个分数解不是有效团（因为1和3之间虽然有边，但1和4、3和4没有边，所以不能同时选1、4或3、4）。但LP允许分数值，所以它给出了一个上界：最大团大小 ≤ 2.5 → 最大团大小 ≤ 2（因为整数解必须为整数）。但真实最大团大小是3！这说明LP松弛太弱了，我们需要加强它。
4. 切割平面（加强松弛）
问题：LP松弛的约束只考虑了非边，但忽略了团的另一个要求：选中的顶点集合必须是一个完全子图。因此，我们需要添加更多约束来排除无效的分数解。
团不等式（Clique Inequality）：
对于任意顶点子集 \(S \subseteq V\)，如果 \(S\) 不是团（即 \(S\) 的导出子图不是完全图），那么这些顶点不能全部被选中。更一般地：
- 设 \(C \subseteq V\) 是一个团（完全子图），那么对任意更大的集合，如果包含 \(C\) 但添加了与 \(C\) 中某个顶点无边连接的顶点，则违反团定义。
- 具体地：对于任意最大团 \(C\)（即不能再添加顶点形成更大团），以及任意顶点 \(v \notin C\) 且 \(v\) 不与 \(C\) 中所有顶点相邻，那么 \(C \cup \{v\}\) 不能是团。
如何自动生成切割？：
在分支切割法中，我们动态添加约束。常见切割包括：
- 三角不等式：对于任意三个顶点 \(i,j,k\)，如果它们两两之间不全有边（即不是三角形），则可以添加约束 \(x_i + x_j + x_k \leq 1\)（如果它们两两无边）或更复杂的约束。
- 更一般地：对于任意顶点子集 \(S\)，如果 \(S\) 的导出子图中缺失一些边（即不是完全图），则可以添加约束 \(\sum_{i \in S} x_i \leq \omega(S)\)，其中 \(\omega(S)\) 是 \(S\) 的导出子图的最大团大小。但计算 \(\omega(S)\) 本身是困难的。
实际常用切割：奇数洞不等式（Odd Hole Inequality） 和反团不等式（Anticlique Inequality）。
- 一个简单有效的切割：对于任意顶点子集 \(T \subseteq V\)，如果 \(T\) 的导出子图是补图中的一个团（即在原图中 \(T\) 内任意两点无边），那么原图中这些顶点不能同时被选入团中（因为团要求两点间有边）。所以：
\[ \sum_{i \in T} x_i \leq 1 \]
这实际上就是最初的边约束（对非边的约束）的推广（当 \(|T|=2\) 时就是边约束）。更大的 \(T\) 可以提供更强的约束。
示例中如何加强？：
在例子中，考虑集合 \(T = \{1,4\}\) 和 \(T = \{3,4\}\) 已经是边约束。但还有集合 \(T = \{1,3,4\}\)：在原图中，1-3有边，但1-4无边、3-4无边，所以 \(T\) 的导出子图不是完全图（缺失边1-4和3-4）。实际上，\(T\) 的补图（将原图无边变有边、有边变无边）中，1-4和3-4有边，1-3无边，所以补图中 \(T\) 是一个团（因为任意两点都有边？检查：补图中1-4有边，3-4有边，但1-3无边？所以不是团）。需要小心：我们需要的是原图中 \(T\) 内任意两点都没有边，这样在补图中 \(T\) 才是团。这里1-3有边，所以不满足。所以不能直接用 \(\sum_{i \in \{1,3,4\}} x_i \leq 1\)。
尝试另一个集合：\(T = \{1,4\}\) 已经约束了。但LP分数解 \(x_1=0.5, x_2=1, x_3=0.5, x_4=0.5\) 中，顶点子集 {1,3,4} 的和是1.5，而它们不能同时被选（因为缺失边1-4和3-4），但我们的约束只分别限制了1+4≤1和3+4≤1，允许1和3同时为0.5。为了排除这个分数解，可以添加约束：
\[x_1 + x_3 + x_4 \leq 1 \]
因为{1,3,4}中任意两点不全有边（1-3有边，但1-4和3-4没有），所以它们不能同时被选入团中。这个约束在整数解中成立（因为最多只能选其中一个），但在分数解中被违反（1+3+4=1.5 > 1）。添加这个切割后，LP重新求解，可能得到更好的上界。
切割添加过程：
- 求解当前LP松弛。
- 检查当前LP分数解是否违反任何团不等式（例如，找一个顶点集合 \(S\) 使得 \(\sum_{i \in S} x_i > 1\) 且 \(S\) 在原图中不是完全子图）。
- 如果找到这样的不等式，将其添加到LP中，重新求解。
- 重复直到没有可添加的切割或达到迭代限制。
5. 分支定界框架
当LP松弛的解仍有分数变量时，我们需要分支。
分支：
选择一个分数变量 \(x_k\)（其值在0和1之间），创建两个子问题：
- 子问题1：固定 \(x_k = 0\)（不选顶点k）。
- 子问题2：固定 \(x_k = 1\)（选顶点k）。
定界：
对每个子问题求解LP松弛（可能添加切割），得到上界。同时维护一个全局下界（当前找到的最大团大小）。
剪枝：
- 如果子问题的LP上界 ≤ 全局下界，则剪枝（不可能得到更好的整数解）。
- 如果子问题的LP解是整数且目标值大于全局下界，更新下界。
- 如果子问题的LP解是整数但目标值不大于下界，剪枝。
搜索策略：
常用深度优先搜索（DFS）或最佳上界优先（选择上界最大的子问题先处理）。
示例完整分支切割过程：
初始问题（P0）：
\[\begin{align*} \max \quad & x_1 + x_2 + x_3 + x_4 \\ \text{s.t.} \quad & x_1 + x_4 \leq 1 \\ & x_3 + x_4 \leq 1 \\ & 0 \leq x_i \leq 1 \end{align*} \]
求解LP松弛得：\(x_1=0.5, x_2=1, x_3=0.5, x_4=0.5\)，目标值=2.5。不是整数解。
添加切割：检测到集合 {1,3,4} 违反团不等式（因为1-4、3-4无边），添加 \(x_1 + x_3 + x_4 \leq 1\)。
重新求解LP（P0'）：
\[\begin{align*} \max \quad & x_1 + x_2 + x_3 + x_4 \\ \text{s.t.} \quad & x_1 + x_4 \leq 1 \\ & x_3 + x_4 \leq 1 \\ & x_1 + x_3 + x_4 \leq 1 \\ & 0 \leq x_i \leq 1 \end{align*} \]
求解得：最优解可能是 \(x_1=0, x_2=1, x_3=0, x_4=1\)（目标值=2）或其他等价解。现在目标值=2，上界下降到2。
分支：选择分数变量（但现在解是整数？实际上，添加切割后可能得到多个最优解。假设我们得到分数解，但这里为了简单，假设得到整数解 \(x=(0,1,0,1)\) 目标=2。但注意 {2,4} 不是团（因为2-4无边），所以这个解违反团的定义？等等，我们的约束只保证了非边约束，但 {2,4} 中2和4不是非边（图中没有边2-4，但也没有约束 \(x_2 + x_4 \leq 1\) 因为2-4不是非边？实际上，非边是指原图中没有边的顶点对。图中2-4没有边，所以应该是非边！我之前的边列表写错了，更正：边是 (1,2), (1,3), (2,3), (3,4)？不，原例是边 (1,2), (1,3), (2,3), (2,4)。所以2-4有边！抱歉，纠正：边集合包括(2,4)。所以 {2,4} 有边，但 {2,4} 的导出子图只有一条边，所以不是团（因为团需要所有点对都有边，这里只有两个点，所以需要一条边，确实有边，所以 {2,4} 是团？是的，两个点的团就是一条边。但注意，团要求任意两点有边，对于两个顶点，只要它们之间有边就是团。所以 {2,4} 是大小为2的团。但最大团是 {1,2,3} 大小为3。
所以原问题中，非边应该是 (1,4) 和 (3,4)？检查：顶点4与1无边，与3无边，但与2有边。所以非边是 (1,4) 和 (3,4)。所以约束 \(x_1 + x_4 \leq 1\) 和 \(x_3 + x_4 \leq 1\) 正确。
现在LP解 \(x=(0,1,0,1)\) 满足所有约束：\(x_1+x_4=0+1=1\), \(x_3+x_4=0+1=1\), \(x_1+x_3+x_4=0+0+1=1\)。所以是可行解。但这是整数解，对应团 {2,4}（大小为2）。目标值=2。
分支定界：
- 全局下界初始为2（来自整数解 {2,4}）。
- 上界是2（LP松弛值），所以可能已经最优？但最大团实际是3。说明我们的LP松弛加上切割后上界是2，但真实最优是3，这意味着我们的切割太强了？检查：我们添加的切割 \(x_1 + x_3 + x_4 \leq 1\) 是否正确？对于整数解，集合 {1,3,4} 确实不能同时选（因为1-4和3-4无边），所以最多选一个，约束成立。但最大团 {1,2,3} 中不包含4，所以不影响。但为什么上界是2？因为LP目标值=2，说明松弛后最优值只有2，小于真实最优值3。这不可能，因为松弛应该给出上界，上界应该≥最优值。矛盾意味着我们的模型或求解有误。
纠正：我意识到错误：我们的目标函数是最大化顶点数，但约束可能过强了。检查约束 \(x_1 + x_3 + x_4 \leq 1\)：对于最大团 {1,2,3}，x1=1, x3=1, x4=0，满足约束（1+1+0=2>1？违反！）。所以这个切割是错误的！因为 {1,3,4} 中1和3之间有边，所以如果只选1和3（不选4）是允许的，但约束禁止了同时选1和3。所以正确切割应该是针对不是完全图的顶点集，即如果集合中缺失至少一条边，则不能所有顶点都被选。但切割形式不是简单的和≤1，而是要根据缺失边的数量。
更精确的切割：对于顶点集 S，如果 S 的导出子图不是完全图，则至少有一个缺失边的顶点对不能被同时选。但如何写成线性约束？一种方法是使用团不等式：对于任意团 C 和顶点 v 与 C 中至少一个顶点无边，则不能同时选 C 中所有顶点和 v。但更通用的切割需要更复杂的构造。
由于时间有限，我们转向标准分支切割法常用策略：在分支定界树中，对每个节点求解LP松弛，然后尝试添加有效不等式（如三角不等式、团不等式）来收紧上界，然后分支。
简化示例：
假设我们跳过切割直接分支。初始LP松弛目标=2.5。分支 x4=0 和 x4=1。
- 分支 x4=0：问题变为
\[ \max x_1+x_2+x_3 \quad \text{s.t.} \quad 0 \leq x_i \leq 1, \quad x_1+x_4\leq1 \text{变成} x_1\leq1, \quad x_3+x_4\leq1 \text{变成} x_3\leq1. \]
所以约束只有边界，最优解 x1=1, x2=1, x3=1, x4=0，目标=3。这是整数解，对应团 {1,2,3}。更新下界=3。
- 分支 x4=1：问题变为
\[ \max x_1+x_2+x_3+1 \quad \text{s.t.} \quad x_1+1\leq1 \Rightarrow x_1=0, \quad x_3+1\leq1 \Rightarrow x_3=0, \quad 0\leq x_i\leq1. \]
所以 x1=0, x3=0, x2≤1, 最优解 x2=1，目标=2。整数解 {2,4}，目标=2 < 下界3，剪枝。
所以最优解是 {1,2,3}，大小=3。
6. 算法总结
分支切割法求解最大团问题的步骤：
- 初始化：建立整数规划模型。
- 松弛：求解LP松弛，得到上界。
- 切割生成：检查LP解，寻找违反的有效不等式（如团不等式、三角不等式等），添加到模型中，重新求解LP，重复直到无法添加切割或达到迭代限制。
- 分支：如果LP解不是整数，选择一个分数变量，分支为两个子问题（固定为0或1）。
- 定界与剪枝：对每个子问题，递归应用步骤2-4。维护全局下界，如果子问题上界≤下界则剪枝。
- 终止：当所有节点被处理，下界即为最优解。
关键点：
- 切割平面可以显著收紧上界，减少分支节点数量。
- 分支策略（如选择分数变量）影响搜索效率。
- 最大团问题是NP难的，分支切割法在实际中用于中小规模图或具有特殊结构的图。
通过以上步骤，我们可以系统性地求解图最大团问题。希望这个讲解对你有所帮助！