基于线性规划的图最小带权反馈边集问题的分支定价法求解示例
字数 4431 2025-12-14 12:16:41

基于线性规划的图最小带权反馈边集问题的分支定价法求解示例

题目描述
考虑一个无向图 \(G = (V, E)\)，其中每条边 \(e \in E\) 有一个正整数权重 \(w_e > 0\)。一个反馈边集是边集 \(F \subseteq E\) 的一个子集，使得从 \(G\) 中删除 \(F\) 中的所有边后，剩余的图不包含任何环（即成为一棵森林）。目标是找到一个反馈边集 \(F\)，使得其总权重 \(\sum_{e \in F} w_e\) 最小。该问题是 NP 难的，但可以通过整数规划建模，并利用分支定价法（Branch and Price，结合列生成和分支定界）求解。我们将逐步介绍其线性规划松弛的列生成求解过程，以及如何在分支定界框架中嵌入列生成。

解题过程

步骤1：整数规划建模
将每条边 \(e\) 是否选入反馈边集用一个 0-1 变量 \(x_e\) 表示：若 \(e \in F\) 则 \(x_e = 1\)，否则 \(x_e = 0\)。我们需要删除至少一条来自每个环的边。但由于环的数量是指数级的，我们改用覆盖所有圈的思路。已知一个边集是反馈边集当且仅当它的补集 \(E \setminus F\) 是森林（即无环）。因此，可以等价地描述为：选取一个最大权森林（即最大生成森林），使得剩余边（即反馈边集）的权重最小。不过更直接的方法是：对每个圈，反馈边集必须包含该圈的至少一条边。这引出以下约束：
对每个圈（环）\(C \subseteq E\)，有

\[\sum_{e \in C} x_e \ge 1. \]

因为如果圈上所有边都没有被选（即 \(x_e = 0\) 对所有 \(e \in C\)），则删除后这个圈仍然存在，不满足无环。
于是得到整数规划模型：

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

\[ \text{s.t.} \quad \sum_{e \in C} x_e \ge 1 \quad \forall \text{ 圈 } C, \]

\[ x_e \in \{0,1\} \quad \forall e \in E. \]

步骤2：线性规划松弛与对偶
首先求解其线性规划松弛（LP relaxation）：将 \(x_e \in \{0,1\}\) 替换为 \(0 \le x_e \le 1\)。约束个数（圈的数量）是指数级的，因此无法显式列出所有约束。我们采用列生成的思路，但这里“列”是对偶问题中的变量。更准确地说，这是一个约束指数多的问题，我们通过解其对偶来生成进入基的约束（即圈不等式）。这是“行生成”（或称切割生成）的一种形式。但因为常称为分支定价（包含列生成的思想），这里我们按标准术语称为分支定价。

原问题线性松弛：

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

\[ \sum_{e \in C} x_e \ge 1 \quad \forall C \in \mathcal{C}, \]

\[ 0 \le x_e \le 1, \]

其中 \(\mathcal{C}\) 是所有圈的集合。

写出其对偶。对每个圈 \(C\) 引入对偶变量 \(y_C \ge 0\)，对每条边 \(e\) 的原变量上界约束 \(x_e \le 1\) 引入对偶变量 \(z_e \ge 0\)（但这里我们不显式写 \(x_e \le 1\)，因为它可以被圈约束隐含保证，不过为了完整性可以加上）。标准对偶推导：原问题有约束 \(A x \ge 1\)（每行对应一个圈），目标系数 \(w\)。对偶为：

\[\max \sum_{C} y_C \]

\[ \text{s.t.} \quad \sum_{C: e \in C} y_C \le w_e \quad \forall e \in E, \]

\[ y_C \ge 0 \quad \forall C. \]

这就是圈填充问题（cycle packing）：给每个圈分配一个非负值 \(y_C\)，使得对每条边 \(e\)，包含 \(e\) 的所有圈的 \(y_C\) 之和不超过 \(w_e\)，最大化总圈值 \(\sum_C y_C\)。

步骤3：限制主问题与定价子问题
我们解原问题 LP 松弛时，并不枚举所有圈，而是维护一个圈的子集 \(\mathcal{C}' \subset \mathcal{C}\)，求解限制主问题（RMP）：

\[\min \sum_{e} w_e x_e \]

\[ \sum_{e \in C} x_e \ge 1 \quad \forall C \in \mathcal{C}', \]

\[ x_e \ge 0. \]

（上界 \(x_e \le 1\) 可省略，因为若 \(x_e > 1\) 可减到 1 而不违反约束且目标更优。）

解 RMP 得到最优解 \(x^*\) 和对偶变量值（对每个圈约束 \(C \in \mathcal{C}'\) 有一个对偶变量 \(y_C \ge 0\)）。我们还需要检查是否有一个圈 \(C \notin \mathcal{C}'\) 使得对应的约束被违反，即是否 \(\sum_{e \in C} x_e^* < 1\)。这样的圈就是需要加入 \(\mathcal{C}'\) 的“列”（对偶角度是行）。寻找这样一个圈等价于：在图上，每条边 \(e\) 赋予“长度” \(x_e^*\)，找一个圈使得其总长 \(< 1\)。如果所有圈的长度都 \(\ge 1\)，则 \(x^*\) 是原 LP 松弛的最优解。

因此，定价子问题是在图上找一个圈 \(C\) 使得 \(\sum_{e \in C} x_e^*\) 最小。如果最小圈长 \(< 1\)，则将该圈加入 \(\mathcal{C}'\) 并重复；否则 LP 松弛已解到最优。

步骤4：子问题求解
子问题是无向图最小权圈问题，其中边权为 \(x_e^* \ge 0\)。这可在多项式时间求解：对每条边 \((u,v)\)，计算去掉该边后从 \(u\) 到 \(v\) 的最短路（用 Dijkstra），加上该边的长度 \(x_{(u,v)}^*\) 即为包含该边的最小圈长度。遍历所有边，取最小者，即可得到最小圈及其长度。复杂度 \(O(|E|(|V|\log |V| + |E|))\)。

步骤5：分支策略
当 RMP 的 LP 松弛解 \(x^*\) 不全为整数时，需要分支。常见的分支规则是：选一条边 \(e\) 使得 \(x_e^*\) 分数（例如最接近 0.5），分成两支：\(x_e = 0\) 和 \(x_e = 1\)。

  • 若 \(x_e = 1\)，则该边必须在反馈边集中。在子问题中，可暂时固定它，并在后续的圈约束中不再考虑包含 \(e\) 的圈（因为已满足）。
  • 若 \(x_e = 0\)，则该边不在反馈边集中，则原图的圈约束必须由其他边满足。在子问题中，该边在圈中时仍需被覆盖。

在分支节点，我们需要在修改的问题上继续用列生成求解 LP 松弛。这需要在定价子问题中考虑固定边的情况。若 \(x_e=1\)，则在求最小圈时可忽略那些包含 \(e\) 的圈（因为约束自动满足）；但为简单起见，可仍然允许生成这些圈，但它们在 RMP 中不会成为有效约束（因为约束右端变成 0？）。更系统的方法是调整 RMP 的约束形式：对固定 \(x_e=1\) 的边，其所在圈约束可删去；对固定 \(x_e=0\) 的边，在计算圈长度时该边的 \(x_e^*=0\) 固定。这仍可适应。

步骤6：整体算法流程

  1. 初始化 \(\mathcal{C}'\) 为一组覆盖所有边的圈（例如每个三角形（如果存在）或通过任意生成树加一条边形成的圈）。
  2. 在当前分支节点，求解 RMP 的 LP 松弛，得 \(x^*\)。
  3. 调用定价子问题：求最小圈长 \(L\) 和对应的圈 \(C\)。
  4. 若 \(L < 1 - \epsilon\)（\(\epsilon\) 为容忍误差），将 \(C\) 加入 \(\mathcal{C}'\)，返回步骤 2。
  5. 若 \(L \ge 1 - \epsilon\)，该节点 LP 松弛解最优。若 \(x^*\) 全为整数，则更新当前最优解（若更好）。否则，选一个分数变量分支，创建两个子节点。
  6. 用分支定界框架搜索，在子节点重复步骤 2-5。

步骤7：示例演示
考虑简单图：\(V=\{1,2,3,4\}\)，边集合 \(E=\{(1,2),(2,3),(3,4),(4,1),(1,3)\}\)，权重均为 1。

  1. 初始化 \(\mathcal{C}'\) 包含一个圈，比如 \(C_1: 1-2-3-1\)（边集 \(\{(1,2),(2,3),(1,3)\}\)）。
  2. 解 RMP：只有一个约束 \(x_{12}+x_{23}+x_{13} \ge 1\)，最小化 \(\sum x_e\)，最优解 \(x_{13}=1\)，其余 0，目标值 1。
  3. 定价子问题：边权 \(x^*\) 为 \((0,0,1,0,0)\) 对应边顺序同上。计算最小圈：对边 \((1,2)\)，去掉后最短路 1-3-2 长 0+0=0，加上 \(x_{12}^*=0\) 得 0。发现圈 1-2-3-1 长 0+0+1=1 不优于 1，但圈 1-2-3-4-1 长 0+0+0+0=0<1。加入这个圈 \(C_2\)。
  4. 新 RMP 有两个圈约束，解得 \(x_{12}=0.5, x_{23}=0.5, x_{34}=0, x_{41}=0, x_{13}=0.5\)，目标 1.5。
  5. 定价子问题：最小圈长？检查圈 1-3-4-1 长 0.5+0+0=0.5<1，加入 \(C_3\)。
  6. 迭代直到无圈长<1。最终 LP 松弛最优解可能是每个圈约束都紧，分数解。
  7. 分支：选 \(x_{12}=0.5\) 分支。在 \(x_{12}=1\) 分支，该边在反馈边集中，从原图中删除该边（或固定变量），重新列生成。最终得到整数最优解：选两条边打破所有圈，例如 \(\{(1,2),(3,4)\}\) 总权重 2。

总结
本问题展示了如何用分支定价法处理约束指数多的线性规划松弛，其中定价子问题是在无向图中找最小权圈。通过列生成（实际是行生成）动态添加圈约束，结合分支定界处理整数性，得到精确解。此方法可推广到有向图的最小反馈弧集问题。

基于线性规划的图最小带权反馈边集问题的分支定价法求解示例 题目描述 考虑一个无向图 \(G = (V, E)\)，其中每条边 \(e \in E\) 有一个正整数权重 \(w_ e > 0\)。一个 反馈边集 是边集 \(F \subseteq E\) 的一个子集，使得从 \(G\) 中删除 \(F\) 中的所有边后，剩余的图不包含任何环（即成为一棵森林）。目标是找到一个反馈边集 \(F\)，使得其总权重 \(\sum_ {e \in F} w_ e\) 最小。该问题是 NP 难的，但可以通过整数规划建模，并利用分支定价法（Branch and Price，结合列生成和分支定界）求解。我们将逐步介绍其线性规划松弛的列生成求解过程，以及如何在分支定界框架中嵌入列生成。 解题过程 步骤1：整数规划建模 将每条边 \(e\) 是否选入反馈边集用一个 0-1 变量 \(x_ e\) 表示：若 \(e \in F\) 则 \(x_ e = 1\)，否则 \(x_ e = 0\)。我们需要删除至少一条来自每个环的边。但由于环的数量是指数级的，我们改用 覆盖所有圈 的思路。已知一个边集是反馈边集当且仅当它的补集 \(E \setminus F\) 是森林（即无环）。因此，可以等价地描述为：选取一个最大权森林（即最大生成森林），使得剩余边（即反馈边集）的权重最小。不过更直接的方法是：对每个圈，反馈边集必须包含该圈的至少一条边。这引出以下约束： 对每个圈（环）\(C \subseteq E\)，有 \[ \sum_ {e \in C} x_ e \ge 1. \] 因为如果圈上所有边都没有被选（即 \(x_ e = 0\) 对所有 \(e \in C\)），则删除后这个圈仍然存在，不满足无环。 于是得到整数规划模型： \[ \min \sum_ {e \in E} w_ e x_ e \] \[ \text{s.t.} \quad \sum_ {e \in C} x_ e \ge 1 \quad \forall \text{ 圈 } C, \] \[ x_ e \in \{0,1\} \quad \forall e \in E. \] 步骤2：线性规划松弛与对偶 首先求解其线性规划松弛（LP relaxation）：将 \(x_ e \in \{0,1\}\) 替换为 \(0 \le x_ e \le 1\)。约束个数（圈的数量）是指数级的，因此无法显式列出所有约束。我们采用 列生成 的思路，但这里“列”是对偶问题中的变量。更准确地说，这是一个约束指数多的问题，我们通过解其 对偶 来生成进入基的约束（即圈不等式）。这是“行生成”（或称切割生成）的一种形式。但因为常称为分支定价（包含列生成的思想），这里我们按标准术语称为分支定价。 原问题线性松弛： \[ \min \sum_ {e \in E} w_ e x_ e \] \[ \sum_ {e \in C} x_ e \ge 1 \quad \forall C \in \mathcal{C}, \] \[ 0 \le x_ e \le 1, \] 其中 \(\mathcal{C}\) 是所有圈的集合。 写出其对偶。对每个圈 \(C\) 引入对偶变量 \(y_ C \ge 0\)，对每条边 \(e\) 的原变量上界约束 \(x_ e \le 1\) 引入对偶变量 \(z_ e \ge 0\)（但这里我们不显式写 \(x_ e \le 1\)，因为它可以被圈约束隐含保证，不过为了完整性可以加上）。标准对偶推导：原问题有约束 \(A x \ge 1\)（每行对应一个圈），目标系数 \(w\)。对偶为： \[ \max \sum_ {C} y_ C \] \[ \text{s.t.} \quad \sum_ {C: e \in C} y_ C \le w_ e \quad \forall e \in E, \] \[ y_ C \ge 0 \quad \forall C. \] 这就是 圈填充问题 （cycle packing）：给每个圈分配一个非负值 \(y_ C\)，使得对每条边 \(e\)，包含 \(e\) 的所有圈的 \(y_ C\) 之和不超过 \(w_ e\)，最大化总圈值 \(\sum_ C y_ C\)。 步骤3：限制主问题与定价子问题 我们解原问题 LP 松弛时，并不枚举所有圈，而是维护一个圈的子集 \(\mathcal{C}' \subset \mathcal{C}\)，求解 限制主问题 （RMP）： \[ \min \sum_ {e} w_ e x_ e \] \[ \sum_ {e \in C} x_ e \ge 1 \quad \forall C \in \mathcal{C}', \] \[ x_ e \ge 0. \] （上界 \(x_ e \le 1\) 可省略，因为若 \(x_ e > 1\) 可减到 1 而不违反约束且目标更优。） 解 RMP 得到最优解 \(x^ \) 和对偶变量值（对每个圈约束 \(C \in \mathcal{C}'\) 有一个对偶变量 \(y_ C \ge 0\)）。我们还需要检查是否有一个圈 \(C \notin \mathcal{C}'\) 使得对应的约束被违反，即是否 \(\sum_ {e \in C} x_ e^ < 1\)。这样的圈就是需要加入 \(\mathcal{C}'\) 的“列”（对偶角度是行）。寻找这样一个圈等价于：在图上，每条边 \(e\) 赋予“长度” \(x_ e^ \)，找一个圈使得其总长 \(< 1\)。如果所有圈的长度都 \(\ge 1\)，则 \(x^ \) 是原 LP 松弛的最优解。 因此， 定价子问题 是在图上找一个圈 \(C\) 使得 \(\sum_ {e \in C} x_ e^* \) 最小。如果最小圈长 \( < 1\)，则将该圈加入 \(\mathcal{C}'\) 并重复；否则 LP 松弛已解到最优。 步骤4：子问题求解 子问题是 无向图最小权圈 问题，其中边权为 \(x_ e^* \ge 0\)。这可在多项式时间求解：对每条边 \((u,v)\)，计算去掉该边后从 \(u\) 到 \(v\) 的最短路（用 Dijkstra），加上该边的长度 \(x_ {(u,v)}^* \) 即为包含该边的最小圈长度。遍历所有边，取最小者，即可得到最小圈及其长度。复杂度 \(O(|E|(|V|\log |V| + |E|))\)。 步骤5：分支策略 当 RMP 的 LP 松弛解 \(x^ \) 不全为整数时，需要分支。常见的分支规则是：选一条边 \(e\) 使得 \(x_ e^ \) 分数（例如最接近 0.5），分成两支：\(x_ e = 0\) 和 \(x_ e = 1\)。 若 \(x_ e = 1\)，则该边必须在反馈边集中。在子问题中，可暂时固定它，并在后续的圈约束中不再考虑包含 \(e\) 的圈（因为已满足）。 若 \(x_ e = 0\)，则该边不在反馈边集中，则原图的圈约束必须由其他边满足。在子问题中，该边在圈中时仍需被覆盖。 在分支节点，我们需要在修改的问题上继续用列生成求解 LP 松弛。这需要在定价子问题中考虑固定边的情况。若 \(x_ e=1\)，则在求最小圈时可忽略那些包含 \(e\) 的圈（因为约束自动满足）；但为简单起见，可仍然允许生成这些圈，但它们在 RMP 中不会成为有效约束（因为约束右端变成 0？）。更系统的方法是调整 RMP 的约束形式：对固定 \(x_ e=1\) 的边，其所在圈约束可删去；对固定 \(x_ e=0\) 的边，在计算圈长度时该边的 \(x_ e^* =0\) 固定。这仍可适应。 步骤6：整体算法流程 初始化 \(\mathcal{C}'\) 为一组覆盖所有边的圈（例如每个三角形（如果存在）或通过任意生成树加一条边形成的圈）。 在当前分支节点，求解 RMP 的 LP 松弛，得 \(x^* \)。 调用定价子问题：求最小圈长 \(L\) 和对应的圈 \(C\)。 若 \(L < 1 - \epsilon\)（\(\epsilon\) 为容忍误差），将 \(C\) 加入 \(\mathcal{C}'\)，返回步骤 2。 若 \(L \ge 1 - \epsilon\)，该节点 LP 松弛解最优。若 \(x^* \) 全为整数，则更新当前最优解（若更好）。否则，选一个分数变量分支，创建两个子节点。 用分支定界框架搜索，在子节点重复步骤 2-5。 步骤7：示例演示 考虑简单图：\(V=\{1,2,3,4\}\)，边集合 \(E=\{(1,2),(2,3),(3,4),(4,1),(1,3)\}\)，权重均为 1。 初始化 \(\mathcal{C}'\) 包含一个圈，比如 \(C_ 1: 1-2-3-1\)（边集 \(\{(1,2),(2,3),(1,3)\}\)）。 解 RMP：只有一个约束 \(x_ {12}+x_ {23}+x_ {13} \ge 1\)，最小化 \(\sum x_ e\)，最优解 \(x_ {13}=1\)，其余 0，目标值 1。 定价子问题：边权 \(x^ \) 为 \((0,0,1,0,0)\) 对应边顺序同上。计算最小圈：对边 \((1,2)\)，去掉后最短路 1-3-2 长 0+0=0，加上 \(x_ {12}^ =0\) 得 0。发现圈 1-2-3-1 长 0+0+1=1 不优于 1，但圈 1-2-3-4-1 长 0+0+0+0=0<1。加入这个圈 \(C_ 2\)。 新 RMP 有两个圈约束，解得 \(x_ {12}=0.5, x_ {23}=0.5, x_ {34}=0, x_ {41}=0, x_ {13}=0.5\)，目标 1.5。 定价子问题：最小圈长？检查圈 1-3-4-1 长 0.5+0+0=0.5<1，加入 \(C_ 3\)。 迭代直到无圈长 <1。最终 LP 松弛最优解可能是每个圈约束都紧，分数解。 分支：选 \(x_ {12}=0.5\) 分支。在 \(x_ {12}=1\) 分支，该边在反馈边集中，从原图中删除该边（或固定变量），重新列生成。最终得到整数最优解：选两条边打破所有圈，例如 \(\{(1,2),(3,4)\}\) 总权重 2。 总结 本问题展示了如何用分支定价法处理约束指数多的线性规划松弛，其中定价子问题是在无向图中找最小权圈。通过列生成（实际是行生成）动态添加圈约束，结合分支定界处理整数性，得到精确解。此方法可推广到有向图的最小反馈弧集问题。