💻 computer science

Residual-Guided Simulated Annealing for Multi-Dimensional Subset Sum

本文介绍了残差引导模拟退火算法（Residual-Guided Simulated Annealing, RGSA），这是一种新型的保持基数启发式算法，它能够针对 $m \ge 12$ 的 QOBLIB 实例，在多维子集和问题上稳定生成低残差、近可行解，其性能优于盲目模拟退火和 QUBO 采样器，并在精确求解器仍难以实现的场景下提供了一个可复现的经典基准。

原作者： Sreekuttan L S

发布于 2026-10-01

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Sreekuttan L S

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

在计算机科学领域，存在着一类被称为“子集和问题”（subset sum problem）的谜题。想象你拥有大量具有特定重量的物品，任务是找到一组物品，使其总重量恰好等于一个特定的目标数值。当只有一个目标时，这项任务看起来很简单；但当你必须同时满足多个不同的目标时，难度就会呈爆炸式增长。这个更难的版本被称为“多维子集和问题”，在研究界被称为“市场分割”（Market Split）问题。它要求计算机将一组物品分为两组，使得每一组的总重量在多个类别上同时匹配一组特定的目标。这些谜题不仅仅是学术练习；它们代表了优化领域的一个基本挑战，测试着计算机在复杂可能性景观中寻找完美契合点的极限能力。几十年来，研究人员一直致力于解决这些问题，因为可能组合的数量增长得太快，以至于即使是最强大的超级计算机也会迷失方向，无法在数十亿次错误的尝试中找到那唯一的完美解。

来自印度 Bloq Quantum 的研究人员 Sreekuttan L. S. 最近通过一种全新的方法应对了这一挑战，该方法的设计初衷并非寻找完美答案，而是在完美答案无法触及时，寻找极其接近它的解。该研究专注于一套来自标准库的特定难题，该库常用于测试优化方法。研究人员并没有试图通过检查每一种可能性来解决问题（这在处理大规模集合时是不可能的），而是开发了一种名为“残差引导模拟退火”（Residual-Guided Simulated Annealing）的方法。为了理解其运作方式，请想象你正在尝试平衡一个带有几种不同砝码的天平。如果天平向一侧倾斜，你确切地知道缺少了多少重量。这种方法利用那个“缺失量”或“误差”来引导下一步行动。当计算机决定将其当前组中的一个物品与另一个物品进行交换时，它并不是随机选择。相反，它会精确计算出新物品需要是什么才能抵消误差，然后寻找最接近该理想替代品的可用物品。这是一种智能的、有方向性的搜索，它会根据距离目标的差距不断修正自己的航向。

研究人员将这种新方法与旧有的、更具随机性的方法以及其他几种强大的计算机程序进行了对比测试。实验在八个不同版本的“市场分割”谜题上运行，范围从较小的、易于处理的规模到被认为极其困难的旗舰版本。在第一轮测试中，新方法与一种在不做误差引导的情况下进行随机交换的版本进行了对决。结果显示，引导式方法具有明显的优势。在难度最高的测试案例中，随机方法留下的平均误差约为 104 个单位，而新的引导方法将该误差降低到了约 100 个单位。虽然这个差异看起来很小，但在这些谜题的语境下，它代表了在寻找更接近完美解方面的显著进步。研究还测试了一个包含此引导方法及其他几个辅助步骤的完整流水线，这使得平均误差进一步降至约 100.37 个单位。至关重要的是，在初始阶段的所有运行中都没有找到完美解，但引导方法始终能产生比随机尝试更接近目标的解。

为了观察这种方法在更广泛的竞争中表现如何，研究人员扩大了研究范围，纳入了更广泛的时间限制，并将新方法与包括一些旨在寻找精确解的求解器在内的六种其他成熟求解器进行了比较。测试在 25 秒的严格时间限制内进行。在这场竞赛中，新的引导方法证明了其高度的可靠性。当其他几种强大的求解器在时限内未能返回任何可用答案时，引导方法始终能产生结果。当时间限制延长至 300 秒时，引导方法继续改进，达到了 36.54 个单位的中位数误差。相比之下，一种基于不同类型随机搜索的方法产生的误差为 263.46 个单位，而另一种流行的遗传算法则稳定在 72.27 个单位。尽管引导方法并未声称找到了完美的精确解，但它能够找到比竞争对手更接近目标的解。

该研究在“寻找完美解”和“寻找非常好的解”之间做了明确的区分。研究人员明确指出，这种方法并不能证明一个完美解是否存在或不存在；它只是寻找一个非常接近完美的解。在这些谜题的世界里，“完美”解意味着数值完全匹配，而“近可行”解意味着它们非常接近。这种新方法非常擅长快速找到这些近乎完美的解。它的作用是作为一个强大的工具，引导计算机到达一个非常接近答案的点，这可以作为其他最终可能找到精确解的方法的起点。研究强调，对于这些最困难版本的谜题，精确求解器往往会耗尽时间或内存，而这种引导方法提供了一种在几秒钟内非常接近目标的可行途径。

研究结果表明，利用计算中的误差来引导搜索是一种非常有效的策略。通过观察缺失的部分并寻找最能填补该缺口的物品，计算机避免了旧有随机方法所具有的漫无目的的徘徊。这种方法并不取代在需要完美答案时对精确求解器的需求，但它为处理精确方法难以应对的最难情况提供了一种稳健且透明的方式。研究结论认为，对于这类特定的困难谜题，引导方法始终能产生经过验证且可复现的低误差结果。它为解决这些问题提供了一个新的基准，表明即使在完美解无法触及的情况下，一种智能的、受引导的搜索也能非常接近目标，为从事复杂优化挑战的研究人员和工程师提供了一个有价值的工具。

技术摘要：用于多维子集和问题的残差引导模拟退火算法

问题定义
本文研究的是多维子集和问题，也称为市场分割（Market Split）问题。形式上，给定一个属性向量矩阵 $A \in \mathbb{Z}_{\ge 0}^{m \times N}$ 和一个目标向量 $b \in \mathbb{Z}_{\ge 0}^m$ ，目标是找到一个二进制向量 $x \in \{0, 1\}^N$ ，使得 $Ax = b$ 。即使在 $m=1$ 时，该问题也是 NP 完全的。评估所使用的特定实例来自量子优化基准库（QOBLIB），其特点是具有“刻意设计的微小且困难”的系统，旨在暴露通用整数规划算法的弱点。这些实例的特征是具有稠密的正系数和等式目标，这使得局部看似合理但全局不一致的选择几乎没有容错空间。本研究侧重于固定基数切片，即选定项目的数量为 $q \approx N/2$ 。

方法论：残差引导模拟退火（RGSA）
核心贡献是残差引导模拟退火（RGSA），这是一种保持基数的局部搜索启发式算法。不同于通常依赖盲目随机交换的标准模拟退火（SA），RGSA 利用当前的残差向量 $\Delta = Ax - b$ 来引导搜索。

几何交换提议： 当从当前集合 $S$ 中移除一个项目 $i$ 时，该方法会计算一个“理想补偿器”向量 $w^* = w_i - \Delta$ 。随后，它在未选集合 $\bar{S}$ 中搜索在 $m$ 维属性空间中与 $w^*$ 在几何上最接近的向量 $w_j$ 。
混合领域： 算法通过概率 $p_g$ （实验中设为 0.65）将这种引导式提议与概率为 $1-p_g$ 的均匀随机交换相结合。这确保了即使当理想补偿器位于观测点云之外时，也能探索解空间。
接受规则： 该方法使用基于欧几里得残差范数 $R(x) = \|Ax - b\|_2$ （而非其平方）的 Metropolis 接受准则，使温度量级具有可解释性。
辅助组件：
- 拉格朗日热启动： 一个可选的初始化步骤，利用拉格朗日对偶投影在退火开始前生成一个可行的基数划分。
- 确定性精化： 一个后处理阶段，涉及详尽的一对一和二对二交换，以在考察的领域内达到局部最优。
- 完整流水线： 将拉格朗日热启动、RGSA 和确定性精化结合在一起的过程被称为“完整 RGSA 流水线”。

实验设置
本研究在 8 个 QOBLIB 市场分割实例上评估了 RGSA，其维度 $m \in \{9, \dots, 15\}$ 且系数范围 $D \in \{50, 200\}$ 。评估分为三个阶段：

受控基准测试： 160 次运行（8 个实例 $\times$ 4 种配置 $\times$ 5 个种子），将 RGSA 变体与“盲目 SA（Blind SA）”基准进行比较。
25 秒预算： 在严格的 25 秒墙钟限制下，对 8 种方法（RGSA 变体、盲目 SA 以及包括 SCIP、CP-SAT、pymoo GA 和 QUBO 采样器在内的 6 种外部求解器）进行 1,554 次运行的比较。
300 秒预算： 一个较长时间的实验，带有中间检查点（25, 60, 120, 300 秒），用于分析收敛性和可用性。

关键结果

残差降低： 与盲目 SA 相比，RGSA 始终能降低欧几里得残差。在旗舰实例 $(m=15, D=200)$ 上，完整 RGSA 流水线实现的平均残差为 100.37，而仅用 RGSA 为 104.06，盲目 SA 的值则显著更高。
与外部求解器的比较：
- 精确求解器： 精确求解器（SCIP、CP-SAT）和线性规划代理（HiGHS）在 25 秒和 300 秒的预算内均未能返回任何可行向量，导致在 25 秒窗口内的有效现任者（incumbents）可用性为 0%。
- 启发式算法： 在 300 秒时，完整 RGSA 流水线实现了最低的中位数残差 36.54，优于 Champion 配置（仅进行引导式 SA 而非完整精化的 RGSA）的 38.00，以及盲目 SA 的 42.25。Champion 配置提供了一个稳定的随时可用（anytime）轨迹，而完整流水线达到了略低的终点残差。
- QUBO 采样器： 标准的 QUBO 模拟退火采样器（Neal）表现较差，中位数残差为 263.46，凸显了 RGSA 特有的残差引导几何结构的优势。
可行性： 在测试的实例中，没有任何配置在给定的时间预算内实现了精确可行性（ $Ax=b$ ）。研究明确指出，在主要基准测试的 160 次运行中，发现精确解的次数为 0。

意义与主张
论文将 RGSA 定位为精确求解器的替代品，而是作为一种透明的经典基准以及候选现任者生成器，用于混合搜索方法。

首次受控研究： 据作者所知，这是第一个针对 $m \ge 12$ 的 QOBLIB 市场分割类进行的受控、多种子启发式缩放研究。
方法论贡献： 它引入了一种特定的、保持基数的几何交换启发式算法，该算法利用残差方程本身来定义最近向量提议，这与以往基于惩罚或单变量跳跃的方法不同。
实际效用： 在 $m=15$ 的前沿领域，RGSA 能在数秒内产生低残差、近乎可行的分配，而此时精确求解器目前难以处理。这些结果提供了“可重复的经典基准”以及精确或混合搜索的起点，而非证明不可行性。
谦逊态度： 作者强调结果是描述性的。非零残差并不意味着不可行，且研究并未声称对其他方法具有普遍统治地位。其主要价值在于对残差质量、可用性和运行时间的严谨报告。

类似论文