Abstract
Single-stage neural combinatorial optimization solvers have achievednear-optimal results on various small-scale combinatorial optimization (CO)problems without needing expert knowledge. However, these solvers exhibitsignificant performance degradation when applied to large-scale CO problems.Recently, two-stage neural methods with divide-and-conquer strategies haveshown efficiency in addressing large-scale CO problems. Nevertheless, theperformance of these methods highly relies on problem-specific heuristics ineither the divide or the conquer procedure, which limits their applicability togeneral CO problems. Moreover, these methods employ separate training schemesand ignore the interdependencies between the dividing and conqueringstrategies, which often leads to sub-optimal solutions. To tackle thesedrawbacks, this article develops a unified neural divide-and-conquer framework(i.e., UDC) for solving general large-scale CO problems. UDC offers aDivide-Conquer-Reunion (DCR) training method to eliminate the negative impactof a sub-optimal dividing policy. Employing a high-efficiency Graph NeuralNetwork (GNN) for global instance dividing and a fixed-length sub-path solverfor conquering divided sub-problems, the proposed UDC framework demonstratesextensive applicability, achieving superior performance in 10 representativelarge-scale CO problems. The code is available athttps://github.com/CIAM-Group/NCO_code/tree/main/single_objective/UDC-Large-scale-CO-master.