SUPL2I: Standalone Learning to Improve for Multi-Objective Combinatorial Optimisation

Neural methods have shown strong performance on single-objective combinatorial optimisation problems (SOCOPs), through both learning to construct solutions from scratch (L2C) and learning to improve complete solutions with local moves (L2I). However, existing neural methods for multi-objective combinatorial optimisation problems (MOCOPs) are predominantly based on the L2C paradigm. The few existing L2I methods for MOCOPs are integrated into external search frameworks (e.g., an MOEA or local search). When designing a standalone L2I method for MOCOPs, there are several issues worth exploring: 1) different objectives may relate to different features (e.g., node coordinates or costs in multi-objective TSP), so a single representation of all these features may not reflect the effect of local moves on each objective separately; 2) unlike L2C, L2I additionally needs to consider node positions, so where to inject the preference is non-trivial; 3) in SOCOPs, a local move typically makes a solution either better or worse, whereas in MOCOPs, a local move can lead to an incomparable solution (i.e., one that is nondominated to the original solution). In this paper, we look at these three issues and propose a standalone preference-conditioned L2I method unified across problem sizes. Specifically, the proposed method 1) builds one representation per objective from its related node features, with a shared encoder, and scores local moves under each objective separately; 2) keeps node positions preference-free while injecting the preference into both the node embeddings and the fusion of the per-objective scores; and 3) considers the nondominance relation (i.e., only accepting superior and incomparable solutions) in training and inference. Moreover, we introduce a positional encoding that captures the cyclic and hierarchical structure of routing solutions and transfers across problem sizes. Experiments show that our method substantially outperforms state-of-the-art neural and conventional methods in both in-distribution and cross-size generalisation settings. Notably, in the in-distribution setting, it even outperforms the strong classical solver LKH with weighted-sum scalarisation while requiring less time.