Research map / Learning theory and algorithms / Combinatorial and search optimization
COExpander: Adaptive Solution Expansion for Combinatorial Optimization
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 Adaptive Expansion (AE), a paradigm bridging global prediction and local construction for neural combinatorial optimization, instantiated as COExpander, a consistency-model-based heatmap predictor with partial-solution prompts and adaptive-step greedy determination, evaluated on 6 COPs.
Problem
Neural combinatorial optimization solvers face trade-offs at scale: global prediction heatmaps become overly smooth for long-range decisions, while local autoregressive construction is slow and cannot handle large instances.
Approach
Train a consistency-based global predictor conditioned on masked partial solutions, then iteratively decode its heatmap by determining an adaptive number of decision variables per round, updating the mask after each round so each step starts from a partially determined state.
Key results
- Average optimality drop across 6 COPs reduced from 3.807% (previous neural SOTA) to 0.657%, with a 4.0x speedup.
- On ultra-large RB-GIANT MIS/MCl/MVC and ER-1400-1600 MIS, COExpander outperforms Gurobi with a 3600s limit by 1.9% on average while being about 1134x faster (per the paper's claim).
- On MIS RB-SMALL with S=4, Ds=20, COExpander reaches 1.88% drop in 0.12s versus Fast-T2T's 1.70% drop in 0.86s.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use adaptive expansion instead of the previous neural state-of-the-art solvers | COExpander · Six COPs | average optimality drop: 3.807% to 0.657% | Helped |
| Increase inference steps (Is) from 1 to 20 (ablation) | COExpander · Experiments in Figure 2 | optimality drop: about 7.0% to 4.1% | Helped |
| Increase determination steps (Ds) from 1 to 20 (ablation) | COExpander · Experiments in Figure 2 | optimality drop: about 7.0% to 2.2% | Helped |
| Increase sampling number (S) to 8 (ablation) | COExpander · Experiments in Figure 2 | optimality drop: 4.8% | Helped |
| Use the partial-to-full multi-step determination process rather than noise-to-full multi-step inference (ablation) | COExpander · COP experiments | optimality drop | Helped |
| Use the consistency-model backbone rather than vanilla GCN (ablation) | COExpander · COP experiments | performance | Helped |
| Fine-tune COExpander using the objective-guided MCut loss (ablation) | COExpander · Maximum cut BA-SMALL and BA-LARGE | objective: 727.53 to 726.54; 2989.46 to 2980.51 | Mixed |
Surprising findings
- COExpander performs less favorably on CVRP, which the authors attribute to limitations of the consistency-model global predictor.
- Using RLSA as a standalone solver on MIS sometimes fails to find any feasible solution (e.g., SATLIB, RB-GIANT), while as a post-processor on COExpander it does not.
Limitations
- Performs less favorably on CVRP due to the consistency-model global predictor's limitations.
- Determination rounds and inference steps trade off quality against time; beam search and fine-tuning are needed for best numbers on some tasks.
Experimental setup
Datasets: RB-SMALL RB-LARGE ER-700-800 BA-SMALL BA-LARGE TSP-50 TSP-100 TSP-500 TSP-1K ATSP-50 ATSP-100 ATSP-200
Benchmarks: RB-SMALL RB-LARGE ER-700-800 SATLIB TSP-50 TSP-100 TSP-500 TSP-1K ATSP-50 ATSP-100 ATSP-200 ATSP-500
Metrics: objective optimality drop time
Baselines: KaMIS Gurobi DIFUSCO Fast-T2T DiffUCO Meta-EGN BQ-NCO GOAL MatNet LKH Concorde DIMES
Builds on: Fast-T2T DIFUSCO Consistency Models Joshi et al. GCN for TSP
Closest papers by meaning
- Neural Solver Selection for Combinatorial Optimization (ICML 2025 · similarity 0.86)
- Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization (NeurIPS 2024 · similarity 0.85)
- Large Language Models as End-to-end Combinatorial Optimization Solvers (NeurIPS 2025 · similarity 0.85)
- CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimization (AAAI 2026 · similarity 0.85)
- UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization Problems (NeurIPS 2024 · similarity 0.85)
- Evolution Fine-Tuning: Learning to Discover Across 371 Optimization Tasks (NeurIPS 2026 · similarity 0.84)
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.