🔢 mathematics

A Numerically-safe Branch-Price-and-Cut Algorithm for the Length-Constrained Cycle Partition Problem

本文提出了一种具有高效动态规划定价策略且数值安全的分支定价割平面算法，该算法在解决长度受限循环划分问题方面显著优于现有方法，能够求解更大规模的实例并解决此前未解的案例。

原作者： Mohammed Ghannam, Ambros Gleixner, Gioni Mexi, Edward Lam

发布于 2026-07-20✓ Author reviewed ⓘ

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Mohammed Ghannam, Ambros Gleixner, Gioni Mexi, Edward Lam

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你是某家无人机配送机队的经理。你的任务是安排无人机前往不同的配送停靠点。这些停靠点可不是普通的地点，每一个地点都有一个非常具体的“时间限制”：有些地点非常紧急，必须在极短的时间内完成访问；而有些地点则相对不那么紧迫，可以稍后处理。

每个停靠点都必须定期访问，并且有一个非常具体的、不可逾越的规则：它有一个“关键时间”，即在该特定地点被再次服务之前，允许经过的最大时间。

你的任务是找出最有效的方法，将所有的配送停靠点组合成循环路径。你希望使用的无人机数量尽可能少，但你创建的每一个循环都必须足够短，以确保该组中所有访问节点中“最紧急”的那个时间限制，能够决定整个行程的上限。换句话说，一个循环的总时长不能超过该路径所经过的所有地点中，那个最紧迫时间限制的最小值。这是一个关于几何与时间的谜题，数学家们称之为“长度受限循环划分问题”（Length-Constrained Cycle Partition Problem）。这类挑战在现实生活中屡见不鲜，比如安排城市安保巡逻或组织肾脏交换，但要完美解决它极其困难。这就像是在尝试解决一个巨大的拼图游戏，而且拼图块的大小还会根据你尝试组合它们的方式而不断变化。

这篇论文介绍了一种全新的、超级智能的方法来解决这个谜题，这种方法不仅速度更快，而且在数学处理上极其严谨。作者们是一支来自德国和澳大利亚的研究团队，他们构建了一个“分支定价割平面”（branch-price-and-cut）算法。你可以把这想象成一位侦探，他不仅仅是在猜测线索，而是系统地构建一张所有可能解的地图，剪掉那些不可能的选项，并为那些有希望的选项进行“定价”，以找到绝对最优的路径。他们的秘密武器是一种名为“列生成”（column generation）的技术，这就像是盖房子时只订购当前立刻需要的特定砖块，而不是试图一次性把整座砖山都运到工地现场。他们还加入了一个“数值安全”功能，这就像是一个双重检查系统，确保计算机不会因为微小的舍入误差而导致错误答案。

结果令人印象深刻。团队在 84 个不同的测试实例上测试了他们的方法，这些实例规模从只有 14 个节点的微型设置到拥有 100 个节点的大型设置不等。他们的新算法成功将其中 52 个实例求解到了证明后的完美解，其中包括一个拥有 76 个节点的实例——这一规模此前从未被解决过（之前的纪录是 52 个节点）。他们还解决了 14 个此前无法求解的实例。在速度方面，他们的方法平均比之前的最佳方法快了 14.7 倍。他们发现最重要的技巧是“对称性破缺”（告诉计算机不要因为循环的起点不同就浪费时间去重复检查同一个循环）和“双向搜索”（同时从两端构建循环并在中间汇合）。他们还尝试添加额外的“割平面”（用于剔除差选项的数学规则），但他们发现对于大多数情况，由于谜题本身已经非常紧凑，这些额外的规则并没有什么帮助，有时甚至会拖慢速度。论文最后指出，虽然他们已经破解了高达 76 个节点的代码，但真正的瓶颈现在在于定价程序的运行速度，要解决规模更大的谜题，可能还需要更强大的计算技巧。

技术摘要：一种用于长度受限环路划分问题的数值安全分支定价割平面算法

1. 问题定义

长度受限环路划分问题 (Length-Constrained Cycle Partition Problem, LCCP) 是一个定义在无向图 $G=(V, E)$ 上的图优化问题。其目标是将节点集 $V$ 划分为最少数量的互不相交的环路，使得每个节点 $i$ 被恰好覆盖一次。

每个节点 $i$ 与一个关键时间 $q_i > 0$ 相关联，每条边 $\{i, j\}$ 具有旅行时间 $t_{i,j} \ge 0$ 。一个环路 $C$ 被认为是长度可行的，如果其总旅行时间不超过其中任何节点的关键时间：
$t(C) := \sum_{\{i,j\} \in C} t_{i,j} \le \min_{i \in C} \{q_i\}$
该问题已知是 NP-hard 的（可由旅行商问题归约而来），且不存在多项式时间近似算法。以往的最先进方法利用紧凑型混合整数规划 (MIP) 模型（基于 Miller-Tucker-Zemlin 或子回路消除约束）来解决规模在 52 个节点以内的实例。

2. 方法论

作者提出了一种基于 集合划分 (Set Partitioning, SP) 模型的高效 分支定价割平面 (Branch-Price-and-Cut, BPC) 算法。

2.1 集合划分模型

该问题并非采用紧凑型模型，而是建模为一个集合划分问题，其中变量代表整个长度可行的环路。令 $\Omega$ 为所有长度可行环路的集合。该模型通过最小化 $\sum_{C \in \Omega} \lambda_C$ 来进行优化，并受限于覆盖约束 $\sum_{C \in \Omega} a^C_i \lambda_C = 1$ （对于所有 $i \in V$ ）。由于 $\Omega$ 的规模呈指数级增长，作者采用 列生成 (Column Generation) 技术来动态求解线性规划 (LP) 松弛问题。

2.2 定价问题 (LCPCCP)

核心计算任务是 长度受限奖金收集环路问题 (Length-Constrained Prize-Collecting Cycle Problem, LCPCCP)，即寻找具有负简化成本的环路。该问题是强 NP-hard 的。作者使用以下方法求解该问题：

动态规划 (DP)： 一种标签设定算法，标签记录了已访问节点、简化成本、总旅行时间以及路径的最小关键时间。
双向搜索： 利用无向图的特性，算法从起始节点 $s$ 向前扩展标签，直到满足 $t(\ell) < q(\ell)/2$ 。随后，将来自前向和后向搜索的非支配标签进行合并，以形成完整的环路。与单向搜索相比，这显著减少了搜索空间。
支配规则： 如果在同一节点处，另一个标签具有更低或相等的简化成本、更低或相等的旅行时间以及被访问节点的子集，则该标签会被剪枝。
ng-松弛 (ng-Relaxation)： 为了处理非基本环路（重复访问节点），作者使用了带有动态邻域扩展的 ng-路径松弛。这提供了有效的下界，同时避免了在初始搜索阶段严格执行基本性（elementarity）的复杂性。
贪婪启发式算法： 首先运行快速启发式算法，通过移除负对偶节点或插入正对偶节点来寻找改进的环路，从而减少昂贵的 DP 迭代需求。

2.3 利用结构特性

三角不等式： 对于满足局部三角不等式的节点，作者切换到集合覆盖约束。这限制了对偶变量为非负，从而允许在定价过程中移除对偶值为零的节点，并实现预先剪枝。
对称性破缺： 为了避免从不同的起始节点生成相同的环路，搜索被限制为仅访问关键时间大于或等于起始节点关键时间的节点（通过索引进行平局处理）。

2.4 割平面

算法集成了两类割平面：

子集行割 (Subset Row Cuts, SRCs)： 应用于节点子集，以限制覆盖这些节点的环路数量。
团割 (Clique Cuts, CCs)： 基于环路的冲突图。
作者研究了在定价问题中遵循这些割平面的情况。研究发现，虽然为了避免复杂性而在定价中忽略了团割，但 子集行割 通过在标签中增加额外的资源约束得到遵循，这在特定的困难实例上提高了收敛性。

2.5 数值安全性

一个关键贡献是实现了 数值安全的边界。浮点运算可能因舍入误差导致不可行的对偶解。作者提出了一个对偶修复机制：

将浮点对偶值缩放为大整数。
使用整数算术精确验证对偶可行性。
若不可行，则降低缩放因子并重试。
这确保了用于分支的下界在数学上是严谨的，防止算法基于数值伪影声称达到了最优性。

2.6 分支与启发式算法

分支： 主要使用 边分支 (Edge Branching)（将边固定为属于或不属于解）。虽然也测试了 Ryan-Foster 分支（基于节点对），但发现其在该特定问题结构下的鲁棒性较差。
启发式算法： 一种分支定价变体通过放宽支配规则来寻找高质量的原问题解，这些解随后被用作精确求解器的热启动（warm starts）。

3. 主要贡献

集合划分模型： 证明了基于 SP 的方法能产生显著更紧的 LP 松弛（平均根节点间隙为 0.4%），而之前的紧凑型模型间隙为 30.3%。
双向 DP 定价： 为 LCPCCP 定价问题引入了高效的双向搜索，利用无向图的对称性来削减搜索空间。
数值安全性： 提供了一个通过结合浮点求解器与精确整数算术进行对偶验证，从而获得证明正确的下界的框架。
算法集成： 将贪婪定价、ng-松弛、对称性破缺和特定的割平面管理整合为一个统一的求解器。

4. 计算结果

该算法在 84 个基准实例（14 到 100 个节点）上针对之前的最先进分支割平面法 (bnc-sec) 进行了测试。

性能： 所提出的分支定价割平面算法（特别是配置 withsrc+pricing）解决了 52 个实例 以达到证明的最优性，而之前最好的方法解决了 40 个。
规模： 它成功解决了规模高达 76 个节点 的实例，填补了 14 个此前未解决的空白。此前的极限为 52 个节点。
速度： 该分支定价核心平均比之前最好的方法快 14.7 倍。
根节点效率： 在 52 个已解决的实例中，有 49 个在无需分支的情况下直接在根节点处解决，凸显了 LP 松弛的强度。
数值安全性开销： 数值安全版本解决的实例数量与非安全版本相同，但速度慢了约 40%（几何平均值分别为 7.6s 和 4.5s）。然而，未在非安全版本中检测到错误结果，且该开销在保证正确性的前提下被认为是适度的。

5. 重要性与声明

论文声称 集合划分模型 是性能的主要驱动力，它提供了强大的边界，使得大多数实例能在根节点处解决。双向搜索 和 对称性破缺 被确定为减少运行时间最有效的算法组件。

作者谦虚地指出，虽然该方法显著提升了现有技术水平，但超过 76 个节点的实例仍未解决，且定价程序仍然是计算瓶颈。他们建议，未来的改进可能需要更强的对偶下界或更具扩展性的定价算法（例如 GPU 加速）。这项工作为解决 LCCP 建立了新的基准，证明了通过结合数值安全和利用结构的技巧，精确方法可以处理更大、更复杂的实例。