Research map / Learning theory and algorithms / Combinatorial and search optimization
PolyNet: Learning Diverse Solution Strategies for Neural 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 PolyNet, a single-decoder neural construction model that learns K complementary solution strategies via a conditioning bit vector and best-of-K (Poppy-style) training, improving exploration without forcing diverse first actions.
Problem
Neural combinatorial optimization construction methods explore the solution space poorly; existing diversity mechanisms either rely on handcrafted first-action forcing (POMO) or need multiple decoders (Poppy, MDAM), which are costly and not suited to complex constraints like CVRPTW.
Approach
A single decoder conditioned on K unique bit vectors (via added PolyNet residual layers) is trained with Poppy-style best-of-K updates, so diversity emerges implicitly from the loss without forced first moves or KL regularization.
Key results
- On TSP n=100 with 10K instances, PolyNet reaches 0.000% gap in 4 minutes vs LKH3 at 8h, and PolyNet+EAS matches Concorde.
- On CVRP n=100, PolyNet+EAS reaches 0.14% gap versus 0.35% for POMO+EAS, and unguided PolyNet reaches 0.49% vs 0.78% for Poppy.
- On CVRPTW n=100, PolyNet+EAS achieves 0.96% gap vs 1.81% for POMO+EAS, and forced-first-move ablation shows free first move is better (2.73% vs 3.00%).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| learn diverse solution strategies with a single decoder | PolyNet · TSP, CVRP, and CVRPTW | solution quality | Helped |
| use PolyNet's learned strategies instead of forced first actions (ablation) | PolyNet · TSP, CVRP, and CVRPTW, n=100 | Gap: 0.006% -> 0.000%; 0.59% -> 0.49%; 3.00% -> 2.73% | Helped |
| add the PolyNet layers (ablation) | PolyNet · TSP, CVRP, and CVRPTW validation | validation cost | Helped |
| warm-start training from a trained POMO model instead of training from scratch (ablation) | PolyNet · CVRP and CVRPTW | validation performance | Helped |
| warm-start training from a trained POMO model instead of training from scratch (ablation) | PolyNet · TSP | validation performance | No clear effect |
| increase the number of learned strategies K (ablation) | PolyNet · TSP, CVRP, and CVRPTW validation | solution cost | Helped |
| increase the number of learned strategies K (ablation) | PolyNet · TSP, CVRP, and CVRPTW validation | percentage of unique solutions | Helped |
| use learned strategy-conditioned sampling rather than forced-first-action sampling | PolyNet · TSP | average broken pairs distance: 2.400 -> 4.621 | Helped |
| use learned strategy-conditioned sampling rather than forced-first-action sampling | PolyNet · CVRP | average broken pairs distance: 16.785 -> 18.535 | Helped |
| use learned strategy-conditioned sampling rather than forced-first-action sampling | PolyNet · CVRPTW | average broken pairs distance: 18.162 -> 19.969 | Helped |
| increase the search budget (ablation) | PolyNet with larger K · TSP, CVRP, and CVRPTW, n=100 | minimum solution cost | Helped |
Surprising findings
- PolyNet selects fewer distinct first nodes than POMO yet produces more diverse solutions overall, suggesting diversity arises through means other than forcing the first action.
- Cold-start training of PolyNet on CVRP and CVRPTW remains worse than warm-started models even after 400 epochs, and only on TSP does cold-start converge.
Limitations
- Autoregressive attention cost restricts applicability to instances below about 1000 nodes.
- Black-box decision-making may be unacceptable in some decision contexts.
- Warm-starting from POMO is used for main results; cold-start is slower and worse on CVRP/CVRPTW.
Experimental setup
Datasets: randomly generated TSP, CVRP, CVRPTW, and FFSP instances
Benchmarks: TSP test sets (n=100, 200, 150, 300) CVRP test sets (n=100, 200, 150, 300) CVRPTW test sets (n=100, 200, 150, 300) FFSP20/50/100
Metrics: objective value optimality gap runtime average broken pairs distance makespan
Baselines: POMO Poppy MDAM DPDP COMPASS DACT SGBS LKH3 HGS Concorde PyVRP MatNet
Builds on: POMO Poppy EAS MatNet
Closest papers by meaning
- Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Method (NeurIPS 2023 · similarity 0.89)
- Neural Solver Selection for Combinatorial Optimization (ICML 2025 · similarity 0.87)
- Preference Optimization for Combinatorial Optimization Problems (ICML 2025 · similarity 0.87)
- GOAL: A Generalist Combinatorial Optimization Agent Learner (ICLR 2025 · similarity 0.86)
- Large Language Models as End-to-end Combinatorial Optimization Solvers (NeurIPS 2025 · similarity 0.86)
- Geometric Algorithms for Neural Combinatorial Optimization with Constraints (NeurIPS 2025 · 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.