将神经约束求解器改造为大邻域搜索,显著提升求解性能。
Large Neighborhood Search meets Iterative Neural Constraint Heuristics
- 把神经求解器拆解为破坏-修复两阶段,借鉴经典搜索思想
- 随机破坏优于贪心破坏,贪心修复比采样修复更有效
- 在数独、图着色等任务中超越原模型和传统方法
神经网络正被越来越多地用作约束满足问题的启发式算法。这些神经方法通常是循环的,通过迭代优化候选赋值来改进解。本文明确建立了此类迭代神经启发式与大邻域搜索(LNS)之间的联系,并将现有神经约束求解方法ConsFormer改造为LNS流程。我们将所得神经LNS分解为两个标准组件:破坏与修复操作。在破坏阶段,我们实现了多种经典启发式,并引入基于模型内部得分预测的新颖引导式算子以选择邻域;在修复阶段,采用ConsFormer作为神经修复算子,并比较了原始基于采样的解码器与选择最可能赋值的贪心解码器。在数独、图着色和MaxCut任务上的实验表明,将神经启发式转化为LNS流程能带来显著性能提升,且在求解质量上超越其原始设置以及经典和神经基线方法。我们还观察到跨任务的一致设计模式:随机破坏优于贪心破坏,而贪心修复在寻找单一高质量可行解时比采样修复更有效。这些发现凸显了LNS作为结构化和改进迭代神经方法的有用视角与设计框架。
原文摘要 · Abstract (English)
Neural networks are being increasingly used as heuristics for constraint satisfaction. These neural methods are often recurrent, learning to iteratively refine candidate assignments. In this work, we make explicit the connection between such iterative neural heuristics and Large Neighborhood Search (LNS), and adapt an existing neural constraint satisfaction method-ConsFormer-into an LNS procedure. We decompose the resulting neural LNS into two standard components: the destroy and repair operators. On the destroy side, we instantiate several classical heuristics and introduce novel prediction-guided operators that exploit the model's internal scores to select neighborhoods. On the repair side, we utilize ConsFormer as a neural repair operator and compare the original sampling-based decoder to a greedy decoder that selects the most likely assignments. Through an empirical study on Sudoku, Graph Coloring, and MaxCut, we find that adapting the neural heuristic to an LNS procedure yields substantial gains over its vanilla settings and improves its competitiveness with classical and neural baselines. We further observe consistent design patterns across tasks: stochastic destroy operators outperform greedy ones, while greedy repair is more effective than sampling-based repair for finding a single high-quality feasible assignment. These findings highlight LNS as a useful lens and design framework for structuring and improving iterative neural approaches.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。