Learning with Local Search MCMC Layers

Abstract: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.

Machine Learning (cs.LG)

arXiv:2505.14240 [cs.LG]

(or arXiv:2505.14240v3 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2505.14240 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.