On Distributional Dependent Performance of Classical and Neural Routing Solvers
This addresses the problem of improving neural routing solvers for combinatorial optimization, but it is incremental as it focuses on distributional adjustments rather than a breakthrough method.
The paper tackles the challenge of neural combinatorial optimization methods underperforming compared to specialized meta-heuristics by proposing a novel approach to structure the distribution of training instances for routing problems. The result shows that the performance gap between neural solvers and meta-heuristics decreases when learning from sub-samples drawn from a fixed base distribution.
Neural Combinatorial Optimization aims to learn to solve a class of combinatorial problems through data-driven methods and notably through employing neural networks by learning the underlying distribution of problem instances. While, so far neural methods struggle to outperform highly engineered problem specific meta-heuristics, this work explores a novel approach to formulate the distribution of problem instances to learn from and, more importantly, plant a structure in the sampled problem instances. In application to routing problems, we generate large problem instances that represent custom base problem instance distributions from which training instances are sampled. The test instances to evaluate the methods on the routing task consist of unseen problems sampled from the underlying large problem instance. We evaluate representative NCO methods and specialized Operation Research meta heuristics on this novel task and demonstrate that the performance gap between neural routing solvers and highly specialized meta-heuristics decreases when learning from sub-samples drawn from a fixed base node distribution.