基于线性规划的图最小边支配集问题的整数规划建模与分支定价算法求解示例
字数 6641 2025-12-06 08:38:21

基于线性规划的图最小边支配集问题的整数规划建模与分支定价算法求解示例

我将为您讲解一个结合整数规划、图论和列生成（分支定价）的算法题目。题目描述如下：

假设我们有一个无向图 \(G = (V, E)\)，其中 \(V\) 是顶点集合，\(E\) 是边集合。图中的一个边支配集定义为一个边子集 \(D \subseteq E\)，使得图中的每条边要么在 \(D\) 中，要么与 \(D\) 中的某条边共享至少一个公共顶点。换句话说，对于任意边 \(e \in E\)，要么 \(e \in D\)，要么存在一条边 \(f \in D\) 使得 \(e\) 和 \(f\) 有一个公共顶点。目标是找到最小基数（即边数最少）的边支配集。

这是一个NP难问题，我们可以通过整数规划建模，并利用分支定价算法（即分支定界框架内嵌入列生成）来求解较大规模实例。下面我详细展开解题思路和步骤。

1. 问题理解与整数规划建模

首先，我们需要理解“边支配”的概念。一条边被支配意味着它要么被选中，要么与其相邻的边中至少有一条被选中。这里的“相邻”指两条边共享一个顶点。因此，我们可以定义决策变量：

对于每条边 \(e \in E\)，定义二元变量 \(x_e \in \{0,1\}\)：

  • \(x_e = 1\) 表示边 \(e\) 被选入边支配集 \(D\)；
  • \(x_e = 0\) 表示边 \(e\) 未被选中。

目标是最小化所选边的数量：

\[\min \sum_{e \in E} x_e \]

约束条件：对于每条边 \(e = \{u,v\} \in E\)，它必须被支配。这意味着：

  • 要么 \(x_e = 1\)（自身被选中），
  • 要么存在与 \(e\) 相邻的边 \(f\) 使得 \(x_f = 1\)。

如何用线性约束表达“存在相邻边被选中”？我们可以枚举所有与 \(e\) 相邻的边。设 \(N(e) = \{ f \in E : f \neq e, \, f \text{ 与 } e \text{ 共享至少一个顶点} \}\)。则约束可写为：

\[x_e + \sum_{f \in N(e)} x_f \ge 1, \quad \forall e \in E \]

解释：对边 \(e\)，其自身及所有相邻边的 \(x\) 变量和至少为1，即至少有一条相关边被选中。

这样我们就得到了一个整数线性规划模型：

\[\begin{aligned} \min &\quad \sum_{e \in E} x_e \\ \text{s.t.} &\quad x_e + \sum_{f \in N(e)} x_f \ge 1, \quad \forall e \in E \\ &\quad x_e \in \{0,1\}, \quad \forall e \in E \end{aligned} \]

但该模型可能变量较多（\(|E|\) 个），而约束数量也是 \(|E|\)。对于大规模图，直接求解这个整数规划可能困难，因此我们考虑采用分支定价算法。

2. 分支定价算法基本思想

分支定价算法常用于大规模整数规划，其核心是将问题分解为：

  1. 主问题（Master Problem）：一个集合覆盖/划分类型的问题，通常变量数非常多（甚至指数级），但约束较少。
  2. 定价子问题（Pricing Subproblem）：用于生成主问题中有潜在改进作用的列（变量），本质上是在检验当前对偶变量下是否还有负检验数的列。

对于最小边支配集，我们可以将其转化为集合覆盖问题：
每条边 \(e\) 需要被至少一个“支配单元”覆盖。一个“支配单元”可以是一条被选中的边 \(f\) ，它能够支配所有与它相邻的边（包括它自身）。那么，边 \(f\) 所支配的边集合就是 \(\{f\} \cup N(f)\)。因此，如果我们定义一种“模式”对应一条边，其支配的边集合就是该边及其邻边。那么问题转化为：选择尽可能少的模式，使得所有边都被至少一个模式覆盖。

这正是集合覆盖模型，而且每个模式对应一条边。这似乎与原模型相同，为什么还需要列生成？
注意：在原模型中，每个变量直接对应一条边是否被选中。而在列生成思路中，我们考虑更复杂的“模式”，例如一个模式可以是一个边集合（不一定是一条边），只要这个边集合能支配所有边。但为了简化，这里我们仍采用“每条边作为一个模式”的集合覆盖模型，但我们可以通过列生成来隐式处理大规模问题，特别是当图的对称性高时，可以合并一些模式。

但为了更清晰地展示分支定价，我们考虑另一种建模角度：将最小边支配集建模为“边覆盖”的推广，然后利用Dantzig-Wolfe分解，将原问题分解为多个子结构。然而，最小边支配集本身结构较简单，通常不直接使用复杂分解。为了演示分支定价流程，我们假设将原图的边集划分为若干连通子图（例如通过某种方式分解），然后每个子图内求解一个小规模边支配集子问题，主问题负责组合子问题的解。但这不是标准做法。实际上，更常见的做法是直接对上述整数规划模型应用分支定界，并在每个节点求解线性规划松弛时采用列生成来动态生成变量（即原变量 \(x_e\)）。但原变量只有 \(|E|\) 个，通常不需要列生成。

为了展示分支定价算法，我们需要一个更丰富的列结构。因此，我们对问题进行变换：考虑“边支配集”的补集视角。定义 \(y_e = 1 - x_e\)，则 \(y_e = 1\) 表示边 \(e\) 未被选中。此时约束变为：

\[1 - y_e + \sum_{f \in N(e)} (1 - y_f) \ge 1 \quad \Rightarrow \quad y_e + \sum_{f \in N(e)} y_f \le |N(e)|, \quad \forall e \in E \]

这个变换没有增加变量，但我们可以考虑另一种思路：将原问题转化为寻找最大“非支配”边集，使得其中任意一条边的邻边中未被选中的边数有限制。但这种转化并不直观。

为简化，我们直接采用原模型，但假设图很大，且我们想用列生成来生成“候选边支配集”的配置模式。实际上，标准的边支配集问题可以直接求解上述整数规划，但为了教学目的，我们构造一个可以使用列生成的扩展问题：考虑带权重的边支配集，每条边有权重 \(w_e\)，目标是找最小权重边支配集。我们引入“模式”概念：一个模式 \(p\) 是一个边子集 \(S_p \subseteq E\)，满足 \(S_p\) 本身是一个边支配集（即它支配了所有边）。显然，单个边的集合 \(\{e\}\) 不一定支配所有边，所以模式是更大的集合。但这样模式数量是指数级的。我们可以用列生成来隐式生成模式。

但这样问题变得更复杂。为了聚焦算法流程，我们回归到一个更简单的视角：我们将原问题看作一个集合覆盖问题，覆盖元素是边 \(e \in E\)，而覆盖集合是“能够支配某条边的候选边集合”。实际上，对于每条边 \(e\)，能支配它的候选边集合是 \(\{e\} \cup N(e)\)。那么，我们可以定义一种“列”对应选择一条边 \(f\)，其覆盖的边集合是 \(\{f\} \cup N(f)\)。这样，列的数量就是 \(|E|\)，与变量数相同，无需列生成。为了有列生成的空间，我们考虑每个模式可以是多条边的组合，但这样模式结构复杂。

为了教学，我们采用一个经典的处理方式：将边支配集问题转化为顶点支配集问题。因为边支配集可以通过构造“线图”转化为顶点支配集：将原图的每条边转化为线图的一个顶点，如果原图中两条边相邻，则在线图中对应的两个顶点间连一条边。那么原图的边支配集等价于线图的顶点支配集。而顶点支配集问题可以用集合覆盖模型表示，并且可以通过列生成来生成“顶点覆盖模式”。但这也偏离了边支配集本身。

为了避免混淆，我们直接讲解在边支配集问题上应用分支定价算法的一种简化教学版本：

我们考虑以下主问题模型（集合覆盖形式）：

  • 覆盖元素：原图的边 \(e \in E\)。
  • 覆盖集合：对应原图的边，但每条边 \(f\) 作为覆盖集合时，它能覆盖的边集合是 \(\{f\} \cup N(f)\)。
  • 主问题的决策变量 \(\lambda_f \in \{0,1\}\) 表示是否选择边 \(f\) 代表的覆盖集合。

这个模型和原模型完全一样，只不过我们将变量名从 \(x_f\) 改为 \(\lambda_f\)。那么列生成还有必要吗？注意，在列生成中，主问题的列可以更一般化，比如一个列可以代表一个“小规模边支配集”，即一个边子集，它能够支配原图的一部分边。但这样问题就变得复杂，需要设计合适的子问题来生成列。

鉴于上述复杂性，我们聚焦于算法框架，并假设我们已经有了一个能够生成“候选支配边集”的子问题。下面是算法步骤的详细说明。

3. 分支定价算法步骤

步骤1：构造初始主问题（限制主问题）

我们需要一个初始可行的边支配集。一个简单的初始解是选择所有边，即 \(\lambda_f = 1, \forall f \in E\)。但为了启动列生成，我们通常先选择一部分列构成限制主问题（Restricted Master Problem, RMP）。例如，我们可以先加入一些单边列，但单边列可能无法构成可行解（因为一条边可能无法支配所有边）。为了保证初始RMP可行，我们可以加入一组“平凡列”，比如每条边自身一列，但这样RMP的初始解就是全选，这会导致对偶变量为零，不利于生成新列。另一种方法是加入一些冗余列，比如每个顶点关联的边集合。但更实际的做法是，我们从一个可行的边支配集开始，比如通过贪心算法构造一个初始解，然后将这个解涉及到的边作为初始列加入RMP。

假设我们通过贪心算法得到一个边支配集 \(D_0\)，它包含边集合 \(\{ e_1, e_2, ..., e_k \}\)。我们在RMP中为每条边 \(e_i\) 创建一列，该列对应的覆盖集合就是 \(\{e_i\} \cup N(e_i)\)。这样RMP的初始列数就是 \(k\)。RMP的线性规划松弛为：

\[\begin{aligned} \min &\quad \sum_{j \in J} \lambda_j \quad \text{(这里假设每条边的权重为1，所以目标系数为1)}\\ \text{s.t.} &\quad \sum_{j \in J} a_{ej} \lambda_j \ge 1, \quad \forall e \in E \\ &\quad \lambda_j \ge 0, \quad \forall j \in J \end{aligned} \]

其中 \(J\) 是当前列的索引集，\(a_{ej} = 1\) 如果边 \(e\) 被列 \(j\) 对应的覆盖集合覆盖，否则为0。注意，这里的 \(\lambda_j\) 是连续变量（因为求解线性规划松弛），在整数规划中会被限制为整数。

步骤2：求解RMP的线性规划松弛，得到对偶变量值

用单纯形法求解上述RMP的LP松弛，得到最优解 \(\lambda^*\) 和对偶变量 \(\pi_e \ge 0\)（对应每个约束 \(\sum_j a_{ej} \lambda_j \ge 1\)）。对偶变量 \(\pi_e\) 可以理解为边 \(e\) 被覆盖的“价值”。

步骤3：定价子问题（寻找检验数为负的列）

我们需要生成新的列，即寻找一个新的覆盖集合（对应原图的一个边子集 \(S \subseteq E\)），使得加入RMP后能改进目标值。在列生成中，检验一个新列 \(j\) 是否应该加入的标准是它的检验数（reduced cost）是否为负。对于最小化问题，检验数 \(\bar{c}_j = c_j - \sum_{e \in E} a_{ej} \pi_e\)，其中 \(c_j\) 是新列的成本（即该覆盖集合的权重），\(a_{ej} = 1\) 如果边 \(e\) 被该列覆盖。

在我们的设定中，一个覆盖集合对应原图的一个边子集 \(S\)，它能覆盖的边集合是 \(\bigcup_{f \in S} (\{f\} \cup N(f))\)。但这样定义的话，\(S\) 可以是任意边子集，其成本 \(c_j = |S|\)（即边数）。我们需要寻找一个边子集 \(S\)，使得检验数 \(\bar{c} = |S| - \sum_{e \in \bigcup_{f \in S} (\{f\} \cup N(f))} \pi_e\) 为负。这等价于最大化 \(\sum_{e \in \text{被覆盖的边}} \pi_e - |S|\)。

但子问题需要搜索所有可能的边子集 \(S\)，这是一个组合优化问题。为了使其可处理，我们通常限制 \(S\) 为单条边，即只生成单边列。这样，子问题就简化了：对于每条边 \(f \in E\)，计算其检验数 \(\bar{c}_f = 1 - \sum_{e \in \{f\} \cup N(f)} \pi_e\)。我们寻找 \(\bar{c}_f < 0\) 的边 \(f\)。如果存在，将对应的列加入RMP，然后回到步骤2。

但如果我们只允许单边列，那么列生成过程就是在逐步加入未被覆盖的边所对应的列，直到所有边都被覆盖。这其实等价于求解原整数规划的LP松弛，并没有利用到列生成的优势。为了真正体现分支定价，我们需要允许 \(S\) 包含多条边，但这样定价子问题就变成了一个带权最大覆盖问题的逆问题，较复杂。作为教学示例，我们通常不深究子问题的细节，而是假设子问题可以高效求解（例如通过动态规划或整数规划）。

步骤4：迭代列生成

重复步骤2和3，直到找不到检验数为负的列。此时，RMP的LP松弛达到最优（对于完整的主问题）。

步骤5：分支定界

如果此时RMP的LP松弛解是整数，则得到最优解。否则，需要分支。在分支定价中，分支策略需要小心设计，以避免破坏子问题的结构。常见的分支策略包括：

  • 对变量 \(\lambda_j\) 进行分支（即强制某列被选中或不被选中），但这可能导致子问题变化。
  • 对原问题的变量 \(x_e\) 进行分支（即强制某条边被选中或不被选中）。由于 \(x_e = \sum_{j: e \in S_j} \lambda_j\)，我们可以通过添加约束 \(\sum_{j: e \in S_j} \lambda_j = 1\) 或 \(=0\) 来分支。这会影响子问题，因为子问题在生成新列时必须满足分支限制。

分支后，在每个节点上继续使用列生成求解LP松弛，直到找到整数最优解或证明不存在更优解。

4. 总结与扩展

虽然边支配集问题本身可以直接用整数规划求解，但通过这个示例，我们展示了如何将其嵌入分支定价框架。实际应用中，分支定价算法更适用于那些具有明显分解结构的问题（如车辆路径、机组排班等），其中子问题通常是资源约束最短路径或背包问题。对于边支配集，标准的求解方法可能是直接用整数规划求解器，但本示例展示了如何从建模到算法实现的完整思路。

关键点：

  • 将问题建模为集合覆盖形式，主问题选择“覆盖集合”，子问题生成新的覆盖集合。
  • 通过列生成动态添加变量，避免枚举所有可能的列。
  • 在分支定界框架内嵌入列生成，处理整数性要求。

这个示例帮助您理解了分支定价算法如何应用于组合优化问题，即使问题本身可能不是典型的应用场景。

基于线性规划的图最小边支配集问题的整数规划建模与分支定价算法求解示例 我将为您讲解一个结合整数规划、图论和列生成（分支定价）的算法题目。题目描述如下： 假设我们有一个无向图 \( G = (V, E) \)，其中 \( V \) 是顶点集合，\( E \) 是边集合。图中的一个 边支配集 定义为一个边子集 \( D \subseteq E \)，使得图中的每条边要么在 \( D \) 中，要么与 \( D \) 中的某条边共享至少一个公共顶点。换句话说，对于任意边 \( e \in E \)，要么 \( e \in D \)，要么存在一条边 \( f \in D \) 使得 \( e \) 和 \( f \) 有一个公共顶点。目标是找到 最小基数 （即边数最少）的边支配集。 这是一个NP难问题，我们可以通过整数规划建模，并利用分支定价算法（即分支定界框架内嵌入列生成）来求解较大规模实例。下面我详细展开解题思路和步骤。 1. 问题理解与整数规划建模 首先，我们需要理解“边支配”的概念。一条边被支配意味着它要么被选中，要么与其相邻的边中至少有一条被选中。这里的“相邻”指两条边共享一个顶点。因此，我们可以定义决策变量： 对于每条边 \( e \in E \)，定义二元变量 \( x_ e \in \{0,1\} \)： \( x_ e = 1 \) 表示边 \( e \) 被选入边支配集 \( D \)； \( x_ e = 0 \) 表示边 \( e \) 未被选中。 目标是最小化所选边的数量： \[ \min \sum_ {e \in E} x_ e \] 约束条件：对于每条边 \( e = \{u,v\} \in E \)，它必须被支配。这意味着： 要么 \( x_ e = 1 \)（自身被选中）， 要么存在与 \( e \) 相邻的边 \( f \) 使得 \( x_ f = 1 \)。 如何用线性约束表达“存在相邻边被选中”？我们可以枚举所有与 \( e \) 相邻的边。设 \( N(e) = \{ f \in E : f \neq e, \, f \text{ 与 } e \text{ 共享至少一个顶点} \} \)。则约束可写为： \[ x_ e + \sum_ {f \in N(e)} x_ f \ge 1, \quad \forall e \in E \] 解释：对边 \( e \)，其自身及所有相邻边的 \( x \) 变量和至少为1，即至少有一条相关边被选中。 这样我们就得到了一个整数线性规划模型： \[ \begin{aligned} \min &\quad \sum_ {e \in E} x_ e \\ \text{s.t.} &\quad x_ e + \sum_ {f \in N(e)} x_ f \ge 1, \quad \forall e \in E \\ &\quad x_ e \in \{0,1\}, \quad \forall e \in E \end{aligned} \] 但该模型可能变量较多（\(|E|\) 个），而约束数量也是 \(|E|\)。对于大规模图，直接求解这个整数规划可能困难，因此我们考虑采用分支定价算法。 2. 分支定价算法基本思想 分支定价算法常用于大规模整数规划，其核心是将问题分解为： 主问题（Master Problem） ：一个集合覆盖/划分类型的问题，通常变量数非常多（甚至指数级），但约束较少。 定价子问题（Pricing Subproblem） ：用于生成主问题中有潜在改进作用的列（变量），本质上是在检验当前对偶变量下是否还有负检验数的列。 对于最小边支配集，我们可以将其转化为集合覆盖问题： 每条边 \( e \) 需要被至少一个“支配单元”覆盖。一个“支配单元”可以是一条被选中的边 \( f \) ，它能够支配所有与它相邻的边（包括它自身）。那么，边 \( f \) 所支配的边集合就是 \( \{f\} \cup N(f) \)。因此，如果我们定义一种“模式”对应一条边，其支配的边集合就是该边及其邻边。那么问题转化为：选择尽可能少的模式，使得所有边都被至少一个模式覆盖。 这正是集合覆盖模型，而且每个模式对应一条边。这似乎与原模型相同，为什么还需要列生成？ 注意：在原模型中，每个变量直接对应一条边是否被选中。而在列生成思路中，我们考虑更复杂的“模式”，例如一个模式可以是一个边集合（不一定是一条边），只要这个边集合能支配所有边。但为了简化，这里我们仍采用“每条边作为一个模式”的集合覆盖模型，但我们可以通过列生成来隐式处理大规模问题，特别是当图的对称性高时，可以合并一些模式。 但为了更清晰地展示分支定价，我们考虑另一种建模角度：将最小边支配集建模为“边覆盖”的推广，然后利用Dantzig-Wolfe分解，将原问题分解为多个子结构。然而，最小边支配集本身结构较简单，通常不直接使用复杂分解。为了演示分支定价流程，我们假设将原图的边集划分为若干连通子图（例如通过某种方式分解），然后每个子图内求解一个小规模边支配集子问题，主问题负责组合子问题的解。但这不是标准做法。实际上，更常见的做法是直接对上述整数规划模型应用分支定界，并在每个节点求解线性规划松弛时采用列生成来动态生成变量（即原变量 \( x_ e \)）。但原变量只有 \(|E|\) 个，通常不需要列生成。 为了展示分支定价算法，我们需要一个更丰富的列结构。因此，我们对问题进行 变换 ：考虑“边支配集”的补集视角。定义 \( y_ e = 1 - x_ e \)，则 \( y_ e = 1 \) 表示边 \( e \) 未被选中。此时约束变为： \[ 1 - y_ e + \sum_ {f \in N(e)} (1 - y_ f) \ge 1 \quad \Rightarrow \quad y_ e + \sum_ {f \in N(e)} y_ f \le |N(e)|, \quad \forall e \in E \] 这个变换没有增加变量，但我们可以考虑另一种思路：将原问题转化为寻找最大“非支配”边集，使得其中任意一条边的邻边中未被选中的边数有限制。但这种转化并不直观。 为简化，我们直接采用原模型，但假设图很大，且我们想用列生成来生成“候选边支配集”的配置模式。实际上，标准的边支配集问题可以直接求解上述整数规划，但为了教学目的，我们构造一个可以使用列生成的扩展问题：考虑 带权重的边支配集 ，每条边有权重 \( w_ e \)，目标是找最小权重边支配集。我们引入“模式”概念：一个模式 \( p \) 是一个边子集 \( S_ p \subseteq E \)，满足 \( S_ p \) 本身是一个边支配集（即它支配了所有边）。显然，单个边的集合 \( \{e\} \) 不一定支配所有边，所以模式是更大的集合。但这样模式数量是指数级的。我们可以用列生成来隐式生成模式。 但这样问题变得更复杂。为了聚焦算法流程，我们回归到一个更简单的视角：我们将原问题看作一个集合覆盖问题，覆盖元素是边 \( e \in E \)，而覆盖集合是“能够支配某条边的候选边集合”。实际上，对于每条边 \( e \)，能支配它的候选边集合是 \( \{e\} \cup N(e) \)。那么，我们可以定义一种“列”对应选择一条边 \( f \)，其覆盖的边集合是 \( \{f\} \cup N(f) \)。这样，列的数量就是 \( |E| \)，与变量数相同，无需列生成。为了有列生成的空间，我们考虑每个模式可以是多条边的组合，但这样模式结构复杂。 为了教学，我们采用一个经典的处理方式：将边支配集问题转化为顶点支配集问题。因为边支配集可以通过构造“线图”转化为顶点支配集：将原图的每条边转化为线图的一个顶点，如果原图中两条边相邻，则在线图中对应的两个顶点间连一条边。那么原图的边支配集等价于线图的顶点支配集。而顶点支配集问题可以用集合覆盖模型表示，并且可以通过列生成来生成“顶点覆盖模式”。但这也偏离了边支配集本身。 为了避免混淆，我们直接讲解 在边支配集问题上应用分支定价算法 的一种简化教学版本： 我们考虑以下主问题模型（集合覆盖形式）： 覆盖元素：原图的边 \( e \in E \)。 覆盖集合：对应原图的 边 ，但每条边 \( f \) 作为覆盖集合时，它能覆盖的边集合是 \( \{f\} \cup N(f) \)。 主问题的决策变量 \( \lambda_ f \in \{0,1\} \) 表示是否选择边 \( f \) 代表的覆盖集合。 这个模型和原模型完全一样，只不过我们将变量名从 \( x_ f \) 改为 \( \lambda_ f \)。那么列生成还有必要吗？注意，在列生成中，主问题的列可以更一般化，比如一个列可以代表一个“小规模边支配集”，即一个边子集，它能够支配原图的一部分边。但这样问题就变得复杂，需要设计合适的子问题来生成列。 鉴于上述复杂性，我们聚焦于算法框架，并假设我们已经有了一个能够生成“候选支配边集”的子问题。下面是算法步骤的详细说明。 3. 分支定价算法步骤 步骤1：构造初始主问题（限制主问题） 我们需要一个初始可行的边支配集。一个简单的初始解是选择所有边，即 \( \lambda_ f = 1, \forall f \in E \)。但为了启动列生成，我们通常先选择一部分列构成限制主问题（Restricted Master Problem, RMP）。例如，我们可以先加入一些单边列，但单边列可能无法构成可行解（因为一条边可能无法支配所有边）。为了保证初始RMP可行，我们可以加入一组“平凡列”，比如每条边自身一列，但这样RMP的初始解就是全选，这会导致对偶变量为零，不利于生成新列。另一种方法是加入一些冗余列，比如每个顶点关联的边集合。但更实际的做法是，我们从一个可行的边支配集开始，比如通过贪心算法构造一个初始解，然后将这个解涉及到的边作为初始列加入RMP。 假设我们通过贪心算法得到一个边支配集 \( D_ 0 \)，它包含边集合 \( \{ e_ 1, e_ 2, ..., e_ k \} \)。我们在RMP中为每条边 \( e_ i \) 创建一列，该列对应的覆盖集合就是 \( \{e_ i\} \cup N(e_ i) \)。这样RMP的初始列数就是 \( k \)。RMP的线性规划松弛为： \[ \begin{aligned} \min &\quad \sum_ {j \in J} \lambda_ j \quad \text{(这里假设每条边的权重为1，所以目标系数为1)}\\ \text{s.t.} &\quad \sum_ {j \in J} a_ {ej} \lambda_ j \ge 1, \quad \forall e \in E \\ &\quad \lambda_ j \ge 0, \quad \forall j \in J \end{aligned} \] 其中 \( J \) 是当前列的索引集，\( a_ {ej} = 1 \) 如果边 \( e \) 被列 \( j \) 对应的覆盖集合覆盖，否则为0。注意，这里的 \( \lambda_ j \) 是连续变量（因为求解线性规划松弛），在整数规划中会被限制为整数。 步骤2：求解RMP的线性规划松弛，得到对偶变量值 用单纯形法求解上述RMP的LP松弛，得到最优解 \( \lambda^* \) 和对偶变量 \( \pi_ e \ge 0 \)（对应每个约束 \( \sum_ j a_ {ej} \lambda_ j \ge 1 \)）。对偶变量 \( \pi_ e \) 可以理解为边 \( e \) 被覆盖的“价值”。 步骤3：定价子问题（寻找检验数为负的列） 我们需要生成新的列，即寻找一个新的覆盖集合（对应原图的一个边子集 \( S \subseteq E \)），使得加入RMP后能改进目标值。在列生成中，检验一个新列 \( j \) 是否应该加入的标准是它的 检验数 （reduced cost）是否为负。对于最小化问题，检验数 \( \bar{c} j = c_ j - \sum {e \in E} a_ {ej} \pi_ e \)，其中 \( c_ j \) 是新列的成本（即该覆盖集合的权重），\( a_ {ej} = 1 \) 如果边 \( e \) 被该列覆盖。 在我们的设定中，一个覆盖集合对应原图的一个边子集 \( S \)，它能覆盖的边集合是 \( \bigcup_ {f \in S} (\{f\} \cup N(f)) \)。但这样定义的话，\( S \) 可以是任意边子集，其成本 \( c_ j = |S| \)（即边数）。我们需要寻找一个边子集 \( S \)，使得检验数 \( \bar{c} = |S| - \sum_ {e \in \bigcup_ {f \in S} (\{f\} \cup N(f))} \pi_ e \) 为负。这等价于最大化 \( \sum_ {e \in \text{被覆盖的边}} \pi_ e - |S| \)。 但子问题需要搜索所有可能的边子集 \( S \)，这是一个组合优化问题。为了使其可处理，我们通常限制 \( S \) 为单条边，即只生成单边列。这样，子问题就简化了：对于每条边 \( f \in E \)，计算其检验数 \( \bar{c} f = 1 - \sum {e \in \{f\} \cup N(f)} \pi_ e \)。我们寻找 \( \bar{c}_ f < 0 \) 的边 \( f \)。如果存在，将对应的列加入RMP，然后回到步骤2。 但如果我们只允许单边列，那么列生成过程就是在逐步加入未被覆盖的边所对应的列，直到所有边都被覆盖。这其实等价于求解原整数规划的LP松弛，并没有利用到列生成的优势。为了真正体现分支定价，我们需要允许 \( S \) 包含多条边，但这样定价子问题就变成了一个 带权最大覆盖问题 的逆问题，较复杂。作为教学示例，我们通常不深究子问题的细节，而是假设子问题可以高效求解（例如通过动态规划或整数规划）。 步骤4：迭代列生成 重复步骤2和3，直到找不到检验数为负的列。此时，RMP的LP松弛达到最优（对于完整的主问题）。 步骤5：分支定界 如果此时RMP的LP松弛解是整数，则得到最优解。否则，需要分支。在分支定价中，分支策略需要小心设计，以避免破坏子问题的结构。常见的分支策略包括： 对变量 \( \lambda_ j \) 进行分支（即强制某列被选中或不被选中），但这可能导致子问题变化。 对原问题的变量 \( x_ e \) 进行分支（即强制某条边被选中或不被选中）。由于 \( x_ e = \sum_ {j: e \in S_ j} \lambda_ j \)，我们可以通过添加约束 \( \sum_ {j: e \in S_ j} \lambda_ j = 1 \) 或 \( =0 \) 来分支。这会影响子问题，因为子问题在生成新列时必须满足分支限制。 分支后，在每个节点上继续使用列生成求解LP松弛，直到找到整数最优解或证明不存在更优解。 4. 总结与扩展 虽然边支配集问题本身可以直接用整数规划求解，但通过这个示例，我们展示了如何将其嵌入分支定价框架。实际应用中，分支定价算法更适用于那些具有明显分解结构的问题（如车辆路径、机组排班等），其中子问题通常是资源约束最短路径或背包问题。对于边支配集，标准的求解方法可能是直接用整数规划求解器，但本示例展示了如何从建模到算法实现的完整思路。 关键点： 将问题建模为集合覆盖形式，主问题选择“覆盖集合”，子问题生成新的覆盖集合。 通过列生成动态添加变量，避免枚举所有可能的列。 在分支定界框架内嵌入列生成，处理整数性要求。 这个示例帮助您理解了分支定价算法如何应用于组合优化问题，即使问题本身可能不是典型的应用场景。