用随机搜索方法让神经网络高效学习组合优化问题。
Learning with Local Search MCMC Layers
- 将局部搜索转化为马尔可夫链蒙特卡洛采样，构建可微分的优化层。
- 在车辆路径、子集选择等任务中，计算量大幅降低且性能稳定。
- 适合需要快速求解复杂优化问题的研究者或工程师使用。
将组合优化层融入神经网络是当前研究热点，但现有方法常缺乏理论保证，或依赖不精确求解器时表现不佳。由于许多运筹学问题为NP难，通常需采用基于邻域的局部搜索启发式方法。本文受模拟退火与Metropolis-Hastings的关联启发，将局部搜索中的邻域系统转化为提议分布，在可行解集合上实现马尔可夫链蒙特卡洛采样，从而构建可微分的随机组合层及其损失函数。相比精确求解器，使用局部搜索显著降低学习计算负担。我们在带时间窗的动态车辆路径问题、二值向量与k-子集预测任务，以及多维背包决策导向学习问题上验证了该方法的有效性。
原文摘要 · Abstract (English)
Integrating combinatorial optimization layers into neural networks has recently attracted significant research interest. However, many existing approaches lack theoretical guarantees or fail to perform adequately when relying on inexact solvers. This is a critical limitation, as many operations research problems are NP-hard, often necessitating the use of neighborhood-based local search heuristics. In this paper, we introduce a principled approach for learning with such inexact solvers. Inspired by the connection between simulated annealing and Metropolis-Hastings, we transform the problem specific neighborhood systems used in local search heuristics into proposal distributions, implementing MCMC on the set of feasible solutions. This allows us to construct differentiable, stochastic combinatorial layers and associated loss functions. Replacing an exact solver with a local search strongly reduces the computational burden of learning on many applications. We demonstrate our approach on a dynamic vehicle routing problem with time windows, binary vector and k-subset prediction tasks, as well as a multi-dimensional knapsack decision-focused learning problem.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。