Neuro-PLS: A Generalizable Local Search Framework for Multi-objective Combinatorial Optimization

In this paper, we present a novel neural multi-objective combinatorial optimization framework with generalization ability across problems. The main idea is to integrate the framework of Pareto Local Search (PLS), a well-known problem independent multi-objective heuristic, with the concept of learning-to-optimize (L2O). In the proposed framework, namely Neuro-PLS, the backbone of PLS is guided by two neural networks to utilize cross-problem knowledge. Specifically, in Neuro-PLS, the solution-selection component is guided by a Graph Neural Network (GNN) and the neighborhood-exploration component is guided by a multi-layer perception. In the experimental studies, the training set of Neuro-PLS contains only one 200-dimensional multi-objective unconstrained binary quadratic programming (mUBQP) instance. The trained Neuro-PLS shows remarkable efficiency on optimizing large-size mUBQP instances and middle-size multi-objective traveling salesman problem (mTSP) instances with different number of objectives. Extensive experiments on a variety of mUBQP and mTSP instances show that the trained Neuro-PLS significantly outperforms some recently proposed reinforcement learning-based methods.