Research map / Learning theory and algorithms / Combinatorial and search optimization
UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization Problems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes UDC, a unified neural divide-and-conquer framework trained end-to-end with a Divide-Conquer-Reunion (DCR) RL procedure, using a GNN dividing policy and constructive conquering solvers, applied to 10 large-scale CO problems.
Problem
Existing neural divide-and-conquer solvers for large-scale combinatorial optimization rely on problem-specific heuristics and train dividing and conquering policies separately, leading to sub-optimal solutions and limited generality.
Approach
Train the GNN dividing policy and the constructive conquering policy jointly with REINFORCE, and add a Reunion step that re-conquers the boundary between adjacent sub-problems so the dividing reward reflects errors introduced by sub-optimal divisions.
Key results
- UDC-x250 (alpha=50) reaches 2.49% gap on TSP2000 and 1.78% on TSP1000 vs. ICAM 1.58% on TSP1000 (best learning baseline on smaller sets).
- On CVRP1000 UDC-x250 achieves 43.00 objective, the best among listed methods including LKH3 (46.40 at 14m).
- On PCTSP500/1000/2000, UDC-x250 (alpha=1) gives the best objective values among all compared methods, e.g., 25.04 on PCTSP2000 vs GLOP 27.25.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use POMO instead of ICAM as the conquering policy (ablation) | UDC · TSP500 | optimality gap: 2.54% vs 2.64% (x2); 1.58% vs 1.64% (x50) | No clear effect |
| use POMO instead of ICAM as the conquering policy (ablation) | UDC · TSP1,000 | optimality gap: 2.92% vs 3.41% (x2); 1.78% vs 1.82% (x50) | No clear effect |
| pre-train the conquering policy before joint training (ablation) | UDC unified training · TSP100 training | convergence | Hurt |
| pre-train the conquering policy and train only the dividing policy (ablation) | UDC unified training · TSP100 training | convergence | Hurt |
Surprising findings
- Pre-training the conquering policy before joint training led training into local optima, so unified training outperformed separate-training variants.
- With a single greedy pass (UDC-x2), UDC is noticeably weaker than baselines such as ICAM and BQ on TSP, requiring many conquering stages to become competitive.
Limitations
- UDC is not applicable to problems where autoregressive construction cannot guarantee legality (e.g., TSPTW), or where sub-problem solutions are unique (dense MIS, job scheduling).
- Greedy single-pass results (UDC-x2) lag several baselines; competitive results require many conquering stages and sampling.
- The authors note that the loss design may be improved; SPCTSP results use a special non-standard setting.
Experimental setup
Datasets: TSP500-1000 random instances CVRP instances (capacity 100-200) MIS ER[700-800] graphs TSPLib CVRPLib Set-X CVRPLib Set-XXL
Benchmarks: TSP500 TSP1000 TSP2000 CVRP500 CVRP1000 CVRP2000 OP PCTSP SPCTSP TSPLib CVRPLib Set-X CVRPLib Set-XXL
Metrics: objective value optimality gap solving time
Baselines: LKH3 BQ LEHD POMO ELG ICAM DIMES DIFUSCO GLOP H-TSP TAM Sym-NCO
Builds on: POMO ICAM AGNN GLOP H-TSP
Closest papers by meaning
- FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimization (ICLR 2026 · similarity 0.89)
- Neural Solver Selection for Combinatorial Optimization (ICML 2025 · similarity 0.88)
- DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization (NeurIPS 2023 · similarity 0.88)
- Geometric Algorithms for Neural Combinatorial Optimization with Constraints (NeurIPS 2025 · similarity 0.87)
- Learning to Explore and Exploit with GNNs for Unsupervised Combinatorial Optimization (ICLR 2025 · similarity 0.87)
- COMBHelper: A Neural Approach to Reduce Search Space for Graph Combinatorial Problems (AAAI 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.