Scaling Combinatorial Optimization Neural Improvement Heuristics with Online Search and Adaptation
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917867979538432 |
|---|---|
| author | Verdù, Federico Julian Camerota Castelli, Lorenzo Bortolussi, Luca |
| author_facet | Verdù, Federico Julian Camerota Castelli, Lorenzo Bortolussi, Luca |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_10163 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Scaling Combinatorial Optimization Neural Improvement Heuristics with Online Search and Adaptation Verdù, Federico Julian Camerota Castelli, Lorenzo Bortolussi, Luca Machine Learning Artificial Intelligence 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. |
| title | Scaling Combinatorial Optimization Neural Improvement Heuristics with Online Search and Adaptation |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2412.10163 |