🔬 condensed matter

Ising-Machine-Assisted Large Neighborhood Search with Flexibly Tunable Subproblem Size

本文提出了 LNS-VT，这是一种新型的由伊辛机辅助的大邻域搜索方法，该方法引入了一个用于控制每辆车连续重新优化步数的可调参数，以在保持可行性的同时精细控制子问题规模，从而显著提高了车辆路径问题的解质量，并证明了子问题规模控制对于其他组合优化任务的重要性。

原作者： Koshiro Fujimoto, Masashi Yamashita, Shu Tanaka

发布于 2026-07-07

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Koshiro Fujimoto, Masashi Yamashita, Shu Tanaka

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

大局观：用“魔法盒”解决不可能的谜题

想象你有一个巨大且极其困难的拼图。也许是计算如何让一家快递公司用 5 辆卡车最有效地配送 300 个包裹，或者是决定如何将 200 件不同的物品装进 5 个背包，以便在不损坏背包的前提下获得最大价值。

在计算机科学领域，这些被称为组合优化问题。可能的解决方案排列组合的数量如此之大（就像沙滩上的沙粒数量一样），以至于即使是最快的超级计算机也无法检查每一个选项来找到那个“完美”的解。

这时，**伊辛机（Ising Machine）**登场了。你可以把它想象成一个“魔法盒”（一种专门设计的计算机），旨在非常快速地找到优秀的解。它的工作原理是将你的谜题转化为一个能量景观：“最佳”解位于山谷的最低点，而机器会自然而然地向低处滚动，从而找到它。

问题所在：
如果你试图一次性把整个 300 个包裹的谜题喂给这个“魔法盒”，会出现两个问题：

过载： 谜题对于这个盒子来说太大了，处理不了。
违反规则： 盒子可能会找到一个“低能量”的解，但却违反了规则（例如：一辆卡车两次访问同一个地点，或者超重了）。

旧策略：“大块头” (LNS-V)

为了解决这个问题，研究人员使用了一种叫做**大邻域搜索（Large Neighborhood Search, LNS）**的方法。他们不再试图一次性解决整个谜题，而是取出当前解的一个小部分，将其丢弃，然后要求“魔法盒”只重新解决这小小的一部分。接着，再将这个新生成的碎片缝合回去。

论文讨论了一种现有的方法，称为 LNS-V。

它是如何工作的： 假设你有 5 辆送货卡车。LNS-V 会挑选出，比如，2 辆卡车，取走它们完整的路线（即它们经过的所有停靠点），然后要求“魔法盒”重新排列这些停靠点。另外 3 辆卡车则保持原样。
缺陷： 这就像是在调节收音机的音量，但你手里的按钮只能让你在“静音”、“大声”和“震耳欲聋”之间切换。你无法调节到“中等”音量。
- 如果你选 2 辆卡车，这个谜题碎片就太大了。
- 如果你选 1 辆卡车，这个谜题碎片又太小了。
- 在两者之间不存在“刚刚好”的大小。有时候，这个碎片太大，导致“魔法盒”无法很好地解决；有时候，它又太小，无法带来实质性的改进。

新策略：“精细切片” (LNS-VT)

作者提出了一种新方法，称为 LNS-VT（VT 代表“变量调优/Variable Tuning”）。

类比： 想象你正在剪辑一部电影。
- LNS-V 说：“让我们把这两位演员的整场戏都重拍一遍。”（要么太大，要么太小）。
- LNS-VT 说：“让我们只重拍这两位演员接下来的 10 秒钟的内容。”
它是如何工作的： LNS-VT 仍然会挑选相同数量的卡车（或演员），但它引入了一个新的控制旋钮：我们要重新优化多少个连续的步骤（或秒数）？
- 你可以告诉“魔法盒”：“重新排列这两辆卡车接下来 10 英里内的停靠点。”
- 或者说：“重新排列这两辆卡车接下来 40 英里内的停靠点。”
优势： 这使得研究人员能够精细地调整谜题碎片的大小。他们可以让碎片的大小恰到好处，既能让“魔法盒”完美解决，又不会违反规则。

研究发现

研究人员在两种不同类型的谜题上进行了测试：

车辆路径问题 (VRP)： 300 个停靠点，5 辆卡车。
二次多重背包问题 (QMKP)： 将 200 件物品装入 5 个袋子。

结果：

更好的解： 通过使用“精细切片”（LNS-VT），他们找到的解比旧的“大块头”方法（LNS-V）要好约 10%（更短的路线、更高的价值）。
速度： 与旧方法相比，他们在约 30% 的时间（迭代次数）内就达到了同样高质量的解。
“甜点区”（最佳大小）是变化的： 他们发现，谜题碎片的“完美”大小并不是固定的。
- 当解还很差时（过程初期），一个较大的碎片效果最好，因为可以做出大幅度的改进。
- 当解已经很好时（过程后期），一个较小的碎片效果最好，因为它能进行微小且精准的调整。
不同的谜题需要不同的尺寸： 卡车谜题的“甜点”尺寸与背包谜题的尺寸截然不同。这证明了你不能使用“一刀切”的方法；你必须能够灵活地调整大小。

结论

论文得出结论：仅仅保持规则（可行性）是不够的，要获得最佳结果，你还需要具备精确调节你要求“魔法盒”解决的问题规模的能力。

通过引入这个新的“连续步骤”参数，研究人员创造了一种让“魔法盒”工作效率更高的方法，能够为复杂的现实世界问题（如配送路线和装箱）更快地找到更好的解决方案。

技术摘要：具有可灵活调节子问题规模的 Ising 机辅助大邻域搜索

问题陈述
Ising 机作为启发式求解器，通过搜索 Ising 模型或二次无约束二进制优化（QUBO）模型的低能态来解决组合优化问题。然而，将它们直接应用于大规模约束问题（“朴素方法”）面临两个主要困难：

可扩展性： 在 QUBO 公式中，二进制变量的数量往往超过了当前 Ising 硬件的容量。
可行性： 约束通常作为惩罚项引入。因此，搜索空间包含了不可行解，且低能态并不一定对应于原始问题的高质量可行解。

虽然现有的方法（如变量固定或分而治之）试图减小问题规模，但它们往往难以在子问题规模与重建原始问题可行解的能力之间取得平衡。大邻域搜索（LNS）提供了一个框架，在该框架下，通过重新优化一个子问题（即“邻域”）来迭代改进一个可行当前解。虽然如果子问题生成方法设计得当，LNS 可以保持可行性，但基于 Ising 机的 LNS 性能对子问题规模高度敏感。如果子问题太小，每次迭代的潜在改进空间有限；如果太大，由于搜索空间扩大，Ising 机的解质量会下降。

方法论
本文重点研究两个问题：车辆路径问题（VRP）和二次多重背包问题（QMKP）。

现有方法 (LNS-V)： 对于 VRP，作者分析了一种之前的算法（LNS-V），该方法选择一组车辆并重新优化其完整路径。虽然这保持了可行性，但子问题规模仅由选定的车辆数量 ( $V'$ ) 控制。由于需要重新优化所选车辆的整个路径，变量数量随之变为 $(V')^2(T-2)^2$ （其中 $T$ 是总步数）。这导致了粒度过粗的问题；改变 $V'$ 的数值会导致变量数量发生剧烈跳变，使得难以将子问题规模调节到 Ising 机的最佳范围内。
提出的方法 (LTS-VT)： 为了解决粒度问题，作者提出了 LNS-VT。除了选择 $V'$ 辆车外，LNS-VT 还引入了一个新参数：每个选定车辆要重新优化的连续步数 ( $T'$ )。
- 机制： 对于每辆选定的车辆，提取一段连续的路径段（长度为 $T_{seg} = \min(T', \text{实际有效步数})$ ）。子问题在保持其余路径固定的情况下，重新优化这些特定路段内的站点分配和顺序。
- 可行性： 通过固定提取区间之外的站点，并确保提取的段仅涉及非仓库站点，该方法保证了将任何可行的子问题解重新插入后，都能得到原始 VRP 的可行解。
- 变量控制： LNS-VT 中的自由变量数量约为 $(V'T')^2$ 。这使得可以独立于总问题步数 $T$ ，实现对子问题规模的细粒度控制。
向 QMKP 的扩展： 作者将相同的设计原则应用于 QMKP。他们构建了一个子问题生成方法，该方法选择一部分背包 ( $K'$ ) 和一部分物品 ( $N'$ ) 进行重新优化。该方法通过固定不在选定集合中的物品，并针对选定背包的剩余容量调整容量约束，从而保持了可行性。

关键结果
数值实验使用 Fixstars Amplify AE Ising 机，针对一个 300 个站点、5 辆车的 VRP 和一个 200 个物品、5 个背包的 QMKP 进行了测试。

VRP 性能：
- LNS-VT 的表现优于朴素方法和现有的 LNS-V。
- 最佳的 LNS-VT 设置（具体为 $V'=2, T'=40$ ）在 100 次迭代后，相比 LNS-V 将目标函数值降低了约 10%。
- LNS-VT 仅用大约 30% 的迭代次数就达到了 LNS-V 的最终解质量。
- 变量敏感性： 研究发现，最优的子问题规模（以非仓库站点分配变量计）在 6,000 到 10,000 之间。现有的 LNS-V 在 $V' \ge 2$ 时无法达到这一范围（其最小值约为 14,400 个变量），这解释了其性能较差的原因。
- 动态需求： 合适的子问题规模在搜索过程中会发生变化。较大的子问题在早期迭代（目标函数值较大时）更有效；而较小的子问题在后期迭代（精炼高质量解时）更有效。
QMKP 性能：
- 应用于 QMKP 的 LNS 同样优于朴素方法。
- QMKP 的最优子问题规模明显较小，约为 100 到 150 个变量。
- 与 VRP（6,000–10,000）的显著差异表明，最优子问题规模取决于特定的问题类别和 QUBO 公式，而非仅仅取决于 Ising 机的能力。

意义与主张
本文声称，对于基于 Ising 机辅助的 LNS 而言，若要有效解决大规模约束问题，仅仅保持可行性是不够的。能够灵活调节子问题规模以匹配 Ising 机性能的“甜点区”（sweet spot），是一个至关重要的设计因素。

研究表明：

引入额外的控制参数（对于 VRP 是连续步数，对于 QMKP 是物品/背包数量）可以实现对子问题规模的细粒度调节，而仅通过改变选定实体数量的方法是无法实现的。
存在一个使解质量最大化的最优变量范围，且该范围在不同问题类（VRP vs. QMKP）之间存在显著差异。
最优子问题规模可能还取决于当前解的质量，这表明静态参数设置在整个搜索过程中可能并非最优。

作者总结道，尽管其结果针对特定的测试实例和机器设置，但“具备结构感知能力且可灵活调节的子问题生成”这一原则，是处理约束组合优化的一个有前景的方向。他们指出，未来的工作应侧重于开发能够根据搜索阶段和问题结构自动选择子问题参数的自适应策略。

大局观：用“魔法盒”解决不可能的谜题

旧策略：“大块头” (LNS-V)

新策略：“精细切片” (LNS-VT)

研究发现

结论

类似论文