Instance-Conditioned Adaptation for Large-scale Generalization of Neural Combinatorial Optimization
<|reference_start|>Instance-Conditioned Adaptation for Large-scale Generalization of Neural Combinatorial Optimization: The neural combinatorial optimization (NCO) approach has shown great potential for solving routing problems without the requirement of expert knowledge. However, existing constructive NCO methods cannot directly solve large-scale instances, which significantly limits their application prospects. To address these crucial shortcomings, this work proposes a novel Instance-Conditioned Adaptation Model (ICAM) for better large-scale generalization of neural combinatorial optimization. In particular, we design a powerful yet lightweight instance-conditioned adaptation module for the NCO model to generate better solutions for instances across different scales. In addition, we develop an efficient three-stage reinforcement learning-based training scheme that enables the model to learn cross-scale features without any labeled optimal solution. Experimental results show that our proposed method is capable of obtaining excellent results with a very fast inference time in solving Traveling Salesman Problems (TSPs) and Capacitated Vehicle Routing Problems (CVRPs) across different scales. To the best of our knowledge, our model achieves state-of-the-art performance among all RL-based constructive methods for TSP and CVRP with up to 1,000 nodes.<|reference_end|>
@article{zhou2024instance-conditioned,
    title={Instance-Conditioned Adaptation for Large-scale Generalization of Neural
  Combinatorial Optimization},
    author={Changliang Zhou, Xi Lin, Zhenkun Wang, Xialiang Tong, Mingxuan Yuan,
  Qingfu Zhang},
    journal={arXiv preprint arXiv:2405.01906},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.01906},
    primaryClass={cs.AI cs.LG}
}