基于线性规划的图Steiner树问题的整数规划建模、分支定价法求解示例
字数 5675 2025-12-23 17:04:01

基于线性规划的图Steiner树问题的整数规划建模、分支定价法求解示例

题目描述

Steiner树问题是图论与组合优化中的一个经典NP-hard问题。给定一个无向图 \(G=(V,E)\)\)，边集 \(E\) 中每条边 \(e\) 有一个非负成本 \(c_e\)，以及一个终端节点集合 \(T \subseteq V\)。目标是找到一个包含所有终端节点的子树（即 Steiner树），使得其总边成本最小。该树可以包含非终端节点（称为 Steiner节点）以降低总成本。

本题要求：

  1. 建立 Steiner树问题的整数线性规划（ILP）模型。
  2. 由于问题规模较大时直接求解ILP困难，采用分支定价法（Branch-and-Price）进行求解，其中主问题为集合覆盖模型，子问题为资源约束最短路问题。
  3. 详细解释分支定价法的每一步，包括列生成、分支策略与定价子问题的建模。

解题过程循序渐进讲解

步骤1：整数线性规划建模（基于路径/树枚举的集合覆盖模型）

传统Steiner树的边变量模型（每个边 \(x_e \in \{0,1\}\) 表示是否选入树）虽直观，但线性松弛弱，且分支定界效率低。分支定价法常用集合覆盖模型：

  • 设 \(\mathcal{P}\) 为所有可能的“Steiner树”的集合（每个树是一个边的集合）。
  • 每个树 \(p \in \mathcal{P}\) 的成本为 \(c_p = \sum_{e \in p} c_e\)。
  • 引入二进制变量 \(y_p \in \{0,1\}\) 表示是否选择树 \(p\)。

目标是最小化总成本，并覆盖所有终端节点：每个终端 \(t \in T\) 必须被至少一条从根（任意指定一个终端为根 \(r \in T\)）到 \(t\) 的路径包含在某个选中的树中。但更自然的覆盖条件是：所选树的并集必须连通且包含所有终端。

更好的建模方式是将 Steiner树分解为从根到每个终端的路径的并集，并添加连通性约束。分支定价法中常用的模型是基于路径的集合覆盖模型：

  • 定义根节点 \(r \in T\)（任意固定）。
  • 对每个终端 \(t \in T \setminus \{r\}\)，令 \(\mathcal{P}_t\) 为所有从 \(r\) 到 \(t\) 的路径集合。
  • 对每条路径 \(p \in \mathcal{P}_t\)，引入变量 \(x_p \in \{0,1\}\) 表示是否选择该路径。
  • 目标：最小化总成本，但路径间共享边时成本不重复计算，这需要额外变量。因此改用资源约束模型，在定价子问题中计算路径成本。

为简化，常用基于树（Steiner树）的集合覆盖模型：

  • 主问题选择若干个Steiner树（每个树包含所有终端），使得每个边被覆盖的次数满足树的结构要求。但这样变量过多，因此采用列生成：主问题只考虑部分树（列），通过求解子问题生成负检验数的列（即可能降低成本的新树）。

实际常用的主问题模型（Set Covering Formulation for Steiner Tree）:

  • 对每个终端 \(t \in T\)，定义其必须与根 \(r\) 连通。
  • 但更常见的处理是：将 Steiner树视为一组从根到每个终端的路径，并要求这些路径共享边时成本只计一次。这可以通过流平衡约束或树状结构约束实现，但在列生成中，主问题通常为：
    • 最小化 \(\sum_{e \in E} c_e y_e\)
    • 满足：对每个终端子集 \(S \subseteq T, S \neq \emptyset, r \notin S\)，至少有一条边从 \(S\) 的补集进入 \(S\)（即割约束）。
    • 这是一个指数级约束的模型，适合用割平面法（如分支切割），但列生成中，主问题通常选择基于路径的松弛。

为了匹配分支定价的常见框架，我们采用以下模型：

主问题（Master Problem, MP）：

  • 令 \(\mathcal{S}\) 为所有可能的 Steiner树（包含所有终端）的集合。
  • 对每个树 \(s \in \mathcal{S}\)，成本 \(c_s = \sum_{e \in s} c_e\)，变量 \(\lambda_s \in \{0,1\}\) 表示是否选择该树。
  • 目标：最小化 \(\sum_{s \in \mathcal{S}} c_s \lambda_s\)。
  • 约束：必须选择一个树，即 \(\sum_{s \in \mathcal{S}} \lambda_s = 1\)。
  • 这是一个集合划分模型，但变量数指数级，因此用列生成：在分支定界树的每个节点，解线性松弛（\(\lambda_s \ge 0\)），通过子问题生成负检验数的列（即新的Steiner树）。

子问题（定价子问题）：
给定主问题对偶变量值，寻找一个 Steiner树 \(s\)（包含所有终端），使得其检验数 \(c_s - \sum \text{对偶乘子相关项} < 0\)。由于对偶变量与约束对应，而主问题只有一条约束，对偶变量为标量 \(\pi\)，检验数为 \(c_s - \pi\)，则子问题是求最小成本 Steiner树。但这样没有利用到更多对偶信息，因此实际常用基于路径的模型，将树分解为根到终端的路径，主问题包含覆盖每个终端的约束，从而产生多个对偶变量，子问题变为寻找最小“调整后成本”的路径。

但更标准的 Steiner树分支定价建模是基于树状图的资源约束最短路，将 Steiner树视为从根出发到各终端路径的叠加，在子问题中构建一个“ Steiner树”作为列，这比较复杂。为简化教学，我们采用以下实用设定：

简化建模（用于本示例）：

  1. 将 Steiner树问题转化为最小成本树状图问题，其中根为 \(r \in T\)，需要从根到每个终端 \(t \in T\setminus \{r\}\) 有路径，且允许路径共享边。
  2. 用流平衡约束保证树结构。
  3. 采用 Dantzig-Wolfe 分解：将每个“从根到终端的路径”作为一个列，主问题选择路径集合，使得每个终端被覆盖，且边使用量通过耦合约束控制成本。

但更常见的列生成方法用于 Steiner树是基于分支定价的集分割模型，子问题为资源约束最短路问题（RCSP），其中资源是终端覆盖情况。限于篇幅，下面给出一个具体数值例子，并略过过于复杂的 RCSP 细节，转而使用基于分支定价的整数规划模型，其中子问题直接求解一个最小 Steiner树问题（用动态规划或整数规划），但这样计算量大。实际中，分支定价用于 Steiner树的研究较少，更常见的是分支切割。但为满足题目要求，下面给出一个教学简化版流程。

步骤2：分支定价法框架

分支定价 = 列生成嵌入分支定界树。每个节点求解限制主问题（RMP，只包含部分列），然后通过子问题生成负检验数列，直到无负检验数，得到节点线性松弛解。若解为整数，则更新界；否则分支。

具体步骤：

  1. 初始化 RMP 列集合（如用最短路径树作为初始列）。
  2. 求解 RMP 的线性松弛，得到对偶变量值。
  3. 求解子问题（定价问题）：寻找检验数为负的列（Steiner树）。
  4. 若找到，加入 RMP，返回步骤2。
  5. 若无负检验数列，得到当前节点松弛最优解。若解分数，分支（如对边变量或节点变量分支）；若整数，更新全局界。
  6. 继续分支定界搜索。

步骤3：具体数值例子

考虑一个简单图，便于手动计算。

图例：

  • 节点：\(V = \{1,2,3,4\}\)，边集 \(E\) 与成本：
    • (1,2): 5
    • (1,3): 3
    • (2,3): 2
    • (2,4): 4
    • (3,4): 6
  • 终端集合 \(T = \{1,4\}\)，根 \(r=1\)。

目标：找最小成本 Steiner树连接节点1和4。注意非终端节点2、3可用可不用。

主问题（集合覆盖式）：
我们采用另一种常见模型：每个终端对之间的连通性通过选取边实现，但用列生成生成“整个树”作为列。这里为了简化，我们改用基于边的模型，而列生成用于处理 Steiner树的指数级割约束。但更标准的做法是：主问题为集合覆盖，子问题为最小 Steiner树（用动态规划求解小规模子图）。

但为示例，我们直接给出基于分支定价的求解逻辑：

  • 初始 RMP 列：用最短路径树（如路径 1-2-4，成本5+4=9）作为一个 Steiner树列 \(\lambda_1\)。
  • 线性松弛：解 \(\min 9\lambda_1\)，约束 \(\lambda_1 = 1\)，解 \(\lambda_1=1\)，成本9，对偶变量 \(\pi = 9\)（因为约束是 \(\sum \lambda_s = 1\)，对偶变量为标量）。
  • 子问题：求最小成本 Steiner树，使得检验数 \(c_s - \pi < 0\) 即 \(c_s < 9\)。已知最小 Steiner树是 1-3-4？成本3+6=9 不小于9。但 1-2-3-4 成本5+2+4=11>9。无负检验数，停止。但显然最优解是9（路径1-3-4 或 1-2-4）。

这例子太简单，无法体现列生成优势。我们改用稍复杂的例子：

新图：

  • 节点：1,2,3,4,5
  • 边成本：
    (1,2)=2, (1,3)=3, (2,3)=1, (2,4)=2, (3,4)=3, (3,5)=2, (4,5)=1
  • 终端 T={1,4,5}，根 r=1。

最优 Steiner树：边 (1,2),(2,3),(3,5),(4,5) 总成本 2+1+2+1=6（节点顺序1-2-3-5 和 4-5）。

列生成过程：

  1. 初始列：三个路径（根到每个终端）的并集作为初始树，如：
    路径到4: 1-2-4 (cost 2+2=4)
    路径到5: 1-2-4-5 (2+2+1=5)
    并集边：{1-2,2-4,4-5} 总成本 2+2+1=5，但未包含终端5的连通？实际上树应包含1,4,5，这棵树是 {1-2,2-4,4-5} 连通了1,4,5，成本5。但可能不是最小。
    用此树作为第一列 \(\lambda_1\)，成本5。
  2. 求解 RMP 线性松弛：\(\min 5\lambda_1\), \(\lambda_1=1\)，解 \(\lambda_1=1\)，对偶变量 \(\pi=5\)。
  3. 子问题：求最小 Steiner树，成本小于5的才有负检验数。已知最优成本6>5，所以无负检验数。但初始解成本5实际上不是可行 Steiner树？检查：树 {1-2,2-4,4-5} 确实连通1,4,5，是可行树，成本5。但图中存在成本5的树吗？边(1-2)=2, (2-4)=2, (4-5)=1 总成本5，是可行树，且确实是最优？但之前我们计算最优为6，矛盾。重新计算：树 {1-2,2-4,4-5} 连通1,4,5，总成本2+2+1=5，确实存在。但检查原图：边(2,4)=2 存在，是。所以最优就是5，不是6。我之前的计算有误。因此列生成结束，得到最优解成本5。

步骤4：分支定价的完整流程

  1. 初始列生成：用启发式（如最短路径树）生成初始树列加入RMP。
  2. 求解RMP线性松弛，得到对偶变量。
  3. 定价子问题：求解一个最小 Steiner树问题，其中边成本调整为 \(c_e - \sum \text{对偶乘子相关项}\)。这里“相关项”取决于主问题约束形式。如果主问题约束是每个终端必须被覆盖，则对偶乘子 \(\pi_t\) 对应每个终端 \(t\)，调整后边成本为 \(c_e - \sum_{t \text{ covered by paths using e}} \pi_t\) 等复杂形式。实际中，定价子问题通常建模为资源约束最短路问题，其中资源是“覆盖哪些终端”。
  4. 若子问题最优值<0，则生成新列（树）加入RMP，返回2。
  5. 若子问题最优值≥0，则当前节点松弛解最优。若解中 \(\lambda_s\) 分数，则分支（如选一条边e，分支为 \(y_e=0\) 或 \(y_e=1\)，其中 \(y_e=\sum_{s: e \in s} \lambda_s\)）。
  6. 继续分支定界搜索。

步骤5：定价子问题的建模示例

定价子问题：给定边成本 \(\bar{c}_e = c_e - \sum_{t} \alpha_{e,t} \pi_t\)（简化形式），找一棵包含所有终端的树，使总调整成本最小。这是一个 Steiner树问题，可以用整数规划快速求解（因为子图规模通常比原图小）。

整数规划模型（用于子问题）：

  • 变量：\(z_e \in \{0,1\}\) 表示边e是否在树中。
  • 目标：最小化 \(\sum_{e} \bar{c}_e z_e\)。
  • 约束：对每个终端子集 \(S\) 满足 \(S \cap T \neq \emptyset\) 且 \(T \not\subseteq S\)，有 \(\sum_{e \in \delta(S)} z_e \ge 1\)（割约束，保证连通性）。
  • 这是一个小规模整数规划，可用求解器快速求解。

步骤6：总结

  • Steiner树问题的分支定价法将指数级变量分解为主问题（选择树）和子问题（生成树）。
  • 定价子问题本身也是一个 Steiner树问题，但规模小，可用动态规划、整数规划或专门算法求解。
  • 分支策略通常基于边的使用量（分数解中 \(y_e\) 分数时分支）。
  • 该方法能处理中等规模实例，比直接整数规划更高效。

通过以上步骤，我们完成了 Steiner树问题的分支定价法求解框架的讲解，包括建模、列生成、定价子问题与分支策略。

基于线性规划的图Steiner树问题的整数规划建模、分支定价法求解示例 题目描述 Steiner树问题是图论与组合优化中的一个经典NP-hard问题。给定一个无向图 \(G=(V,E)\)\)，边集 \(E\) 中每条边 \(e\) 有一个非负成本 \(c_ e\)，以及一个终端节点集合 \(T \subseteq V\)。目标是找到一个包含所有终端节点的子树（即 Steiner树），使得其总边成本最小。该树可以包含非终端节点（称为 Steiner节点）以降低总成本。 本题要求： 建立 Steiner树问题的整数线性规划（ILP）模型。 由于问题规模较大时直接求解ILP困难，采用分支定价法（Branch-and-Price）进行求解，其中主问题为集合覆盖模型，子问题为资源约束最短路问题。 详细解释分支定价法的每一步，包括列生成、分支策略与定价子问题的建模。 解题过程循序渐进讲解 步骤1：整数线性规划建模（基于路径/树枚举的集合覆盖模型） 传统Steiner树的边变量模型（每个边 \(x_ e \in \{0,1\}\) 表示是否选入树）虽直观，但线性松弛弱，且分支定界效率低。分支定价法常用 集合覆盖模型 ： 设 \(\mathcal{P}\) 为所有可能的“Steiner树”的集合（每个树是一个边的集合）。 每个树 \(p \in \mathcal{P}\) 的成本为 \(c_ p = \sum_ {e \in p} c_ e\)。 引入二进制变量 \(y_ p \in \{0,1\}\) 表示是否选择树 \(p\)。 目标是最小化总成本，并 覆盖所有终端节点 ：每个终端 \(t \in T\) 必须被至少一条从根（任意指定一个终端为根 \(r \in T\)）到 \(t\) 的路径包含在某个选中的树中。但更自然的覆盖条件是：所选树的并集必须连通且包含所有终端。 更好的建模方式是将 Steiner树分解为从根到每个终端的路径的并集，并添加连通性约束。分支定价法中常用的模型是 基于路径的集合覆盖模型 ： 定义根节点 \(r \in T\)（任意固定）。 对每个终端 \(t \in T \setminus \{r\}\)，令 \(\mathcal{P}_ t\) 为所有从 \(r\) 到 \(t\) 的路径集合。 对每条路径 \(p \in \mathcal{P}_ t\)，引入变量 \(x_ p \in \{0,1\}\) 表示是否选择该路径。 目标：最小化总成本，但路径间共享边时成本不重复计算，这需要额外变量。因此改用 资源约束模型 ，在定价子问题中计算路径成本。 为简化，常用 基于树（Steiner树）的集合覆盖模型 ： 主问题选择若干个Steiner树（每个树包含所有终端），使得每个边被覆盖的次数满足树的结构要求。但这样变量过多，因此采用 列生成 ：主问题只考虑部分树（列），通过求解子问题生成负检验数的列（即可能降低成本的新树）。 实际常用的主问题模型（Set Covering Formulation for Steiner Tree） : 对每个终端 \(t \in T\)，定义其必须与根 \(r\) 连通。 但更常见的处理是：将 Steiner树视为一组从根到每个终端的路径，并要求这些路径共享边时成本只计一次。这可以通过 流平衡约束 或 树状结构约束 实现，但在列生成中，主问题通常为： 最小化 \(\sum_ {e \in E} c_ e y_ e\) 满足：对每个终端子集 \(S \subseteq T, S \neq \emptyset, r \notin S\)，至少有一条边从 \(S\) 的补集进入 \(S\)（即割约束）。 这是一个指数级约束的模型，适合用割平面法（如分支切割），但列生成中，主问题通常选择基于路径的松弛。 为了匹配分支定价的常见框架，我们采用以下模型： 主问题（Master Problem, MP） ： 令 \(\mathcal{S}\) 为所有可能的 Steiner树（包含所有终端）的集合。 对每个树 \(s \in \mathcal{S}\)，成本 \(c_ s = \sum_ {e \in s} c_ e\)，变量 \(\lambda_ s \in \{0,1\}\) 表示是否选择该树。 目标：最小化 \(\sum_ {s \in \mathcal{S}} c_ s \lambda_ s\)。 约束：必须选择一个树，即 \(\sum_ {s \in \mathcal{S}} \lambda_ s = 1\)。 这是一个 集合划分模型 ，但变量数指数级，因此用列生成：在分支定界树的每个节点，解线性松弛（\(\lambda_ s \ge 0\)），通过子问题生成负检验数的列（即新的Steiner树）。 子问题（定价子问题） ： 给定主问题对偶变量值，寻找一个 Steiner树 \(s\)（包含所有终端），使得其 检验数 \(c_ s - \sum \text{对偶乘子相关项} < 0\)。由于对偶变量与约束对应，而主问题只有一条约束，对偶变量为标量 \(\pi\)，检验数为 \(c_ s - \pi\)，则子问题是求最小成本 Steiner树。但这样没有利用到更多对偶信息，因此实际常用 基于路径的模型 ，将树分解为根到终端的路径，主问题包含覆盖每个终端的约束，从而产生多个对偶变量，子问题变为寻找最小“调整后成本”的路径。 但更标准的 Steiner树分支定价建模是 基于树状图的资源约束最短路 ，将 Steiner树视为从根出发到各终端路径的叠加，在子问题中构建一个“ Steiner树”作为列，这比较复杂。为简化教学，我们采用以下实用设定： 简化建模（用于本示例） ： 将 Steiner树问题转化为 最小成本树状图问题 ，其中根为 \(r \in T\)，需要从根到每个终端 \(t \in T\setminus \{r\}\) 有路径，且允许路径共享边。 用流平衡约束保证树结构。 采用 Dantzig-Wolfe 分解：将每个“从根到终端的路径”作为一个列，主问题选择路径集合，使得每个终端被覆盖，且边使用量通过耦合约束控制成本。 但更常见的列生成方法用于 Steiner树是 基于分支定价的集分割模型 ，子问题为 资源约束最短路问题（RCSP） ，其中资源是终端覆盖情况。限于篇幅，下面给出一个具体数值例子，并略过过于复杂的 RCSP 细节，转而使用 基于分支定价的整数规划模型 ，其中子问题直接求解一个 最小 Steiner树问题 （用动态规划或整数规划），但这样计算量大。实际中，分支定价用于 Steiner树的研究较少，更常见的是分支切割。但为满足题目要求，下面给出一个教学简化版流程。 步骤2：分支定价法框架 分支定价 = 列生成嵌入分支定界树。每个节点求解限制主问题（RMP，只包含部分列），然后通过子问题生成负检验数列，直到无负检验数，得到节点线性松弛解。若解为整数，则更新界；否则分支。 具体步骤 ： 初始化 RMP 列集合（如用最短路径树作为初始列）。 求解 RMP 的线性松弛，得到对偶变量值。 求解子问题（定价问题）：寻找检验数为负的列（Steiner树）。 若找到，加入 RMP，返回步骤2。 若无负检验数列，得到当前节点松弛最优解。若解分数，分支（如对边变量或节点变量分支）；若整数，更新全局界。 继续分支定界搜索。 步骤3：具体数值例子 考虑一个简单图，便于手动计算。 图例 ： 节点：\(V = \{1,2,3,4\}\)，边集 \(E\) 与成本： (1,2): 5 (1,3): 3 (2,3): 2 (2,4): 4 (3,4): 6 终端集合 \(T = \{1,4\}\)，根 \(r=1\)。 目标：找最小成本 Steiner树连接节点1和4。注意非终端节点2、3可用可不用。 主问题（集合覆盖式） ： 我们采用另一种常见模型：每个终端对之间的连通性通过选取边实现，但用列生成生成“整个树”作为列。这里为了简化，我们改用基于边的模型，而列生成用于处理 Steiner树的 指数级割约束 。但更标准的做法是：主问题为集合覆盖，子问题为最小 Steiner树（用动态规划求解小规模子图）。 但为示例，我们直接给出 基于分支定价的求解逻辑 ： 初始 RMP 列：用最短路径树（如路径 1-2-4，成本5+4=9）作为一个 Steiner树列 \(\lambda_ 1\)。 线性松弛：解 \(\min 9\lambda_ 1\)，约束 \(\lambda_ 1 = 1\)，解 \(\lambda_ 1=1\)，成本9，对偶变量 \(\pi = 9\)（因为约束是 \(\sum \lambda_ s = 1\)，对偶变量为标量）。 子问题：求最小成本 Steiner树，使得检验数 \(c_ s - \pi < 0\) 即 \(c_ s < 9\)。已知最小 Steiner树是 1-3-4？成本3+6=9 不小于9。但 1-2-3-4 成本5+2+4=11>9。无负检验数，停止。但显然最优解是9（路径1-3-4 或 1-2-4）。 这例子太简单，无法体现列生成优势。我们改用稍复杂的例子： 新图 ： 节点：1,2,3,4,5 边成本： (1,2)=2, (1,3)=3, (2,3)=1, (2,4)=2, (3,4)=3, (3,5)=2, (4,5)=1 终端 T={1,4,5}，根 r=1。 最优 Steiner树：边 (1,2),(2,3),(3,5),(4,5) 总成本 2+1+2+1=6（节点顺序1-2-3-5 和 4-5）。 列生成过程 ： 初始列：三个路径（根到每个终端）的并集作为初始树，如： 路径到4: 1-2-4 (cost 2+2=4) 路径到5: 1-2-4-5 (2+2+1=5) 并集边：{1-2,2-4,4-5} 总成本 2+2+1=5，但未包含终端5的连通？实际上树应包含1,4,5，这棵树是 {1-2,2-4,4-5} 连通了1,4,5，成本5。但可能不是最小。 用此树作为第一列 \(\lambda_ 1\)，成本5。 求解 RMP 线性松弛：\(\min 5\lambda_ 1\), \(\lambda_ 1=1\)，解 \(\lambda_ 1=1\)，对偶变量 \(\pi=5\)。 子问题：求最小 Steiner树，成本小于5的才有负检验数。已知最优成本6>5，所以无负检验数。但初始解成本5实际上不是可行 Steiner树？检查：树 {1-2,2-4,4-5} 确实连通1,4,5，是可行树，成本5。但图中存在成本5的树吗？边(1-2)=2, (2-4)=2, (4-5)=1 总成本5，是可行树，且确实是最优？但之前我们计算最优为6，矛盾。重新计算：树 {1-2,2-4,4-5} 连通1,4,5，总成本2+2+1=5，确实存在。但检查原图：边(2,4)=2 存在，是。所以最优就是5，不是6。我之前的计算有误。因此列生成结束，得到最优解成本5。 步骤4：分支定价的完整流程 初始列生成 ：用启发式（如最短路径树）生成初始树列加入RMP。 求解RMP线性松弛 ，得到对偶变量。 定价子问题 ：求解一个 最小 Steiner树问题 ，其中边成本调整为 \(c_ e - \sum \text{对偶乘子相关项}\)。这里“相关项”取决于主问题约束形式。如果主问题约束是每个终端必须被覆盖，则对偶乘子 \(\pi_ t\) 对应每个终端 \(t\)，调整后边成本为 \(c_ e - \sum_ {t \text{ covered by paths using e}} \pi_ t\) 等复杂形式。实际中，定价子问题通常建模为 资源约束最短路问题 ，其中资源是“覆盖哪些终端”。 若子问题最优值 <0，则生成新列（树）加入RMP，返回2。 若子问题最优值≥0，则当前节点松弛解最优。若解中 \(\lambda_ s\) 分数，则分支（如选一条边e，分支为 \(y_ e=0\) 或 \(y_ e=1\)，其中 \(y_ e=\sum_ {s: e \in s} \lambda_ s\)）。 继续分支定界搜索。 步骤5：定价子问题的建模示例 定价子问题：给定边成本 \( \bar{c} e = c_ e - \sum {t} \alpha_ {e,t} \pi_ t \)（简化形式），找一棵包含所有终端的树，使总调整成本最小。这是一个 Steiner树问题，可以用整数规划快速求解（因为子图规模通常比原图小）。 整数规划模型（用于子问题）： 变量：\(z_ e \in \{0,1\}\) 表示边e是否在树中。 目标：最小化 \(\sum_ {e} \bar{c}_ e z_ e\)。 约束：对每个终端子集 \(S\) 满足 \(S \cap T \neq \emptyset\) 且 \(T \not\subseteq S\)，有 \(\sum_ {e \in \delta(S)} z_ e \ge 1\)（割约束，保证连通性）。 这是一个小规模整数规划，可用求解器快速求解。 步骤6：总结 Steiner树问题的分支定价法将指数级变量分解为主问题（选择树）和子问题（生成树）。 定价子问题本身也是一个 Steiner树问题，但规模小，可用动态规划、整数规划或专门算法求解。 分支策略通常基于边的使用量（分数解中 \(y_ e\) 分数时分支）。 该方法能处理中等规模实例，比直接整数规划更高效。 通过以上步骤，我们完成了 Steiner树问题的分支定价法求解框架的讲解，包括建模、列生成、定价子问题与分支策略。