Scaling Combinatorial Optimization Neural Improvement Heuristics with Online Search and Adaptation

This dissertation investigates the application of reinforcement learning (RL) to combinatorial optimization (CO), focusing on three key problem domains: the Travelling Salesman Problem (TSP), Pickup and Delivery Problems (PDP), and phylogenetic tree inference in the Balanced Minimum Evolution Problem (BMEP). The primary objective is to enhance the generalization capabilities of RL-based improvement heuristics for solving complex combinatorial tasks. By leveraging deep reinforcement learning (DRL) within local search heuristics, we develop strategies for effectively selecting moves such as subtree pruning and regrafting (SPR) in phylogenetics and also employ pre-trained models for other approaches in vehicle routing. A major contribution of this work is the introduction of Limited Rollout Beam Search (LRBS), a method designed to extend the applicability of pre-trained DRL policies to problem instances that significantly exceed the scales encountered during training. LRBS integrates online search with efficient adaptation to boost generalization, making it a powerful tool for solving larger and more diverse problem sets. The framework’s flexibility is demonstrated through its application across different CO problems and varying policies. LRBS exhibits strong performance on TSP benchmarks, outperforming improvement-based baselines and reducing the optimality gap compared with constructive heuristics, especially on smaller instances. For larger instances, LRBS remains competitive, though constructive methods continue to outperform. Our results show that improvement heuristics, such as those driven by RL, can scale more efficiently than constructive methods, highlighting their potential for future advancements. In the context of PDPs, while the RL-based approach struggles with generalization, LRBS significantly reduces the gap, underscoring its utility even in challenging scenarios. In the BMEP, applying RL and LRBS demonstrates considerable potential, particularly when addressing larger datasets and varying substitution models. Our experiments reveal that the integration of LRBS with online adaptation leads to state-of-the-art performance on small to medium phylogenetic inference problems, while further developments could unlock broader generalization for more complex cases.

Questa tesi studia l'applicazione del reinforcement learning (RL), anche detto apprendimento per rinforzo, per i problemi di ottimizazione combinatoria (CO), concentrandosi su tre problemi chiave: il problema del commesso viaggiatore (TSP), problemi di ritiro e consegna (PDP) e inferenza filogenetica nel Balanced Minimum Evlution Problem (BMEP). L’obiettivo primario è migliorare le capacità di generalizzazione delle euristiche che migliorano soluzioni e basate su RL per risolvere problemi di CO. Sfruttando il deep reinforcement learning (DRL) ed euristiche di ricerca locale, in questo lavoro sviluppiamo strategie per selezionare efficacemente azioni come Subtree Pruning and Regrafting (SPR) in filogenetica ed impieghiamo anche modelli pre-addestrati per altri approcci nei problemi del TSP e PDP. Un contributo importante di questo lavoro è Limited Rollout Beam Search (LRBS), un metodo progettato per estendere l'applicabilità delle policy DRL pre-addestrate a istanze che che superano significativamente le scale incontrate durante l'apprendimento del modello. LRBS integra la ricerca online con un adattamento efficiente del modello per aumentare la generalizzazione, rendendola un potente strumento per risolvere problemi più grandi e diversificati. La flessibilità del nostro approccio è dimostrato attraverso la sua applicazione a diversi problemi di CO e a diverse policy. LRBS mostra ottime prestazioni sui benchmark TSP, superando i metodi di riferimento e riducendo il divario di ottimalità rispetto alle euristiche costruttive, soprattutto su istanze più piccole. Per i casi più grandi, tuttavia, LRBS rimane competitivo ma i metodi costruttivi continuano a sovraperformare. I nostri risultati mostrano che le euristiche basate sul miglioramento di soluzioni possono scalare in modo più efficiente rispetto ai metodi costruttivi, evidenziandone il potenziale per futuri avanzamenti. Nel contesto dei PDP, mentre la policy allenata con RL fatica a generalizzare, LRBS riduce significativamente il divario con il metodo di riferimento, sottolineandone l'utilità anche in scenari difficili. Nel BMEP, l'applicazione di RL e LRBS dimostra un notevole potenziale, in particolare quando si affrontano set di dati più grandi e diversi modelli di sostituzione. I nostri esperimenti rivaling che l'integrazione di LRBS con l'adattamento online porta a prestazioni analoghe ai metodi che rappresentano lo stato dell'arte su problemi di inferenza filogenetica di piccole e medie dimensioni, mentre ulteriori sviluppi potrebbero portare ad una generalizzazione più efficiente per casi più complessi.