基于线性规划的图Steiner树问题的整数规划建模与分支定界法求解示例
字数 3422 2025-12-14 05:16:14

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

1. 问题描述

Steiner树问题是一个经典的组合优化问题。给定一个无向图 \(G = (V, E)\)，边权 \(w_e \geq 0\)（表示代价或长度），以及一个终端节点集合 \(T \subseteq V\)。目标是找到一个包含所有终端节点 \(T\) 的连通子图（通常是一棵树），使得该子图的边权总和最小。该子图可以包含非终端节点（称为Steiner节点），这有助于降低总代价。该问题是NP-hard的。

示例：设图有顶点 \(V = \{1,2,3,4,5\}\)，边权如下：\(w_{12}=4, w_{13}=3, w_{23}=2, w_{24}=5, w_{34}=1, w_{35}=6, w_{45}=3\)。终端集合 \(T = \{1,3,5\}\)。目标是找到连接这三个终端的最小代价Steiner树。

2. 整数规划建模

我们采用基于流（多商品流）的整数规划模型，它通过发送“流”来确保连通性。

决策变量：

  • \(x_e \in \{0, 1\}\)，如果边 \(e\) 被选入Steiner树中则为1，否则为0。
  • \(f_{ij}^k \geq 0\)（连续变量或整数），表示从某个指定的根终端节点 \(r \in T\) 到其他每个终端 \(k \in T \setminus \{r\}\) 的流。这里选择 \(r\) 为任意一个终端，例如 \(r=1\)。对每个 \(k \in T \setminus \{r\}\)，流变量 \(f_{ij}^k\) 表示从 \(r\) 到 \(k\) 沿着边 \((i,j)\) 方向发送的流大小。

目标函数：
最小化总边权：

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

约束条件：

  1. 容量约束：每条边上的总流不能超过该边是否被选的指示变量（乘以一个足够大的数，这里可以选 \(|T|-1\) 因为从根最多发出 \(|T|-1\) 单位的流到其他终端）：

\[ \sum_{k \in T \setminus \{r\}} (f_{ij}^k + f_{ji}^k) \leq (|T|-1) x_e, \quad \forall e=(i,j) \in E \]

这里 \(f_{ij}^k\) 和 \(f_{ji}^k\) 分别表示两个方向的流。

  1. 流守恒约束（对每个终端 \(k\) 和每个顶点 \(i\)）：
    • 对于根 \(r\)：它发送1单位流给每个其他终端 \(k\)：

\[ \sum_{j: (r,j) \in E} (f_{rj}^k - f_{jr}^k) = 1, \quad \forall k \in T \setminus \{r\} \]

  • 对于终端 \(k\)：它接收1单位流（即净流入为1）：

\[ \sum_{j: (k,j) \in E} (f_{jk}^k - f_{kj}^k) = 1, \quad \forall k \in T \setminus \{r\} \]

  • 对于其他所有节点 \(i \in V \setminus \{r, k\}\)（包括Steiner节点和其他终端节点）：净流量为0：

\[ \sum_{j: (i,j) \in E} (f_{ij}^k - f_{ji}^k) = 0, \quad \forall k \in T \setminus \{r\}, \ \forall i \in V \setminus \{r, k\} \]

  1. 变量域：

\[ x_e \in \{0,1\}, \quad f_{ij}^k \geq 0 \]

（注：实际上由于流变量是连续的且约束是线性的，最优解中流会自动取整数值，因为这是一个单商品流网络矩阵是全单模的，但这里我们为了建模的清晰性，仍保留为连续变量。）

为什么这个模型正确？

  • 约束1确保如果边被选中（\(x_e=1\)），则可以承载流；如果未选中（\(x_e=0\)），则不能有流通过，从而强制流只能在选中的边上流动。
  • 流守恒约束确保从根 \(r\) 到每个其他终端 \(k\) 存在一条流路径，这保证了所有终端都在同一个连通分量中（因为根和每个终端都连通）。
  • 由于流是沿着边发送的，且边权为正，最优解会自动形成一棵树（如果存在环，去掉环上的一条边仍满足流约束且代价更小，所以最优解是无环的）。

3. 求解方法：分支定界法

由于该整数规划是NP-hard，我们采用分支定界法来求解。

步骤1：线性规划松弛
将整数变量 \(x_e\) 松弛为 \(0 \leq x_e \leq 1\)，求解线性规划松弛。得到最优目标值 \(z_{LP}\) 和分数解 \(x_e^*\)。

步骤2：定界
线性规划松弛的解给出了原问题最优值的一个下界（因为最小化问题）。

步骤3：分支
如果所有 \(x_e^*\) 都是0或1，则得到整数最优解，结束。否则，选择一个分数变量 \(x_e\)（例如最接近0.5的）进行分支：

  • 左分支：强制 \(x_e = 0\)。
  • 右分支：强制 \(x_e = 1\)。
    这样就创建了两个子问题。

步骤4：求解子问题
对每个子问题，更新约束后重新求解线性规划松弛。

步骤5：剪枝
在分支过程中，根据以下规则剪枝（即不再探索该分支）：

  • 界剪枝：如果子问题的线性规划松弛目标值已经大于当前最好整数解的目标值（上界），则该分支不可能产生更好的整数解。
  • 整数解剪枝：如果子问题的松弛解是整数，则记录该整数解，并更新当前最好整数解（上界）。
  • 不可行剪枝：如果子问题不可行，则剪枝。

步骤6：继续搜索
重复步骤3-5，直到所有分支都被处理完毕。最后得到的最好的整数解就是最优Steiner树。

4. 应用到示例

图：\(V = \{1,2,3,4,5\}\)，边权如上，终端 \(T = \{1,3,5\}\)，选根 \(r=1\)。
线性规划松弛求解（可使用单纯形法）后，可能得到分数解。假设初始松弛解中某些 \(x_e\) 是分数。

分支过程示例：

  • 初始松弛解：\(x_{13}=0.8, x_{34}=0.6, x_{45}=0.6\)，其他为0或1？假设目标值下界为 \(z_{LP}=7\)。
  • 当前最好整数解（可能通过启发式得到）：例如选择边集 \(\{1-3, 3-4, 4-5\}\)（连通终端1,3,5），总代价 \(3+1+3=7\)，所以上界为7。
  • 由于下界=7，上界=7，所以最优值就是7？但注意下界是松弛的，可能需要分支检查是否真的能达到7的整数解。
  • 假设松弛解中 \(x_{13}=0.8\) 不是整数，选择它分支：
    • 分支1：设 \(x_{13}=0\)，重新求解线性规划。可能需要经过其他边（如1-2-3）连通终端1和3，这样松弛目标可能升高，例如变为7.5 > 上界7，所以剪枝。
    • 分支2：设 \(x_{13}=1\)，重新求解线性规划，此时解可能变为整数：\(x_{13}=1, x_{34}=1, x_{45}=1\)，其他为0，目标值=3+1+3=7，得到一个整数解，更新上界=7（其实不变）。
  • 由于所有分支处理完毕，且上界=下界=7，所以最优解就是边集 \(\{1-3, 3-4, 4-5\}\)，代价7。

5. 结果与扩展

该分支定界法最终找到了最优Steiner树：连接终端1,3,5，使用边(1,3)、(3,4)、(4,5)，总代价7。注意如果仅连接三个终端而不使用Steiner节点4，则可能的树是1-3-5（边1-3和3-5）代价3+6=9，或者1-2-3-5代价4+2+6=12，都大于7。因此利用Steiner节点4可以降低代价。

该方法可以推广到更复杂的图，但分支定界可能在最坏情况下指数时间。实际中常结合启发式、割平面（如加入割集约束）等加速。

基于线性规划的图Steiner树问题的整数规划建模与分支定界法求解示例 1. 问题描述 Steiner树问题是一个经典的组合优化问题。给定一个无向图 \( G = (V, E) \)，边权 \( w_ e \geq 0 \)（表示代价或长度），以及一个终端节点集合 \( T \subseteq V \)。目标是找到一个包含所有终端节点 \( T \) 的连通子图（通常是一棵树），使得该子图的边权总和最小。该子图可以包含非终端节点（称为Steiner节点），这有助于降低总代价。该问题是NP-hard的。 示例：设图有顶点 \( V = \{1,2,3,4,5\} \)，边权如下：\( w_ {12}=4, w_ {13}=3, w_ {23}=2, w_ {24}=5, w_ {34}=1, w_ {35}=6, w_ {45}=3 \)。终端集合 \( T = \{1,3,5\} \)。目标是找到连接这三个终端的最小代价Steiner树。 2. 整数规划建模 我们采用基于流（多商品流）的整数规划模型，它通过发送“流”来确保连通性。 决策变量 ： \( x_ e \in \{0, 1\} \)，如果边 \( e \) 被选入Steiner树中则为1，否则为0。 \( f_ {ij}^k \geq 0 \)（连续变量或整数），表示从某个指定的根终端节点 \( r \in T \) 到其他每个终端 \( k \in T \setminus \{r\} \) 的流。这里选择 \( r \) 为任意一个终端，例如 \( r=1 \)。对每个 \( k \in T \setminus \{r\} \)，流变量 \( f_ {ij}^k \) 表示从 \( r \) 到 \( k \) 沿着边 \( (i,j) \) 方向发送的流大小。 目标函数 ： 最小化总边权： \[ \min \sum_ {e \in E} w_ e x_ e \] 约束条件 ： 容量约束 ：每条边上的总流不能超过该边是否被选的指示变量（乘以一个足够大的数，这里可以选 \( |T|-1 \) 因为从根最多发出 \( |T|-1 \) 单位的流到其他终端）： \[ \sum_ {k \in T \setminus \{r\}} (f_ {ij}^k + f_ {ji}^k) \leq (|T|-1) x_ e, \quad \forall e=(i,j) \in E \] 这里 \( f_ {ij}^k \) 和 \( f_ {ji}^k \) 分别表示两个方向的流。 流守恒约束 （对每个终端 \( k \) 和每个顶点 \( i \)）： 对于根 \( r \)：它发送1单位流给每个其他终端 \( k \)： \[ \sum_ {j: (r,j) \in E} (f_ {rj}^k - f_ {jr}^k) = 1, \quad \forall k \in T \setminus \{r\} \] 对于终端 \( k \)：它接收1单位流（即净流入为1）： \[ \sum_ {j: (k,j) \in E} (f_ {jk}^k - f_ {kj}^k) = 1, \quad \forall k \in T \setminus \{r\} \] 对于其他所有节点 \( i \in V \setminus \{r, k\} \)（包括Steiner节点和其他终端节点）：净流量为0： \[ \sum_ {j: (i,j) \in E} (f_ {ij}^k - f_ {ji}^k) = 0, \quad \forall k \in T \setminus \{r\}, \ \forall i \in V \setminus \{r, k\} \] 变量域 ： \[ x_ e \in \{0,1\}, \quad f_ {ij}^k \geq 0 \] （注：实际上由于流变量是连续的且约束是线性的，最优解中流会自动取整数值，因为这是一个单商品流网络矩阵是全单模的，但这里我们为了建模的清晰性，仍保留为连续变量。） 为什么这个模型正确？ 约束1确保如果边被选中（\( x_ e=1 \)），则可以承载流；如果未选中（\( x_ e=0 \)），则不能有流通过，从而强制流只能在选中的边上流动。 流守恒约束确保从根 \( r \) 到每个其他终端 \( k \) 存在一条流路径，这保证了所有终端都在同一个连通分量中（因为根和每个终端都连通）。 由于流是沿着边发送的，且边权为正，最优解会自动形成一棵树（如果存在环，去掉环上的一条边仍满足流约束且代价更小，所以最优解是无环的）。 3. 求解方法：分支定界法 由于该整数规划是NP-hard，我们采用分支定界法来求解。 步骤1：线性规划松弛 将整数变量 \( x_ e \) 松弛为 \( 0 \leq x_ e \leq 1 \)，求解线性规划松弛。得到最优目标值 \( z_ {LP} \) 和分数解 \( x_ e^* \)。 步骤2：定界 线性规划松弛的解给出了原问题最优值的一个下界（因为最小化问题）。 步骤3：分支 如果所有 \( x_ e^* \) 都是0或1，则得到整数最优解，结束。否则，选择一个分数变量 \( x_ e \)（例如最接近0.5的）进行分支： 左分支：强制 \( x_ e = 0 \)。 右分支：强制 \( x_ e = 1 \)。 这样就创建了两个子问题。 步骤4：求解子问题 对每个子问题，更新约束后重新求解线性规划松弛。 步骤5：剪枝 在分支过程中，根据以下规则剪枝（即不再探索该分支）： 界剪枝 ：如果子问题的线性规划松弛目标值已经大于当前最好整数解的目标值（上界），则该分支不可能产生更好的整数解。 整数解剪枝 ：如果子问题的松弛解是整数，则记录该整数解，并更新当前最好整数解（上界）。 不可行剪枝 ：如果子问题不可行，则剪枝。 步骤6：继续搜索 重复步骤3-5，直到所有分支都被处理完毕。最后得到的最好的整数解就是最优Steiner树。 4. 应用到示例 图：\( V = \{1,2,3,4,5\} \)，边权如上，终端 \( T = \{1,3,5\} \)，选根 \( r=1 \)。 线性规划松弛求解（可使用单纯形法）后，可能得到分数解。假设初始松弛解中某些 \( x_ e \) 是分数。 分支过程示例 ： 初始松弛解：\( x_ {13}=0.8, x_ {34}=0.6, x_ {45}=0.6 \)，其他为0或1？假设目标值下界为 \( z_ {LP}=7 \)。 当前最好整数解（可能通过启发式得到）：例如选择边集 \( \{1-3, 3-4, 4-5\} \)（连通终端1,3,5），总代价 \( 3+1+3=7 \)，所以上界为7。 由于下界=7，上界=7，所以最优值就是7？但注意下界是松弛的，可能需要分支检查是否真的能达到7的整数解。 假设松弛解中 \( x_ {13}=0.8 \) 不是整数，选择它分支： 分支1：设 \( x_ {13}=0 \)，重新求解线性规划。可能需要经过其他边（如1-2-3）连通终端1和3，这样松弛目标可能升高，例如变为7.5 > 上界7，所以剪枝。 分支2：设 \( x_ {13}=1 \)，重新求解线性规划，此时解可能变为整数：\( x_ {13}=1, x_ {34}=1, x_ {45}=1 \)，其他为0，目标值=3+1+3=7，得到一个整数解，更新上界=7（其实不变）。 由于所有分支处理完毕，且上界=下界=7，所以最优解就是边集 \( \{1-3, 3-4, 4-5\} \)，代价7。 5. 结果与扩展 该分支定界法最终找到了最优Steiner树：连接终端1,3,5，使用边(1,3)、(3,4)、(4,5)，总代价7。注意如果仅连接三个终端而不使用Steiner节点4，则可能的树是1-3-5（边1-3和3-5）代价3+6=9，或者1-2-3-5代价4+2+6=12，都大于7。因此利用Steiner节点4可以降低代价。 该方法可以推广到更复杂的图，但分支定界可能在最坏情况下指数时间。实际中常结合启发式、割平面（如加入割集约束）等加速。