将启发式搜索转化为可微采样器，让神经网络直接学习组合优化。
Regularized Large Neighborhood Search
- 用正则化扰动局部子问题，把LNS变成可微的马尔可夫链采样器。
- 在熵正则下实现精确的块吉布斯采样，无需全局求解器。
- 可调节迭代次数，灵活平衡伪似然与最大似然估计，适合端到端训练。
运筹学从业者通常使用大规模邻域搜索（LNS）这一可扩展的启发式方法，通过局部重优化变量子集来迭代改进当前解。然而，现有将组合优化层集成到神经网络的方法大多依赖于精确的全局解，这在计算上不可行。本文提出正则化大规模邻域搜索（RLNS），通过正则化或扰动局部子问题，将LNS启发式转化为对可行解组合集的高效MCMC采样器，并伴随Fenchel-Young损失。在熵正则下，我们证明RLNS实现了精确的块吉布斯采样。此外，调整RLNS迭代次数可实现伪似然与精确最大似然估计之间的插值，从而实现无需全局求解器的端到端学习。我们在k-子集选择、广义分配和随机车辆调度问题上验证了该方法的有效性。
原文摘要 · Abstract (English)
Operations research practitioners typically tackle NP-hard combinatorial problems using large neighborhood search (LNS), a scalable heuristic that iteratively refines a current solution by locally re-optimizing subsets of its variables. In contrast, most existing approaches for integrating combinatorial optimization layers into neural networks still assume access to an exact global solution, which is computationally intractable. We bridge this gap by introducing regularized LNS (RLNS). By regularizing or perturbing local subproblems, we turn the LNS heuristic into an efficient MCMC sampler over the combinatorial set of feasible solutions, with associated Fenchel-Young losses. Under entropic regularization, we prove that RLNS performs exact block Gibbs sampling. Furthermore, adjusting the number of RLNS iterations allows us to interpolate between pseudolikelihood and exact maximum likelihood estimation, for end-to-end learning without global solvers. We demonstrate our approach on $k$-subset selection, generalized assignment, and stochastic vehicle scheduling problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。