Scaling Combinatorial Optimization Neural Improvement Heuristics with Online Search and Adaptation
We introduce Limited Rollout Beam Search (LRBS), a beam search strategy for deep reinforcement learning (DRL) based combinatorial optimization improvement heuristics. Utilizing pre-trained models on the Euclidean Traveling Salesperson Problem, LRBS significantly enhances both in-distribution performance and generalization to larger problem instances, achieving optimality gaps that outperform existing improvement heuristics and narrowing the gap with state-of-the-art constructive methods. We also extend our analysis to two pickup and delivery TSP variants to validate our results. Finally, we employ our search strategy for offline and online adaptation of the pre-trained improvement policy, leading to improved search performance and surpassing recent adaptive methods for constructive heuristics.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationDeep Reinforcement LearningSimilar Papers 제목 키워드 기반
Estimation of the yield curve for Costa Rica using combinatorial optimization metaheuristics applied to nonlinear regression
The term structure of interest rates or yield curve is a function relating the interest rate with its own term. Nonlinear regression models of Nelson-Siegel and Svensson were used to estimate the yield curve using a samp…
Combinatorial OptimizationregressionLearning to Perform Local Rewriting for Combinatorial Optimization
Search-based methods for hard combinatorial optimization are often guided by heuristics. Tuning heuristics in various conditions and situations is often time-consuming. In this paper, we propose NeuRewriter that learns a…
Combinatorial OptimizationReinforcement LearningReinforcement Learning (RL)SchedulingReinforcement Learning for Combinatorial Optimization: A Survey
Many traditional algorithms for solving combinatorial optimization problems involve using hand-crafted heuristics that sequentially construct a solution. Such heuristics are designed by domain experts and may often be su…
Combinatorial OptimizationDecision Makingreinforcement-learningReinforcement Learning+2ML-Guided Primal Heuristics for Mixed Binary Quadratic Programs
Mixed Binary Quadratic Programs (MBQPs) are an important and complex set of problems in combinatorial optimization. As solving large-scale combinatorial optimization problems is challenging, primal heuristics have been d…
Leveraging Large Language Models to Develop Heuristics for Emerging Optimization Problems
Combinatorial optimization problems often rely on heuristic algorithms to generate efficient solutions. However, the manual design of heuristics is resource-intensive and constrained by the designer's expertise. Recent a…
Combinatorial OptimizationIn-Context LearningTraveling Salesman Problem