按需生成困难实例：用 Nevergrad 优化器搜索 NP-hard 问题的最难算例

查看 PDF HTML（实验性）

摘要：算法实验研究的结论好坏取决于所运行的实例。针对已被充分研究的问题，基准库花费了数十年才整理完成；而对新问题的评估往往退回到随机实例，而众所周知随机实例具有误导性：它们可能更多地反映了随机生成器的特性，而非所研究的算法问题本身。
我们将实例生成视为一个优化问题：参数化实例空间，以求解器的运行时间作为目标，让黑盒优化器搜索困难实例。我们基于 Nevergrad 优化平台开发了一套适用广泛的工作流程，并在四个 NP 难问题上进行了演示：可满足性、旅行商、哈密顿回路和非置换流水车间调度。该搜索只需要求解器、实例编码器和计算预算。在所有四个案例研究中，我们演化出的实例都击败了预算匹配的随机抽取中最难的实例，其中三个案例中领先一个数量级或更多。它们通常可与长期整理的基准集相媲美：我们的 SAT 冠军（对于三求解器组合）比其规模类别中 498 个 SAT 竞赛公式中的 78% 更难；我们的 20 城市 TSP 冠军所需时间比测得的最难经典 TSPLIB 实例（229 个城市）长数倍；我们的流水车间冠军需要 CP Optimizer 238.6 秒才能求解到证明最优（而 100,000 次随机抽取中最难的仅需 4.5 秒），同时使 CP-SAT 无法给出最优性证明。优化器甚至仅凭运行时间就能恢复已知结构：它定位到相变附近的 SAT 子句/变量比，并为两个调度引擎找到结构不同的冠军。

评论：	被 ALENEX 2027 接收的论文完整版
主题：	数据结构与算法（cs.DS）；人工智能（cs.AI）；优化与控制（math.OC）
引用为：	arXiv:2610.22637 [cs.DS]
	（或本版本使用 arXiv:2610.22637v1 [cs.DS]）
	https://doi.org/10.48550/arXiv.2610.22637 由 DataCite 颁发的 arXiv DOI（待注册）

提交历史

来自：Martin Koutecký [查看电子邮件]
[v1] 2026年10月15日星期四 20:47:46 UTC（47 KB）