用采样增强的神经搜索法，解决整数规划求解中的局部最优陷阱。
SPL-LNS: Sampling-Enhanced Large Neighborhood Search for Solving Integer Linear Programs
- 引入采样机制，让搜索跳出局部最优
- 自生成数据训练，提升长期采样效率
- 在多种规模问题上优于现有神经求解器
大型邻域搜索（LNS）是组合优化中常用的启发式方法，通过迭代探索当前解的大邻域寻找更优解。近年来，基于神经网络的LNS求解器通过学习贪婪预测下一邻域的局部最优解，在求解整数线性规划（ILP）问题上取得显著进展。然而，这种贪婪策略引发两大问题：(1) 贪婪提案在多大程度上陷入局部最优？(2) 如何在长期内有效提升采样效率？为此，本文首次将LNS建模为随机过程，提出SPL-LNS——一种基于采样的神经LNS求解器，利用局部信息引导的提案策略以逃离局部最优。同时，设计了一种新颖的回溯重标注方法，高效训练SPL-LNS于自生成数据。实验表明，SPL-LNS在不同规模的各类ILP问题上均显著超越先前神经LNS求解器。
原文摘要 · Abstract (English)
Large Neighborhood Search (LNS) is a common heuristic in combinatorial optimization that iteratively searches over a large neighborhood of the current solution for a better one. Recently, neural network-based LNS solvers have achieved great success in solving Integer Linear Programs (ILPs) by learning to greedily predict the locally optimal solution for the next neighborhood proposal. However, this greedy approach raises two key concerns: (1) to what extent this greedy proposal suffers from local optima, and (2) how can we effectively improve its sample efficiency in the long run. To address these questions, this paper first formulates LNS as a stochastic process, and then introduces SPL-LNS, a sampling-enhanced neural LNS solver that leverages locally-informed proposals to escape local optima. We also develop a novel hindsight relabeling method to efficiently train SPL-LNS on self-generated data. Experimental results demonstrate that SPL-LNS substantially surpasses prior neural LNS solvers for various ILP problems of different sizes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。