Research map / Reinforcement learning / RL from feedback
Preference Optimization for 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 Preference Optimization (PO), which converts reward comparisons among sampled COP solutions into Bradley-Terry-style preference labels on policy log-probabilities, and fine-tunes with local search outputs as preferred solutions, evaluated on TSP, CVRP and FFSP neural solvers.
Problem
Neural combinatorial optimization trained with REINFORCE-style RL suffers from diminishing advantage signals and inefficient exploration in huge action spaces, and local search gains are not absorbed by the policy without extra inference cost.
Approach
Reparameterize the reward through the policy (r = alpha log pi + const from the entropy-regularized optimum) so that preferences between sampled solutions, labeled by the ground-truth reward indicator, become a classification loss on log-probabilities; integrate local-search-refined solutions as preferred samples during a fine-tuning phase.
Key results
- PO converges 1.5x to 2.5x faster than REINFORCE on POMO, Sym-NCO and Pointerformer; POMO with PO for 80 epochs matches RF at 200 epochs.
- POMO+PO+Finetune reaches 0.03% gap on TSP-100 and 1.19% on CVRP-100 versus 0.07% and 1.37% for PO alone and 0.15% and 1.76% for RF.
- On FFSP, MatNet (PO+Aug.) reports 0.00% gap across FFSP20/50/100 versus 0.79%/0.20%/0.56% for RF+Aug.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace REINFORCE with Preference Optimization in POMO | POMO · TSP | Gap: 0.15% -> 0.07% (TSP-100) | Helped |
| Replace REINFORCE with Preference Optimization in POMO | POMO · CVRP | Gap: 1.76% -> 1.37% (CVRP-100) | Helped |
| Add local-search fine-tuning to PO (ablation) | POMO with PO · TSP-100 | Gap: 0.07% -> 0.03% | Helped |
| Add local-search fine-tuning to PO (ablation) | POMO with PO · CVRP | Gap: 1.37% -> 1.19% (CVRP-100) | Helped |
| Replace REINFORCE with Preference Optimization in MatNet | MatNet · FFSP | Gap: 2.58% -> 2.13% (FFSP100) | Helped |
| Replace REINFORCE with Preference Optimization in ELG | ELG · TSPLib total | Gap: 3.08% -> 3.00% | Helped |
| Replace REINFORCE with Preference Optimization in ELG | ELG · CVRPLib total | Gap: 6.03% -> 5.94% | Helped |
| Train with PO instead of REINFORCE | POMO and Sym-NCO · TSP-100 training | Training epochs to comparable performance: 80 epochs vs. 200 epochs | Helped |
| Train with PO instead of REINFORCE | POMO, Sym-NCO, and Pointerformer · TSP-100 training | Convergence speed: 1.5x to 2.5x | Helped |
Surprising findings
- The Bradley-Terry preference model outperforms other preference models (Thurstone, Plackett-Luce, exponential) on TSP-100 in their study.
Limitations
- Stability of the reparameterized reward across diverse COPs is not fully investigated.
- Local search fine-tuning adds per-iteration training overhead.
- Alpha must be tuned per problem-model combination via grid search.
Experimental setup
Datasets: uniform random TSP instances uniform random CVRP instances FFSP instances TSPLib CVRPLib Set-X
Benchmarks: TSP-20/50/100 CVRP-20/50/100 FFSP20/50/100 TSPLib CVRPLib-Set-X
Metrics: optimality gap inference time training convergence epochs consistency trajectory entropy
Baselines: REINFORCE (RF) POMO Sym-NCO Pointerformer AM ELG MatNet LKH3 HGS Concorde CPLEX
Builds on: REINFORCE POMO Bradley-Terry preference model maximum entropy RL DPO
Closest papers by meaning
- Combinatorial Optimization with Policy Adaptation using Latent Space Search (NeurIPS 2023 · similarity 0.91)
- Winner Takes It All: Training Performant RL Populations for Combinatorial Optimization (NeurIPS 2023 · similarity 0.90)
- Preference-Driven Multi-Objective Combinatorial Optimization with Conditional Computation (NeurIPS 2025 · similarity 0.89)
- Combinatorial Reinforcement Learning with Preference Feedback (ICML 2025 · similarity 0.89)
- Efficient Preference-Based Reinforcement Learning: Randomized Exploration meets Experimental Design (NeurIPS 2025 · similarity 0.87)
- Structured Reinforcement Learning for Combinatorial Decision-Making (NeurIPS 2025 · similarity 0.87)
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.