Reproduce “Learning to Control Local Search for Combinatorial Optimization” on OpenResearch

About this paper

Jonas K. Falkner, Daniela Thyssens, Ahmad Bdeir, Lars Schmidt-Thieme

The Intelligent Systems and Machine Learning Laboratory at the University of Hildesheim introduced NeuroLS, a Graph Neural Network (GNN)-based controller that learns to manage local search meta-heuristics for combinatorial optimization. This system consistently outperformed traditional meta-heuristics and several state-of-the-art machine learning approaches on Job Shop Scheduling and Capacitated Vehicle Routing Problems.

Key insights

• Formalizing local search control as an MDP with explicit intervention points provides a structured and learnable framework for meta-heuristic design, moving beyond manual tuning.
• Graph Neural Networks effectively capture both static invariant problem structures and dynamic solution-specific information, offering robust state representations for an RL agent.
• The capability to learn and select appropriate neighborhood operators and perturbation strategies dynamically during search leads to superior performance, especially for larger and more complex problem instances.

Summary by alphaXiv.