Adaptive Heuristic Selection in Large Neighbourhood Search : A Multi-Armed Bandit Approach

Sammanfattning

Large neighbourhood search is a method for solving combinatorial optimisation problems which relies on a selection heuristic to guide its search. While generic selection heuristics applicable to any problem exist, no single heuristic performs best across all problems. This thesis investigates whether framing the choice of selection heuristic as a multi-armed bandit problem can improve solver performance, and if so, which bandit strategy is most effective. Eleven bandit strategies are implemented and evaluated against a round-robin baseline across a suite of benchmark problems. A Friedman test finds that the strategies do not all perform equally, but post-hoc testing cannot identify any individual strategy as significantly better or worse than the others. A structural issue with UCB-based strategies in parallel solver settings is identified and connected to the delayed feedback bandit literature.