基于线性规划的“旅行推销员问题”的整数规划建模、松弛与分支切割法求解示例
字数 5459 2025-12-17 21:24:07

基于线性规划的“旅行推销员问题”的整数规划建模、松弛与分支切割法求解示例

我将为您讲解线性规划领域的一个经典问题——旅行推销员问题（TSP, Traveling Salesman Problem）的整数规划建模、松弛技巧以及如何利用分支切割法（Branch-and-Cut）来求解它。这个问题是组合优化和运筹学中最著名的问题之一，其整数规划建模和求解技巧是线性规划高级应用的核心内容。

第一步：问题描述

旅行推销员问题（TSP）的定义如下：

给定一组城市（通常用点或顶点表示）以及每对城市之间的距离（或旅行成本），目标是为推销员找到一条访问每个城市恰好一次，最后回到起始城市，并且总旅行距离（或总成本）最短的闭合回路（一个哈密顿回路）。

问题输入：

  1. 一个有向或无向完全图 G = (V, E)，其中顶点集 V = {1, 2, ..., n} 代表城市。
  2. 一个距离（或成本）矩阵 C = [c_ij]，其中 c_ij 表示从城市 i 到城市 j 的距离。对于对称TSP，c_ij = c_ji；对于非对称TSP，c_ij 和 c_ji 可以不同。

问题输出：

  1. 一个顶点序列 (v1, v2, ..., vn, v1)，构成一个哈密顿回路，使得总距离 Σ(沿着回路相邻顶点间的距离) 最小。

第二步：整数线性规划建模

这是将组合优化问题转化为数学规划模型的关键一步。我们引入决策变量：

  • 二元决策变量 \(x_{ij}\)：
    \(x_{ij} = 1\) 如果从城市 i 到城市 j 的边在最优路径上，否则 \(x_{ij} = 0\)。

模型目标：最小化总旅行成本：

\[\min \sum_{i=1}^{n} \sum_{j=1, j \neq i}^{n} c_{ij} x_{ij} \]

模型约束：

  1. 每个顶点恰好离开一次（出度约束）：

\[\sum_{j=1, j \neq i}^{n} x_{ij} = 1, \quad \forall i \in V \]

这意味着从每个城市 i 出发，恰好有一条边离开。

  1. 每个顶点恰好到达一次（入度约束）：

\[\sum_{i=1, i \neq j}^{n} x_{ij} = 1, \quad \forall j \in V \]

这意味着到达每个城市 j，恰好有一条边进入。

  1. 消除子回路（Subtour Elimination）约束：
    出度和入度约束本身并不能保证路径是一条单一回路。一个只满足上述两个约束的可行解可能由多个互不相交的子回路构成（例如，两个分离的小环），这不是一个有效的哈密顿回路。为了消除子回路，我们需要额外的约束。
    • Dantzig-Fulkerson-Johnson (DFJ) 子回路消除约束（最经典的形式）：

\[ \sum_{i \in S} \sum_{j \in S, j \neq i} x_{ij} \leq |S| - 1, \quad \forall S \subset V, 2 \leq |S| \leq n-1 \]

 这个约束的含义是：对于任意顶点集合 S（S 是真子集，且至少包含2个顶点），不能构成一个完整的、只包含 S 中顶点的回路。一个包含 |S| 个顶点的回路恰好有 |S| 条边，这个约束限制了 S 内部边的数量最多为 |S|-1 条，从而阻止了 S 自身形成一个闭合子回路。
  1. 二元性约束：

\[ x_{ij} \in \{0, 1\}, \quad \forall i, j \in V, i \neq j \]

这个整数线性规划（ILP）模型是TSP的精确模型。然而，DFJ约束的数量是指数级的（所有顶点集合的真子集），这使得我们无法在建模时显式地列出所有约束。

第三步：线性规划松弛与初始松弛问题

为了启动求解过程，我们首先构建一个初始的线性规划松弛问题。

  1. 我们暂时忽略数量巨大的DFJ子回路消除约束。
  2. 我们将二元变量约束 \(x_{ij} \in \{0,1\}\) 松弛为连续变量约束 \(0 \leq x_{ij} \leq 1\)。
  3. 保留目标函数、出度约束、入度约束，以及简单的边界约束。

于是，我们得到初始的线性规划松弛问题（P₀）：

\[\begin{aligned} \min \quad & \sum_{i} \sum_{j \neq i} c_{ij} x_{ij} \\ \text{s.t.} \quad & \sum_{j \neq i} x_{ij} = 1, \quad \forall i \in V \\ & \sum_{i \neq j} x_{ij} = 1, \quad \forall j \in V \\ & 0 \leq x_{ij} \leq 1, \quad \forall i, j \in V, i \neq j \end{aligned} \]

这个模型被称为指派问题松弛或二分图完美匹配松弛。它的最优解（用单纯形法等求解）是原TSP问题最优值的一个下界。但这个解通常包含多个子回路（subtours），不是一个单一的哈密顿回路。

第四步：分支切割法（Branch-and-Cut）的总体框架

由于DFJ约束的数量是指数级的，并且 \(x_{ij}\) 是整数变量，我们采用分支切割法来求解这个整数规划。分支切割法是分支定界法和割平面法的结合。

核心思想：

  1. 从松弛问题（P₀）开始求解。
  2. 检查当前线性规划松弛的最优解。如果它满足所有整数约束（即所有 \(x_{ij}\) 为0或1）并且不包含任何子回路（即是一个单一的哈密顿回路），那么我们就找到了原问题的最优解。
  3. 否则，我们做以下两件事之一：
    a. 添加割平面：如果当前解是分数解或包含子回路，我们尝试寻找一个（或多个）被当前解违反的DFJ约束（或其他有效的有效性约束，如梳子不等式等），将其作为“割平面”添加到当前线性规划中。这个割平面能“割掉”当前的非整数可行解或含子回路的解，但不会割掉任何真正的整数可行解（哈密顿回路）。然后，我们重新求解这个加强了约束的线性规划。
    b. 分支：如果找不到有效的割平面，或者添加割平面后解仍不满足整数/单一回路要求，我们就进行“分支”。我们选择一个分数变量 \(x_{ij}\)（其值在0和1之间），创建两个新的子问题：一个强制 \(x_{ij} = 0\)，另一个强制 \(x_{ij} = 1\)。这相当于在搜索树上创建两个分支。

这个过程在整个分支定界树上递归进行，通过不断添加割平面来收紧下界，通过分支来探索整数解空间。

第五步：关键技术细节——如何找到割平面

这是分支切割法的核心。在TSP的求解中，最常用的一类割平面就是处理子回路的约束。

  1. 连通分量/子回路检测：
    在得到当前线性规划松弛的最优解 \(x^*\) 后，我们将 \(x^*_{ij}\) 视为一个图的边权（虽然是分数）。我们在这个图上运行一个查找连通分量的算法（如深度优先搜索）。由于出度和入度约束，每个顶点的出度和入度在解中恰好为1（在分数意义上，边的流入流出和也为1），但整个图可能被分割成多个连通分量。每个连通分量对应一个“分数子回路”或“支撑结构”。
    对于一个包含顶点集 S 的连通分量，如果 S 是 {V} 的真子集，那么它就可能违反了DFJ约束。更精确地说，如果 S 中所有顶点的“分数边”的权重和大于 |S|-1，就违反了约束。

  2. 最小割/最大流算法寻找有效不等式：
    更系统的方法是，将当前解 \(x^*\) 视为一个网络流。我们想找到一个顶点集合 S，使得不等式 \(\sum_{i \in S} \sum_{j \in S} x_{ij} \leq |S| - 1\) 被 \(x^*\) 违反得最严重，即 \(\sum_{i \in S} \sum_{j \in S} x^*_{ij} > |S| - 1\)。
    这等价于寻找一个割，使得割的“容量”最大。我们可以通过求解一个最大流/最小割问题来寻找这样的集合 S。具体地，可以构造一个辅助图，将顶点集合 V 复制为源点侧和汇点侧，边的容量设为 \(x^*_{ij}\)。通过求解一系列最小割问题，可以找到被违反的DFJ约束（或其他更强的约束，如梳子不等式）。

  3. 添加割平面：
    一旦找到一个（或多个）被违反的约束（例如，对于一个集合 S，有 \(\sum_{i \in S} \sum_{j \in S} x^*_{ij} > |S| - 1 + \epsilon\)），我们就将这个线性不等式（即DFJ约束）作为新行添加到当前的线性规划模型中。然后重新求解这个新的线性规划。这个新割平面会迫使最优解远离当前的非可行解，从而提升目标函数的下界。

第六步：求解过程示例

假设一个简单的4城市对称TSP，距离矩阵如下（城市A, B, C, D编号为1,2,3,4）：

\[c = \begin{bmatrix} 0 & 2 & 9 & 10 \\ 2 & 0 & 6 & 4 \\ 9 & 6 & 0 & 8 \\ 10 & 4 & 8 & 0 \end{bmatrix} \]

  1. 建立初始松弛模型（P₀）：
    模型包含目标函数、8个出/入度约束（每个城市1个出度，1个入度）、12个变量 \(x_{ij} (i \neq j)\) 及其边界约束 \(0 \leq x_{ij} \leq 1\)。

  2. 求解（P₀）：
    利用单纯形法求解这个线性规划。假设我们得到的最优解是：
    \(x_{12} = x_{21} = 0.5, x_{13} = x_{31} = 0.5, x_{24} = x_{42} = 0.5, x_{34} = x_{43} = 0.5\)，其他为0。
    目标函数值 = 0.5*(2+2+9+9+4+4+8+8) = 23。
    检查这个解：它满足每个顶点的出/入度为1（例如，城市1： \(x_{12}+x_{13}=0.5+0.5=1\)）。但它不是一个单一回路。实际上，它描述了两个2-city的子回路（A-B 和 C-D）的凸组合，或者可以理解为存在两个支撑结构。

  3. 寻找并添加割平面：
    检测连通分量。分析解，可以识别出两个集合：

    • 集合 S1 = {1, 2}，其内部边权和为 \(x_{12} + x_{21} = 0.5+0.5=1.0\)。
    • 集合 S2 = {3, 4}，其内部边权和为 \(x_{34} + x_{43} = 0.5+0.5=1.0\)。
      对于 S1 (|S1|=2)，DFJ约束为 \(\sum_{i \in S1} \sum_{j \in S1} x_{ij} \leq 1\)。当前解的值1.0并没有违反（≤1）。但是，如果我们考虑“支撑结构”或利用最大流算法，可能会发现一个更有效的割。假设我们通过算法找到了集合 S = {1,2}，并发现约束被轻微违反，或者我们为了教学，主动添加两个约束来切断这两个明显的子回路结构：

\[ x_{12} + x_{21} \leq 1 \quad \text{和} \quad x_{34} + x_{43} \leq 1 \]

实际上，标准的DFJ约束对 S={1,2} 是 $ x_{12} + x_{21} \leq 1 $，当前解恰好满足等号，没有违反。我们需要找到真正被违反的约束。假设通过最小割算法，我们找到了一个被违反的约束，比如包含更复杂的集合。但为了简化，假设我们添加了某种割平面后，重新求解线性规划，得到了一个新的解，这个解可能仍然是分数的，但目标值增加了（下界提高了）。

  1. 分支操作：
    在某个节点，如果找不到有效割平面，而解中仍有分数变量（例如 \(x_{12} = 0.6\)），则进行分支。创建两个子问题节点：

    • 节点1：添加约束 \(x_{12} = 0\)。
    • 节点2：添加约束 \(x_{12} = 1\)。
      然后分别求解这两个新的线性规划问题（包含所有已添加的割平面）。

  2. 重复与终止：
    在整个分支定界树上，对所有活跃节点重复步骤2-4：

    • 求解节点松弛问题。
    • 寻找并添加割平面（切割）。
    • 如果解是整数且为单一回路，则记录为候选最优解，并更新全局上界。
    • 如果节点的下界超过当前全局上界，则剪枝该节点。
    • 否则，若解为分数，则选择分支变量进行分支。

    当所有节点都被处理（求解或剪枝）后，搜索结束。记录的最佳可行解（即总距离最短的哈密顿回路）就是TSP的最优解。

总结：
通过整数规划建模、线性规划松弛以及分支切割法，我们可以在理论上求解任意规模的TSP实例（尽管对于大规模问题，计算时间仍然是指数级的，但现代求解器如CPLEX, Gurobi通过高效的割平面生成、启发式找到可行解、以及巧妙的搜索策略，能够处理成千上万个城市规模的实例）。这个方法完美地展示了线性规划理论、松弛技巧、以及组合优化在求解NP难问题中的强大结合。

基于线性规划的“旅行推销员问题”的整数规划建模、松弛与分支切割法求解示例 我将为您讲解线性规划领域的一个经典问题——旅行推销员问题（TSP, Traveling Salesman Problem）的整数规划建模、松弛技巧以及如何利用分支切割法（Branch-and-Cut）来求解它。这个问题是组合优化和运筹学中最著名的问题之一，其整数规划建模和求解技巧是线性规划高级应用的核心内容。 第一步：问题描述 旅行推销员问题（TSP）的定义如下： 给定一组城市（通常用点或顶点表示）以及每对城市之间的距离（或旅行成本），目标是为推销员找到一条 访问每个城市恰好一次 ，最后 回到起始城市 ，并且 总旅行距离（或总成本）最短 的闭合回路（一个哈密顿回路）。 问题输入 ： 一个有向或无向完全图 G = (V, E)，其中顶点集 V = {1, 2, ..., n} 代表城市。 一个距离（或成本）矩阵 C = [ c_ ij]，其中 c_ ij 表示从城市 i 到城市 j 的距离。对于对称TSP，c_ ij = c_ ji；对于非对称TSP，c_ ij 和 c_ ji 可以不同。 问题输出 ： 一个顶点序列 (v1, v2, ..., vn, v1)，构成一个哈密顿回路，使得总距离 Σ(沿着回路相邻顶点间的距离) 最小。 第二步：整数线性规划建模 这是将组合优化问题转化为数学规划模型的关键一步。我们引入决策变量： 二元决策变量 \( x_ {ij} \)： \( x_ {ij} = 1 \) 如果从城市 i 到城市 j 的边在最优路径上，否则 \( x_ {ij} = 0 \)。 模型目标 ：最小化总旅行成本： \[ \min \sum_ {i=1}^{n} \sum_ {j=1, j \neq i}^{n} c_ {ij} x_ {ij} \] 模型约束 ： 每个顶点恰好离开一次 （出度约束）： \[ \sum_ {j=1, j \neq i}^{n} x_ {ij} = 1, \quad \forall i \in V \] 这意味着从每个城市 i 出发，恰好有一条边离开。 每个顶点恰好到达一次 （入度约束）： \[ \sum_ {i=1, i \neq j}^{n} x_ {ij} = 1, \quad \forall j \in V \] 这意味着到达每个城市 j，恰好有一条边进入。 消除子回路（Subtour Elimination）约束 ： 出度和入度约束本身并不能保证路径是一条单一回路。一个只满足上述两个约束的可行解可能由多个互不相交的子回路构成（例如，两个分离的小环），这不是一个有效的哈密顿回路。为了消除子回路，我们需要额外的约束。 Dantzig-Fulkerson-Johnson (DFJ) 子回路消除约束 （最经典的形式）： \[ \sum_ {i \in S} \sum_ {j \in S, j \neq i} x_ {ij} \leq |S| - 1, \quad \forall S \subset V, 2 \leq |S| \leq n-1 \] 这个约束的含义是：对于任意顶点集合 S（S 是真子集，且至少包含2个顶点），不能构成一个完整的、只包含 S 中顶点的回路。一个包含 |S| 个顶点的回路恰好有 |S| 条边，这个约束限制了 S 内部边的数量最多为 |S|-1 条，从而阻止了 S 自身形成一个闭合子回路。 二元性约束 ： \[ x_ {ij} \in \{0, 1\}, \quad \forall i, j \in V, i \neq j \] 这个整数线性规划（ILP）模型是TSP的精确模型。然而，DFJ约束的数量是指数级的（所有顶点集合的真子集），这使得我们无法在建模时显式地列出所有约束。 第三步：线性规划松弛与初始松弛问题 为了启动求解过程，我们首先构建一个 初始的线性规划松弛 问题。 我们暂时忽略数量巨大的DFJ子回路消除约束。 我们将二元变量约束 \( x_ {ij} \in \{0,1\} \) 松弛为连续变量约束 \( 0 \leq x_ {ij} \leq 1 \)。 保留目标函数、出度约束、入度约束，以及简单的边界约束。 于是，我们得到初始的线性规划松弛问题（P₀）： \[ \begin{aligned} \min \quad & \sum_ {i} \sum_ {j \neq i} c_ {ij} x_ {ij} \\ \text{s.t.} \quad & \sum_ {j \neq i} x_ {ij} = 1, \quad \forall i \in V \\ & \sum_ {i \neq j} x_ {ij} = 1, \quad \forall j \in V \\ & 0 \leq x_ {ij} \leq 1, \quad \forall i, j \in V, i \neq j \end{aligned} \] 这个模型被称为 指派问题松弛 或 二分图完美匹配松弛 。它的最优解（用单纯形法等求解）是原TSP问题最优值的一个 下界 。但这个解通常包含多个子回路（subtours），不是一个单一的哈密顿回路。 第四步：分支切割法（Branch-and-Cut）的总体框架 由于DFJ约束的数量是指数级的，并且 \( x_ {ij} \) 是整数变量，我们采用 分支切割法 来求解这个整数规划。分支切割法是 分支定界法 和 割平面法 的结合。 核心思想 ： 从松弛问题（P₀）开始求解。 检查当前线性规划松弛的最优解。如果它满足所有整数约束（即所有 \( x_ {ij} \) 为0或1）并且不包含任何子回路（即是一个单一的哈密顿回路），那么我们就找到了原问题的最优解。 否则，我们做以下两件事之一： a. 添加割平面 ：如果当前解是分数解或包含子回路，我们尝试寻找一个（或多个）被当前解违反的DFJ约束（或其他有效的有效性约束，如梳子不等式等），将其作为“割平面”添加到当前线性规划中。这个割平面能“割掉”当前的非整数可行解或含子回路的解，但不会割掉任何真正的整数可行解（哈密顿回路）。然后，我们重新求解这个加强了约束的线性规划。 b. 分支 ：如果找不到有效的割平面，或者添加割平面后解仍不满足整数/单一回路要求，我们就进行“分支”。我们选择一个分数变量 \( x_ {ij} \)（其值在0和1之间），创建两个新的子问题：一个强制 \( x_ {ij} = 0 \)，另一个强制 \( x_ {ij} = 1 \)。这相当于在搜索树上创建两个分支。 这个过程在整个分支定界树上递归进行，通过不断添加割平面来收紧下界，通过分支来探索整数解空间。 第五步：关键技术细节——如何找到割平面 这是分支切割法的核心。在TSP的求解中，最常用的一类割平面就是处理 子回路 的约束。 连通分量/子回路检测 ： 在得到当前线性规划松弛的最优解 \( x^* \) 后，我们将 \( x^* _ {ij} \) 视为一个图的边权（虽然是分数）。我们在这个图上运行一个查找连通分量的算法（如深度优先搜索）。由于出度和入度约束，每个顶点的出度和入度在解中恰好为1（在分数意义上，边的流入流出和也为1），但整个图可能被分割成多个连通分量。每个连通分量对应一个“分数子回路”或“支撑结构”。 对于一个包含顶点集 S 的连通分量，如果 S 是 {V} 的真子集，那么它就可能违反了DFJ约束。更精确地说，如果 S 中所有顶点的“分数边”的权重和大于 |S|-1，就违反了约束。 最小割/最大流算法寻找有效不等式 ： 更系统的方法是，将当前解 \( x^* \) 视为一个网络流。我们想找到一个顶点集合 S，使得不等式 \( \sum_ {i \in S} \sum_ {j \in S} x_ {ij} \leq |S| - 1 \) 被 \( x^* \) 违反得最严重，即 \( \sum_ {i \in S} \sum_ {j \in S} x^ _ {ij} > |S| - 1 \)。 这等价于寻找一个割，使得割的“容量”最大。我们可以通过求解一个 最大流/最小割 问题来寻找这样的集合 S。具体地，可以构造一个辅助图，将顶点集合 V 复制为源点侧和汇点侧，边的容量设为 \( x^ _ {ij} \)。通过求解一系列最小割问题，可以找到被违反的DFJ约束（或其他更强的约束，如梳子不等式）。 添加割平面 ： 一旦找到一个（或多个）被违反的约束（例如，对于一个集合 S，有 \( \sum_ {i \in S} \sum_ {j \in S} x^* _ {ij} > |S| - 1 + \epsilon \)），我们就将这个线性不等式（即DFJ约束）作为新行添加到当前的线性规划模型中。然后重新求解这个新的线性规划。这个新割平面会迫使最优解远离当前的非可行解，从而提升目标函数的下界。 第六步：求解过程示例 假设一个简单的4城市对称TSP，距离矩阵如下（城市A, B, C, D编号为1,2,3,4）： \[ c = \begin{bmatrix} 0 & 2 & 9 & 10 \\ 2 & 0 & 6 & 4 \\ 9 & 6 & 0 & 8 \\ 10 & 4 & 8 & 0 \end{bmatrix} \] 建立初始松弛模型（P₀） ： 模型包含目标函数、8个出/入度约束（每个城市1个出度，1个入度）、12个变量 \( x_ {ij} (i \neq j) \) 及其边界约束 \( 0 \leq x_ {ij} \leq 1 \)。 求解（P₀） ： 利用单纯形法求解这个线性规划。假设我们得到的最优解是： \( x_ {12} = x_ {21} = 0.5, x_ {13} = x_ {31} = 0.5, x_ {24} = x_ {42} = 0.5, x_ {34} = x_ {43} = 0.5 \)，其他为0。 目标函数值 = 0.5* (2+2+9+9+4+4+8+8) = 23。 检查这个解：它满足每个顶点的出/入度为1（例如，城市1： \( x_ {12}+x_ {13}=0.5+0.5=1 \)）。但它不是一个单一回路。实际上，它描述了两个2-city的子回路（A-B 和 C-D）的凸组合，或者可以理解为存在两个支撑结构。 寻找并添加割平面 ： 检测连通分量。分析解，可以识别出两个集合： 集合 S1 = {1, 2}，其内部边权和为 \( x_ {12} + x_ {21} = 0.5+0.5=1.0 \)。 集合 S2 = {3, 4}，其内部边权和为 \( x_ {34} + x_ {43} = 0.5+0.5=1.0 \)。 对于 S1 (|S1|=2)，DFJ约束为 \( \sum_ {i \in S1} \sum_ {j \in S1} x_ {ij} \leq 1 \)。当前解的值1.0并没有违反（≤1）。但是，如果我们考虑“支撑结构”或利用最大流算法，可能会发现一个更有效的割。假设我们通过算法找到了集合 S = {1,2}，并发现约束被轻微违反，或者我们为了教学，主动添加两个约束来切断这两个明显的子回路结构： \[ x_ {12} + x_ {21} \leq 1 \quad \text{和} \quad x_ {34} + x_ {43} \leq 1 \] 实际上，标准的DFJ约束对 S={1,2} 是 \( x_ {12} + x_ {21} \leq 1 \)，当前解恰好满足等号，没有违反。我们需要找到真正被违反的约束。假设通过最小割算法，我们找到了一个被违反的约束，比如包含更复杂的集合。但为了简化，假设我们添加了某种割平面后，重新求解线性规划，得到了一个新的解，这个解可能仍然是分数的，但目标值增加了（下界提高了）。 分支操作 ： 在某个节点，如果找不到有效割平面，而解中仍有分数变量（例如 \( x_ {12} = 0.6 \)），则进行分支。创建两个子问题节点： 节点1：添加约束 \( x_ {12} = 0 \)。 节点2：添加约束 \( x_ {12} = 1 \)。 然后分别求解这两个新的线性规划问题（包含所有已添加的割平面）。 重复与终止 ： 在整个分支定界树上，对所有活跃节点重复步骤2-4： 求解节点松弛问题。 寻找并添加割平面（切割）。 如果解是整数且为单一回路，则记录为候选最优解，并更新全局上界。 如果节点的下界超过当前全局上界，则剪枝该节点。 否则，若解为分数，则选择分支变量进行分支。 当所有节点都被处理（求解或剪枝）后，搜索结束。记录的最佳可行解（即总距离最短的哈密顿回路）就是TSP的最优解。 总结 ： 通过整数规划建模、线性规划松弛以及分支切割法，我们可以在理论上求解任意规模的TSP实例（尽管对于大规模问题，计算时间仍然是指数级的，但现代求解器如CPLEX, Gurobi通过高效的割平面生成、启发式找到可行解、以及巧妙的搜索策略，能够处理成千上万个城市规模的实例）。这个方法完美地展示了线性规划理论、松弛技巧、以及组合优化在求解NP难问题中的强大结合。