基于线性规划的图最小顶点覆盖问题的分支定价法（Branch-and-Price）求解示例
字数 9310 2025-12-15 20:52:05

基于线性规划的图最小顶点覆盖问题的分支定价法（Branch-and-Price）求解示例

1. 问题描述

最小顶点覆盖问题是图论中的一个经典 NP-hard 问题。给定一个无向图 G=(V, E)，其中 V 是顶点集，E 是边集。一个顶点覆盖是一个顶点子集 S ⊆ V，使得图中的每条边至少有一个端点在 S 中。最小顶点覆盖问题的目标是找到一个规模最小的顶点覆盖，即最小化 |S|。

分支定价法（Branch-and-Price）是解决大规模整数线性规划问题的强大方法，尤其适用于其线性规划松弛可以通过列生成算法高效求解的问题。该方法结合了分支定界（Branch-and-Bound）框架和列生成（Column Generation）技术。我们将通过一个具体的例子，展示如何用分支定价法精确求解最小顶点覆盖问题。

2. 建立整数线性规划主问题模型

我们可以为每个顶点引入一个0-1决策变量：

  • \(x_v = 1\) 如果顶点 v 被选入覆盖集 S，否则 \(x_v = 0\)。

那么，最小顶点覆盖问题的标准整数线性规划模型为：

\[\begin{aligned} \min \quad & \sum_{v \in V} x_v \\ \text{s.t.} \quad & x_u + x_v \geq 1, \quad \forall (u,v) \in E \\ & x_v \in \{0, 1\}, \quad \forall v \in V \end{aligned} \tag{IP-MVC} \]

这是一个紧凑的、易于理解的模型。然而，为了应用分支定价法，我们需要将其重新建模为集合覆盖问题（Set Cover Problem）的形式，这会导致变量数（列数）非常多（指数级），但约束数较少。

重构模型（主问题）：
我们可以从另一个角度思考：一个顶点覆盖 S 可以看作是一个“覆盖了所有边的顶点集合”。我们可以将整个顶点集 V 的每个子集 S 视为一个潜在的“覆盖模式”。但是，我们只关心那些能覆盖所有边的可行子集，即 S 是 G 的一个顶点覆盖。然而，要列出所有可行覆盖模式是困难的。

更实用的方法是利用对偶思想。我们的原始模型（IP-MVC）的对偶问题是最大匹配问题。在分支定价中，我们通常用 Dantzig-Wolfe 分解将原问题分解为一个“主问题”（负责保证所有边被覆盖）和多个“子问题”（负责生成可行的、成本更低的覆盖“模式”或“列”）。

对于最小顶点覆盖，一个巧妙的分解方法是将其建模为一个集合覆盖问题，其中：

  • 元素：图中的每条边 \(e \in E\)。
  • 集合：每个顶点 \(v \in V\) 定义了一个集合，包含所有与顶点 v 关联的边，即集合 \(\delta(v) = \{ e \in E : e \text{ 与 } v \text{ 关联} \}\)。
  • 选择顶点 v 的成本是 1。

那么，最小顶点覆盖问题等价于：选择一些顶点（集合），使得每条边（元素）至少被一个选中的集合覆盖，且最小化选中集合的数量。

这可以写成一个集合覆盖整数线性规划模型：

\[\begin{aligned} \min \quad & \sum_{v \in V} x_v \\ \text{s.t.} \quad & \sum_{v: e \in \delta(v)} x_v \geq 1, \quad \forall e \in E \quad \text{(覆盖约束)}\\ & x_v \in \{0, 1\}, \quad \forall v \in V \end{aligned} \tag{IP-SC} \]

这个模型和之前的（IP-MVC）其实是等价的。但为了演示分支定价，我们考虑一个更“宽松”的主问题模型，允许使用顶点覆盖的“组合模式”。

扩展模型：
假设我们能够枚举出图 G 的所有极大独立集 \(I_1, I_2, ..., I_k\)。因为一个图的最小顶点覆盖是其补图最大独立集的补集，但这里我们用另一种方式：任何一个顶点集 S 是顶点覆盖，当且仅当它的补集 \(V \setminus S\) 是一个独立集（即内部没有边）。那么，任何顶点覆盖 S 都可以表示为某个独立集 I 的补集。但这在实际列生成中不直接使用。更常见的用于分支定价的模型，是直接将顶点覆盖 S 本身作为一个“列”或“模式”加入主问题。

一个更通用的主问题模型是：

\[\begin{aligned} \min \quad & \sum_{p \in \Omega} c_p \lambda_p \\ \text{s.t.} \quad & \sum_{p \in \Omega} a_{ep} \lambda_p \geq 1, \quad \forall e \in E \quad \text{(每条边必须被覆盖)}\\ & \lambda_p \in \{0, 1\}, \quad \forall p \in \Omega \end{aligned} \tag{MP} \]

其中：

  • \(\Omega\) 是所有可行顶点覆盖（模式）的集合。对于最小顶点覆盖，每个模式 p 就是一个顶点覆盖 S_p ⊆ V。
  • \(c_p = |S_p|\)，即模式 p 的成本（覆盖的顶点数）。
  • \(a_{ep} = 1\) 如果边 e 的至少一个端点在 S_p 中，否则为 0。
  • \(\lambda_p = 1\) 表示选择模式 p。

这个模型的问题是 \(\Omega\) 可能非常庞大（所有顶点覆盖的数量是指数级的）。我们无法显式地列出所有 \(\lambda_p\)。列生成的思想是：开始时只考虑一个很小的可行列子集 \(\Omega' \subset \Omega\)，求解这个受限主问题（RMP），然后利用对偶信息，通过求解一个定价子问题（Pricing Subproblem）来寻找一个具有负检验数（在最小化问题中，即有可能降低目标函数）的新列（新模式）加入 RMP，迭代直到找不到这样的列为止。

3. 列生成过程：受限主问题与定价子问题

步骤 3.1：初始化受限主问题
我们从一个简单可行的初始列集合开始。一个简单的方法是，为图中的每条边 (u, v)，生成一个只包含其两个端点的覆盖模式。但更简单的初始集合是：每个顶点单独作为一个覆盖模式（当然，单个顶点可能无法覆盖所有边，所以初始 RMP 可能不可行）。一个保证可行的初始化是：选择所有顶点组成的覆盖模式（即 \(S = V\)）。但这样目标值很差。另一个更好的初始化是使用一个启发式算法（例如贪婪算法）找到一个可行的顶点覆盖 S_h，将其作为一个初始列加入 RMP。为了满足 RMP 的可行性，我们可能需要多个列。一个标准技巧是添加人工变量（或使用两阶段法），但为了简化，我们假设初始启发式找到了一个可行覆盖，我们将其分解为多个列，或者更简单地，我们使用一组覆盖所有边的“小”覆盖模式，例如，对每条边，添加一个覆盖它的最小覆盖模式（即包含其两个端点的模式）。这样，初始 RMP 的行数（|E|）和初始列数（O(|E|) 或 O(|V|)）是可控的。

假设我们有一个初始的可行列集合 \(\Omega'\)，我们求解 RMP 的线性规划松弛（LP relaxation），即松弛 \(\lambda_p \in [0, 1]\)。

步骤 3.2：求解定价子问题（寻找负检验数列）
设求解 RMP 的 LP 松弛后，得到最优对偶变量 \(\pi_e \geq 0\) 对应于每条边 e 的覆盖约束。

在最小化问题中，对于一个新模式（新列）p（对应一个新的顶点覆盖 S_p），其检验数（Reduced Cost）为：

\[\overline{c}_p = c_p - \sum_{e \in E} a_{ep} \pi_e \]

其中 \(c_p = |S_p|\)，\(a_{ep} = 1\) 当且仅当边 e 被 S_p 覆盖。

如果存在一个模式 p 使得 \(\overline{c}_p < 0\)，那么将这个列加入 RMP 有可能改进目标值。

我们的定价子问题就是：找到一个顶点覆盖 S （即一个满足每条边至少有一个端点在 S 中的集合），使得检验数 \(\overline{c}(S) = |S| - \sum_{e \in E} I_{e \in E(S)} \pi_e\) 最小化，其中 \(I_{e \in E(S)}\) 是指示函数，当边 e 至少有一个端点在 S 中时为 1。

\[\sum_{e \in E} I_{e \in E(S)} \pi_e = \sum_{e \in E} \pi_e \cdot [\text{e 被 S 覆盖}] \]

注意，一条边 e=(u,v) 被 S 覆盖当且仅当 \(u \in S\) 或 \(v \in S\)。因此，这个和可以重新表述。我们为每个顶点引入 0-1 变量 \(y_v\) 表示顶点 v 是否在 S 中。那么，边 e=(u,v) 被覆盖的条件是 \(y_u + y_v \geq 1\)。于是，定价子问题可以建模为如下整数线性规划：

\[\begin{aligned} \min \quad & \sum_{v \in V} y_v - \sum_{e=(u,v) \in E} \pi_e \cdot z_e \\ \text{s.t.} \quad & y_u + y_v \geq 1, \quad \forall e=(u,v) \in E \\ & z_e \leq y_u, \quad \forall e=(u,v) \in E \\ & z_e \leq y_v, \quad \forall e=(u,v) \in E \\ & z_e \geq 0, \quad \forall e \in E \\ & y_v \in \{0, 1\}, \quad \forall v \in V \end{aligned} \tag{SP} \]

这里 \(z_e\) 是一个连续变量，用于线性化“边 e 是否被覆盖”的乘积项。事实上，由于目标是最小化，且 \(\pi_e \geq 0\)，在最优解中，\(z_e\) 会取到尽可能大的值，即 \(z_e = \min(y_u, y_v)\)。但边被覆盖的条件是 \(y_u + y_v \geq 1\)，所以如果 \(y_u=0\) 且 \(y_v=0\)，则约束不满足。如果 \(y_u=1\) 或 \(y_v=1\)，则 \(\min(y_u, y_v)\) 可能是 0 或 1。实际上，对于定价子问题，我们可以更直接地理解：目标是 \(\sum_{v} y_v - \sum_{e} \pi_e \cdot [\text{e 被覆盖}]\)。由于 \([\text{e 被覆盖}] = 1\) 当 \(y_u + y_v \geq 1\)，我们可以将其线性化，或者注意到，对于一个给定的覆盖 S（由 y 决定），其检验数是 \(|S| - \sum_{e: e 被 S 覆盖} \pi_e\)。定价子问题就是要找到检验数最小的覆盖 S。这是一个加权版本的最小顶点覆盖问题，其中选择顶点 v 的成本是 1，而覆盖边 e 可以获得“奖励” \(\pi_e\)。这正是最小权顶点覆盖问题，可以通过整数规划求解（对于一般图是 NP-hard 的，但我们可以用 ILP 求解器，或者利用二分图上的多项式时间算法如果原图是二分图）。在我们的分支定价框架中，子问题本身可能也是 NP-hard 的，但我们通常用一个整数规划求解器来精确求解它，因为它的规模是原图规模，而不是主问题规模。

步骤 3.3：列生成迭代

  1. 求解当前的 RMP（线性规划松弛），得到最优解 \(\lambda^*\) 和对偶变量 \(\pi^*\)。
  2. 将 \(\pi^*\) 代入定价子问题（SP），求解 SP，得到最小检验数 \(\overline{c}_{min}\) 和对应的新列（即新的顶点覆盖 S）。
  3. 如果 \(\overline{c}_{min} < 0\)（通常设置一个小的负容差，如 -1e-6），则将这个新列添加到 RMP 中（即添加变量 \(\lambda_{new}\)，其系数 \(c_{new} = |S|\)，\(a_{e, new} = 1\) 当边 e 被 S 覆盖）。返回步骤1。
  4. 如果 \(\overline{c}_{min} \geq 0\)，则当前 RMP 的 LP 松弛已求解到最优（即没有能改进目标的新列）。我们得到了原问题（MP）的 LP 松弛的最优解。

4. 分支定价：处理整数性

当列生成迭代停止后，我们得到了 MP 的 LP 松弛最优解 \(\lambda^*\)。如果 \(\lambda^*\) 的所有分量都是整数（0 或 1），那么我们就得到了原最小顶点覆盖问题的最优解（通过所选模式的并集，注意可能有多个模式被选中，但目标函数是所选模式的成本和，而每个模式本身就是一个完整的顶点覆盖。在集合覆盖模型中，通常一个解是由多个模式组成的，但在这里，由于每个模式本身就是一个完整的顶点覆盖，选择多个覆盖的并集可能不是最小覆盖。实际上，我们需要保证最终解是一个单一的覆盖。在经典的集合覆盖问题的分支定价中，解可以是多个模式的并集，它们共同覆盖所有元素。但在我们重新建模的顶点覆盖问题中，一个模式本身就是一个完整覆盖，所以我们希望选择一个模式即可。但这样，主问题就变成了从众多覆盖中选择一个最好的。这可以建模为：

\[\min \{ c_p : p \in \Omega \} \]

这本质上是一个枚举问题。为了应用分支定价，我们通常允许解是多个模式的凸组合，但在整数解中，应该只有一个模式被选中。这可以通过在分支定界树上添加约束来实现，例如分支决策强制某个顶点是否在覆盖中。这引出了第二种，也是更常用的分支策略。

在实际的分支定价算法中，更常见的做法是在主问题中使用原始的顶点变量 \(x_v\) 的分解。我们可以将原问题（IP-MVC）用 Dantzig-Wolfe 分解重新表述，其中子问题是求解某个结构下的最小顶点覆盖，但这样比较复杂。另一种更直接的方法是我们不改变原变量，但用列生成来动态生成“有效不等式”，而不是新模式。但对于最小顶点覆盖，一个更实用的分支定价实现方式是：

  1. 主问题 使用原始的边覆盖约束，但变量是 \(x_v\)。
  2. 定价 不是生成新的变量，而是生成“割平面”（cut），例如子图不等式、团不等式等，来加强线性规划松弛。但这属于分支切割（Branch-and-Cut）的范畴。

为了保持示例的清晰，我们这里演示一个经典的分支定价思路，但应用于一个不同的、但更适合的模型：集合覆盖公式，并允许解是多个模式的并集。在这种情况下，每个模式 p 不一定需要覆盖所有边，但所有被选模式的并集必须覆盖所有边。每个模式 p 可以定义为某个顶点的子集，其成本是子集大小。主问题（MP）如之前所示。如果 LP 松弛解 \(\lambda^*\) 分数，我们需要分支。

分支策略：
常见的分支策略是对原始变量 \(x_v\) 进行分支，即使它们没有显式出现在主问题中。因为 \(x_v = \sum_{p \in \Omega: v \in S_p} \lambda_p\)，我们可以计算每个顶点 v 的“分数值”。选择分数值最接近 0.5 的顶点 v*，创建两个分支：

  • 分支1：强制 \(x_{v*} = 1\)（即 v* 必须在覆盖中）。这对应于在定价子问题中，强制 \(y_{v*} = 1\)。
  • 分支2：强制 \(x_{v*} = 0\)（即 v* 不能在覆盖中）。这对应于在定价子问题中，强制 \(y_{v*} = 0\)。

在每个分支节点，我们需要在新的限制下（定价子问题添加了 \(y_{v*} = 1\) 或 \(y_{v*} = 0\) 的约束）重新进行列生成，求解受限主问题的 LP 松弛。分支定界树不断扩展，直到所有节点都探查完毕（被剪枝或找到整数解）。记录找到的最优整数解。

5. 示例图与求解流程演示

考虑一个简单的无向图 G = (V, E)，V = {1, 2, 3, 4}，E = {(1,2), (2,3), (3,4), (1,4)}。这是一个4个顶点的环 C4。

步骤1：初始受限主问题 (RMP)
初始列：我们可以用最简单的覆盖：整个顶点集 V = {1,2,3,4} 作为一个模式 p0，成本 c0=4，显然它覆盖所有边。初始 RMP 只有一个变量 λ0。
初始 RMP：

\[\begin{aligned} \min \quad & 4\lambda_0 \\ \text{s.t.} \quad & \lambda_0 \geq 1 \quad \text{(对于所有边 e1,e2,e3,e4)} \\ & \lambda_0 \geq 0 \end{aligned} \]

最优解 λ0=1，目标值=4。对偶变量：每条边的对偶值 π_e 都等于 1？ 不，这里约束是四个独立的约束，但只有一个变量。对偶问题为 max ∑ π_e, s.t. ∑ π_e ≤ 4, π_e ≥ 0。最优解可以是 π_e = 1 对于所有四条边，对偶目标值=4。我们得到对偶变量 π = (1,1,1,1) 对于边 e1(1,2), e2(2,3), e3(3,4), e4(1,4)。

步骤2：第一次定价子问题
我们需要找到一个顶点覆盖 S，使得检验数 \(\overline{c} = |S| - \sum_{e: e 被 S 覆盖} \pi_e\) 最小。
给定 π_e = 1 对所有边，所以 \(\sum_{e: e 被 S 覆盖} \pi_e\) 等于 S 覆盖的边数。
我们求解子问题（SP）：最小化 |S| - (S覆盖的边数)。
对于图 C4，最小顶点覆盖的大小是2（例如 {1,3} 或 {2,4}）。
如果我们取 S = {1,3}，则覆盖的边是 (1,2), (1,4), (2,3), (3,4) 全部四条边。所以检验数 = 2 - 4 = -2。
所以找到了一个检验数为负的列（模式 p1 = {1,3}, 成本=2）。

步骤3：添加新列，求解新 RMP
RMP 现在有两个变量 λ0 (V) 和 λ1 ({1,3})。约束为每条边必须被覆盖。
边覆盖情况：

  • 模式 p0: 覆盖所有边。
  • 模式 p1: 覆盖边 e1, e2, e3, e4（全部）。
    新的 RMP：

\[\begin{aligned} \min \quad & 4\lambda_0 + 2\lambda_1 \\ \text{s.t.} \quad & \lambda_0 + \lambda_1 \geq 1 \quad \text{(每条边，因为两个模式都覆盖所有边)} \\ & \lambda_0, \lambda_1 \geq 0 \end{aligned} \]

实际上，四条边的约束是相同的：λ0 + λ1 ≥ 1。所以等价于一个约束。
最优解：取 λ1=1, λ0=0，目标值=2。对偶变量：四条边共用一个约束，对偶变量 π_e 的和受主约束限制。对偶问题：max ∑ π_e, s.t. ∑ π_e ≤ 4, ∑ π_e ≤ 2, π_e ≥ 0。最优解是让 ∑ π_e 尽可能大，但受第二个约束限制（对应 λ1），所以 ∑ π_e = 2。由于对称性，可以取每条边的 π_e = 0.5。

步骤4：第二次定价子问题
对偶变量 π = (0.5, 0.5, 0.5, 0.5)。
我们需要找到覆盖 S，最小化 |S| - ∑_{e covered} 0.5 = |S| - 0.5 * (# 被覆盖的边数)。
尝试 S = {1,3}，检验数 = 2 - 0.54 = 0。
尝试 S = {2,4}，检验数 = 2 - 0.54 = 0。
尝试 S = {1,2,3}，检验数 = 3 - 0.5*4 = 1 （更差）。
没有检验数为负的列了（最小检验数为0）。所以当前 RMP 的 LP 松弛已最优，目标值=2，解 λ1=1, λ0=0。这是一个整数解！对应的覆盖是模式 p1 = {1,3}，大小2。

步骤5：得到整数最优解
因为 LP 松弛解已经是整数，且我们求解的是 MP 的 LP 松弛，而这个解对应于一个单一的覆盖模式，所以它就是原最小顶点覆盖问题的最优解。不需要分支。

所以，对于图 C4，最小顶点覆盖的大小是2，例如 {1,3}。

6. 总结与扩展

这个示例演示了如何用分支定价法求解最小顶点覆盖问题：

  1. 建模：将问题构建为大规模整数线性规划主问题（MP），其变量对应可行的顶点覆盖模式。
  2. 列生成：在分支定界树的每个节点，求解 MP 的 LP 松弛。通过求解一个定价子问题（一个带奖励的最小顶点覆盖问题）来生成改进的新列，迭代直到 LP 松弛最优。
  3. 分支：如果 LP 松弛解分数，则基于原始顶点变量进行分支（例如，强制某个顶点在或不在覆盖中），在每个子节点重新进行列生成。
  4. 界限与剪枝：利用 LP 松弛解提供的下界，结合当前最好整数解的上界，进行剪枝。

这个方法的优势在于，主问题可能只有少量约束（边数），而复杂的组合结构被隐藏在定价子问题中。对于某些图类（如二分图），定价子问题可以在多项式时间内求解（例如用 König 定理和最大匹配算法），这使得分支定价法非常高效。对于一般图，定价子问题是 NP-hard 的，但仍可以用整数规划求解器在合理规模的图上求解。分支定价法通过避免显式枚举所有可能的覆盖模式，能够处理大规模的最小顶点覆盖问题实例。

基于线性规划的图最小顶点覆盖问题的分支定价法（Branch-and-Price）求解示例 1. 问题描述 最小顶点覆盖问题是图论中的一个经典 NP-hard 问题。给定一个无向图 G=(V, E)，其中 V 是顶点集，E 是边集。一个顶点覆盖是一个顶点子集 S ⊆ V，使得图中的每条边至少有一个端点在 S 中。最小顶点覆盖问题的目标是找到一个规模最小的顶点覆盖，即最小化 |S|。 分支定价法（Branch-and-Price）是解决大规模整数线性规划问题的强大方法，尤其适用于其线性规划松弛可以通过列生成算法高效求解的问题。该方法结合了分支定界（Branch-and-Bound）框架和列生成（Column Generation）技术。我们将通过一个具体的例子，展示如何用分支定价法精确求解最小顶点覆盖问题。 2. 建立整数线性规划主问题模型 我们可以为每个顶点引入一个0-1决策变量： \( x_ v = 1 \) 如果顶点 v 被选入覆盖集 S，否则 \( x_ v = 0 \)。 那么，最小顶点覆盖问题的标准整数线性规划模型为： \[ \begin{aligned} \min \quad & \sum_ {v \in V} x_ v \\ \text{s.t.} \quad & x_ u + x_ v \geq 1, \quad \forall (u,v) \in E \\ & x_ v \in \{0, 1\}, \quad \forall v \in V \end{aligned} \tag{IP-MVC} \] 这是一个紧凑的、易于理解的模型。然而，为了应用分支定价法，我们需要将其重新建模为集合覆盖问题（Set Cover Problem）的形式，这会导致变量数（列数）非常多（指数级），但约束数较少。 重构模型（主问题）： 我们可以从另一个角度思考：一个顶点覆盖 S 可以看作是一个“覆盖了所有边的顶点集合”。我们可以将整个顶点集 V 的每个子集 S 视为一个潜在的“覆盖模式”。但是，我们只关心那些能覆盖所有边的可行子集，即 S 是 G 的一个顶点覆盖。然而，要列出所有可行覆盖模式是困难的。 更实用的方法是利用 对偶思想 。我们的原始模型（IP-MVC）的对偶问题是最大匹配问题。在分支定价中，我们通常用 Dantzig-Wolfe 分解将原问题分解为一个“主问题”（负责保证所有边被覆盖）和多个“子问题”（负责生成可行的、成本更低的覆盖“模式”或“列”）。 对于最小顶点覆盖，一个巧妙的分解方法是将其建模为一个集合覆盖问题，其中： 元素 ：图中的每条边 \( e \in E \)。 集合 ：每个顶点 \( v \in V \) 定义了一个集合，包含所有与顶点 v 关联的边，即集合 \( \delta(v) = \{ e \in E : e \text{ 与 } v \text{ 关联} \} \)。 选择顶点 v 的成本是 1。 那么，最小顶点覆盖问题等价于：选择一些顶点（集合），使得每条边（元素）至少被一个选中的集合覆盖，且最小化选中集合的数量。 这可以写成一个集合覆盖整数线性规划模型： \[ \begin{aligned} \min \quad & \sum_ {v \in V} x_ v \\ \text{s.t.} \quad & \sum_ {v: e \in \delta(v)} x_ v \geq 1, \quad \forall e \in E \quad \text{(覆盖约束)}\\ & x_ v \in \{0, 1\}, \quad \forall v \in V \end{aligned} \tag{IP-SC} \] 这个模型和之前的（IP-MVC）其实是等价的。但为了演示分支定价，我们考虑一个更“宽松”的主问题模型，允许使用顶点覆盖的“组合模式”。 扩展模型： 假设我们能够枚举出图 G 的所有 极大独立集 \( I_ 1, I_ 2, ..., I_ k \)。因为一个图的最小顶点覆盖是其补图最大独立集的补集，但这里我们用另一种方式：任何一个顶点集 S 是顶点覆盖，当且仅当它的补集 \( V \setminus S \) 是一个独立集（即内部没有边）。那么，任何顶点覆盖 S 都可以表示为某个独立集 I 的补集。但这在实际列生成中不直接使用。更常见的用于分支定价的模型，是直接将顶点覆盖 S 本身作为一个“列”或“模式”加入主问题。 一个更通用的主问题模型是： \[ \begin{aligned} \min \quad & \sum_ {p \in \Omega} c_ p \lambda_ p \\ \text{s.t.} \quad & \sum_ {p \in \Omega} a_ {ep} \lambda_ p \geq 1, \quad \forall e \in E \quad \text{(每条边必须被覆盖)}\\ & \lambda_ p \in \{0, 1\}, \quad \forall p \in \Omega \end{aligned} \tag{MP} \] 其中： \( \Omega \) 是所有可行顶点覆盖（模式）的集合。对于最小顶点覆盖，每个模式 p 就是一个顶点覆盖 S_ p ⊆ V。 \( c_ p = |S_ p| \)，即模式 p 的成本（覆盖的顶点数）。 \( a_ {ep} = 1 \) 如果边 e 的至少一个端点在 S_ p 中，否则为 0。 \( \lambda_ p = 1 \) 表示选择模式 p。 这个模型的问题是 \( \Omega \) 可能非常庞大（所有顶点覆盖的数量是指数级的）。我们无法显式地列出所有 \( \lambda_ p \)。列生成的思想是：开始时只考虑一个很小的可行列子集 \( \Omega' \subset \Omega \)，求解这个受限主问题（RMP），然后利用对偶信息，通过求解一个 定价子问题 （Pricing Subproblem）来寻找一个具有 负检验数 （在最小化问题中，即有可能降低目标函数）的新列（新模式）加入 RMP，迭代直到找不到这样的列为止。 3. 列生成过程：受限主问题与定价子问题 步骤 3.1：初始化受限主问题 我们从一个简单可行的初始列集合开始。一个简单的方法是，为图中的每条边 (u, v)，生成一个只包含其两个端点的覆盖模式。但更简单的初始集合是：每个顶点单独作为一个覆盖模式（当然，单个顶点可能无法覆盖所有边，所以初始 RMP 可能不可行）。一个保证可行的初始化是：选择所有顶点组成的覆盖模式（即 \( S = V \)）。但这样目标值很差。另一个更好的初始化是使用一个启发式算法（例如贪婪算法）找到一个可行的顶点覆盖 S_ h，将其作为一个初始列加入 RMP。为了满足 RMP 的可行性，我们可能需要多个列。一个标准技巧是添加人工变量（或使用两阶段法），但为了简化，我们假设初始启发式找到了一个可行覆盖，我们将其分解为多个列，或者更简单地，我们使用一组覆盖所有边的“小”覆盖模式，例如，对每条边，添加一个覆盖它的最小覆盖模式（即包含其两个端点的模式）。这样，初始 RMP 的行数（|E|）和初始列数（O(|E|) 或 O(|V|)）是可控的。 假设我们有一个初始的可行列集合 \( \Omega' \)，我们求解 RMP 的线性规划松弛（LP relaxation），即松弛 \( \lambda_ p \in [ 0, 1 ] \)。 步骤 3.2：求解定价子问题（寻找负检验数列） 设求解 RMP 的 LP 松弛后，得到最优对偶变量 \( \pi_ e \geq 0 \) 对应于每条边 e 的覆盖约束。 在最小化问题中，对于一个新模式（新列）p（对应一个新的顶点覆盖 S_ p），其检验数（Reduced Cost）为： \[ \overline{c} p = c_ p - \sum {e \in E} a_ {ep} \pi_ e \] 其中 \( c_ p = |S_ p| \)，\( a_ {ep} = 1 \) 当且仅当边 e 被 S_ p 覆盖。 如果存在一个模式 p 使得 \( \overline{c}_ p < 0 \)，那么将这个列加入 RMP 有可能改进目标值。 我们的定价子问题就是：找到一个顶点覆盖 S （即一个满足每条边至少有一个端点在 S 中的集合），使得检验数 \( \overline{c}(S) = |S| - \sum_ {e \in E} I_ {e \in E(S)} \pi_ e \) 最小化，其中 \( I_ {e \in E(S)} \) 是指示函数，当边 e 至少有一个端点在 S 中时为 1。 \[ \sum_ {e \in E} I_ {e \in E(S)} \pi_ e = \sum_ {e \in E} \pi_ e \cdot [ \text{e 被 S 覆盖} ] \] 注意，一条边 e=(u,v) 被 S 覆盖当且仅当 \( u \in S \) 或 \( v \in S \)。因此，这个和可以重新表述。我们为每个顶点引入 0-1 变量 \( y_ v \) 表示顶点 v 是否在 S 中。那么，边 e=(u,v) 被覆盖的条件是 \( y_ u + y_ v \geq 1 \)。于是，定价子问题可以建模为如下整数线性规划： \[ \begin{aligned} \min \quad & \sum_ {v \in V} y_ v - \sum_ {e=(u,v) \in E} \pi_ e \cdot z_ e \\ \text{s.t.} \quad & y_ u + y_ v \geq 1, \quad \forall e=(u,v) \in E \\ & z_ e \leq y_ u, \quad \forall e=(u,v) \in E \\ & z_ e \leq y_ v, \quad \forall e=(u,v) \in E \\ & z_ e \geq 0, \quad \forall e \in E \\ & y_ v \in \{0, 1\}, \quad \forall v \in V \end{aligned} \tag{SP} \] 这里 \( z_ e \) 是一个连续变量，用于线性化“边 e 是否被覆盖”的乘积项。事实上，由于目标是最小化，且 \( \pi_ e \geq 0 \)，在最优解中，\( z_ e \) 会取到尽可能大的值，即 \( z_ e = \min(y_ u, y_ v) \)。但边被覆盖的条件是 \( y_ u + y_ v \geq 1 \)，所以如果 \( y_ u=0 \) 且 \( y_ v=0 \)，则约束不满足。如果 \( y_ u=1 \) 或 \( y_ v=1 \)，则 \( \min(y_ u, y_ v) \) 可能是 0 或 1。实际上，对于定价子问题，我们可以更直接地理解：目标是 \( \sum_ {v} y_ v - \sum_ {e} \pi_ e \cdot [ \text{e 被覆盖}] \)。由于 \( [ \text{e 被覆盖}] = 1 \) 当 \( y_ u + y_ v \geq 1 \)，我们可以将其线性化，或者注意到，对于一个给定的覆盖 S（由 y 决定），其检验数是 \( |S| - \sum_ {e: e 被 S 覆盖} \pi_ e \)。定价子问题就是要找到检验数最小的覆盖 S。这是一个加权版本的最小顶点覆盖问题，其中选择顶点 v 的成本是 1，而覆盖边 e 可以获得“奖励” \( \pi_ e \)。这正是 最小权顶点覆盖问题 ，可以通过整数规划求解（对于一般图是 NP-hard 的，但我们可以用 ILP 求解器，或者利用二分图上的多项式时间算法如果原图是二分图）。在我们的分支定价框架中，子问题本身可能也是 NP-hard 的，但我们通常用一个整数规划求解器来精确求解它，因为它的规模是原图规模，而不是主问题规模。 步骤 3.3：列生成迭代 求解当前的 RMP（线性规划松弛），得到最优解 \( \lambda^* \) 和对偶变量 \( \pi^* \)。 将 \( \pi^* \) 代入定价子问题（SP），求解 SP，得到最小检验数 \( \overline{c}_ {min} \) 和对应的新列（即新的顶点覆盖 S）。 如果 \( \overline{c} {min} < 0 \)（通常设置一个小的负容差，如 -1e-6），则将这个新列添加到 RMP 中（即添加变量 \( \lambda {new} \)，其系数 \( c_ {new} = |S| \)，\( a_ {e, new} = 1 \) 当边 e 被 S 覆盖）。返回步骤1。 如果 \( \overline{c}_ {min} \geq 0 \)，则当前 RMP 的 LP 松弛已求解到最优（即没有能改进目标的新列）。我们得到了原问题（MP）的 LP 松弛的最优解。 4. 分支定价：处理整数性 当列生成迭代停止后，我们得到了 MP 的 LP 松弛最优解 \( \lambda^* \)。如果 \( \lambda^* \) 的所有分量都是整数（0 或 1），那么我们就得到了原最小顶点覆盖问题的最优解（通过所选模式的并集，注意可能有多个模式被选中，但目标函数是所选模式的成本和，而每个模式本身就是一个完整的顶点覆盖。在集合覆盖模型中，通常一个解是由多个模式组成的，但在这里，由于每个模式本身就是一个完整的顶点覆盖，选择多个覆盖的并集可能不是最小覆盖。实际上，我们需要保证最终解是一个单一的覆盖。在经典的集合覆盖问题的分支定价中，解可以是多个模式的并集，它们共同覆盖所有元素。但在我们重新建模的顶点覆盖问题中，一个模式本身就是一个完整覆盖，所以我们希望选择一个模式即可。但这样，主问题就变成了从众多覆盖中选择一个最好的。这可以建模为： \[ \min \{ c_ p : p \in \Omega \} \] 这本质上是一个枚举问题。为了应用分支定价，我们通常允许解是多个模式的凸组合，但在整数解中，应该只有一个模式被选中。这可以通过在分支定界树上添加约束来实现，例如分支决策强制某个顶点是否在覆盖中。这引出了第二种，也是更常用的分支策略。 在实际的分支定价算法中，更常见的做法是 在主问题中使用原始的顶点变量 \( x_ v \) 的分解。我们可以将原问题（IP-MVC）用 Dantzig-Wolfe 分解重新表述，其中子问题是求解某个结构下的最小顶点覆盖，但这样比较复杂。另一种更直接的方法是我们不改变原变量，但用列生成来动态生成“有效不等式”，而不是新模式。但对于最小顶点覆盖，一个更实用的分支定价实现方式是： 主问题 使用原始的边覆盖约束，但变量是 \( x_ v \)。 定价 不是生成新的变量，而是生成“割平面”（cut），例如 子图不等式 、 团不等式 等，来加强线性规划松弛。但这属于分支切割（Branch-and-Cut）的范畴。 为了保持示例的清晰，我们这里演示一个经典的分支定价思路，但应用于一个不同的、但更适合的模型： 集合覆盖公式 ，并允许解是多个模式的并集。在这种情况下，每个模式 p 不一定需要覆盖所有边，但所有被选模式的并集必须覆盖所有边。每个模式 p 可以定义为某个顶点的子集，其成本是子集大小。主问题（MP）如之前所示。如果 LP 松弛解 \( \lambda^* \) 分数，我们需要分支。 分支策略 ： 常见的分支策略是对原始变量 \( x_ v \) 进行分支，即使它们没有显式出现在主问题中。因为 \( x_ v = \sum_ {p \in \Omega: v \in S_ p} \lambda_ p \)，我们可以计算每个顶点 v 的“分数值”。选择分数值最接近 0.5 的顶点 v* ，创建两个分支： 分支1：强制 \( x_ {v* } = 1 \)（即 v* 必须在覆盖中）。这对应于在定价子问题中，强制 \( y_ {v* } = 1 \)。 分支2：强制 \( x_ {v* } = 0 \)（即 v* 不能在覆盖中）。这对应于在定价子问题中，强制 \( y_ {v* } = 0 \)。 在每个分支节点，我们需要在新的限制下（定价子问题添加了 \( y_ {v* } = 1 \) 或 \( y_ {v* } = 0 \) 的约束）重新进行列生成，求解受限主问题的 LP 松弛。分支定界树不断扩展，直到所有节点都探查完毕（被剪枝或找到整数解）。记录找到的最优整数解。 5. 示例图与求解流程演示 考虑一个简单的无向图 G = (V, E)，V = {1, 2, 3, 4}，E = {(1,2), (2,3), (3,4), (1,4)}。这是一个4个顶点的环 C4。 步骤1：初始受限主问题 (RMP) 初始列：我们可以用最简单的覆盖：整个顶点集 V = {1,2,3,4} 作为一个模式 p0，成本 c0=4，显然它覆盖所有边。初始 RMP 只有一个变量 λ0。 初始 RMP： \[ \begin{aligned} \min \quad & 4\lambda_ 0 \\ \text{s.t.} \quad & \lambda_ 0 \geq 1 \quad \text{(对于所有边 e1,e2,e3,e4)} \\ & \lambda_ 0 \geq 0 \end{aligned} \] 最优解 λ0=1，目标值=4。对偶变量：每条边的对偶值 π_ e 都等于 1？ 不，这里约束是四个独立的约束，但只有一个变量。对偶问题为 max ∑ π_ e, s.t. ∑ π_ e ≤ 4, π_ e ≥ 0。最优解可以是 π_ e = 1 对于所有四条边，对偶目标值=4。我们得到对偶变量 π = (1,1,1,1) 对于边 e1(1,2), e2(2,3), e3(3,4), e4(1,4)。 步骤2：第一次定价子问题 我们需要找到一个顶点覆盖 S，使得检验数 \( \overline{c} = |S| - \sum_ {e: e 被 S 覆盖} \pi_ e \) 最小。 给定 π_ e = 1 对所有边，所以 \( \sum_ {e: e 被 S 覆盖} \pi_ e \) 等于 S 覆盖的边数。 我们求解子问题（SP）：最小化 |S| - (S覆盖的边数)。 对于图 C4，最小顶点覆盖的大小是2（例如 {1,3} 或 {2,4}）。 如果我们取 S = {1,3}，则覆盖的边是 (1,2), (1,4), (2,3), (3,4) 全部四条边。所以检验数 = 2 - 4 = -2。 所以找到了一个检验数为负的列（模式 p1 = {1,3}, 成本=2）。 步骤3：添加新列，求解新 RMP RMP 现在有两个变量 λ0 (V) 和 λ1 ({1,3})。约束为每条边必须被覆盖。 边覆盖情况： 模式 p0: 覆盖所有边。 模式 p1: 覆盖边 e1, e2, e3, e4（全部）。 新的 RMP： \[ \begin{aligned} \min \quad & 4\lambda_ 0 + 2\lambda_ 1 \\ \text{s.t.} \quad & \lambda_ 0 + \lambda_ 1 \geq 1 \quad \text{(每条边，因为两个模式都覆盖所有边)} \\ & \lambda_ 0, \lambda_ 1 \geq 0 \end{aligned} \] 实际上，四条边的约束是相同的：λ0 + λ1 ≥ 1。所以等价于一个约束。 最优解：取 λ1=1, λ0=0，目标值=2。对偶变量：四条边共用一个约束，对偶变量 π_ e 的和受主约束限制。对偶问题：max ∑ π_ e, s.t. ∑ π_ e ≤ 4, ∑ π_ e ≤ 2, π_ e ≥ 0。最优解是让 ∑ π_ e 尽可能大，但受第二个约束限制（对应 λ1），所以 ∑ π_ e = 2。由于对称性，可以取每条边的 π_ e = 0.5。 步骤4：第二次定价子问题 对偶变量 π = (0.5, 0.5, 0.5, 0.5)。 我们需要找到覆盖 S，最小化 |S| - ∑_ {e covered} 0.5 = |S| - 0.5 * (# 被覆盖的边数)。 尝试 S = {1,3}，检验数 = 2 - 0.5 4 = 0。 尝试 S = {2,4}，检验数 = 2 - 0.5 4 = 0。 尝试 S = {1,2,3}，检验数 = 3 - 0.5* 4 = 1 （更差）。 没有检验数为负的列了（最小检验数为0）。所以当前 RMP 的 LP 松弛已最优，目标值=2，解 λ1=1, λ0=0。这是一个整数解！对应的覆盖是模式 p1 = {1,3}，大小2。 步骤5：得到整数最优解 因为 LP 松弛解已经是整数，且我们求解的是 MP 的 LP 松弛，而这个解对应于一个单一的覆盖模式，所以它就是原最小顶点覆盖问题的最优解。不需要分支。 所以，对于图 C4，最小顶点覆盖的大小是2，例如 {1,3}。 6. 总结与扩展 这个示例演示了如何用分支定价法求解最小顶点覆盖问题： 建模 ：将问题构建为大规模整数线性规划主问题（MP），其变量对应可行的顶点覆盖模式。 列生成 ：在分支定界树的每个节点，求解 MP 的 LP 松弛。通过求解一个定价子问题（一个带奖励的最小顶点覆盖问题）来生成改进的新列，迭代直到 LP 松弛最优。 分支 ：如果 LP 松弛解分数，则基于原始顶点变量进行分支（例如，强制某个顶点在或不在覆盖中），在每个子节点重新进行列生成。 界限与剪枝 ：利用 LP 松弛解提供的下界，结合当前最好整数解的上界，进行剪枝。 这个方法的优势在于，主问题可能只有少量约束（边数），而复杂的组合结构被隐藏在定价子问题中。对于某些图类（如二分图），定价子问题可以在多项式时间内求解（例如用 König 定理和最大匹配算法），这使得分支定价法非常高效。对于一般图，定价子问题是 NP-hard 的，但仍可以用整数规划求解器在合理规模的图上求解。分支定价法通过避免显式枚举所有可能的覆盖模式，能够处理大规模的最小顶点覆盖问题实例。