Research map / Reinforcement learning / RL from feedback
BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference 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 BOPO, a preference-optimization training paradigm for neural combinatorial optimization that builds best-anchored preference pairs from sampled solutions and uses an objective-guided loss, evaluated on JSP, TSP and FJSP.
Problem
Neural combinatorial optimization trained with RL or self-labeling suffers from low sample efficiency because of sparse rewards and discarding most sampled solutions.
Approach
Treat objective values of sampled solutions as explicit preferences, pair the best solution with several suboptimal ones (best-anchored pairing), and optimize a DPO/SimPO-like pairwise loss on length-normalized log-likelihoods scaled by the ratio of objective values, with no reward model or reference policy.
Key results
- On TA JSP benchmark, BOPO with 512 sampled solutions reaches 7.5% average gap versus 7.8% for SLIM with the same model family (SLIM_MGL 9.6 at B'=128 vs BOPO 7.5 at B'=512 w/ sampling reported in the table averages).
- On TSP100 uniform instances, BOPO (aug.) reaches 0.04% gap vs POMO (aug.) 0.14% and SLIM (aug.) 1.17%.
- On FJSP LA e-data with 512 samples, BOPO achieves 5.0% gap vs 6.9% for RS at 100 samples.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use BOPO instead of SLIM | JSP LA benchmark · JSP LA Avg | optimality gap (%): 2.5 -> 2.3 | Helped |
| use BOPO instead of SLIM | JSP DMU benchmark · JSP DMU Avg | optimality gap (%): 13.1 -> 12.9 | Helped |
| use BOPO instead of POMO | TSP100 with augmentation · TSP100 | Gap: 0.14 -> 0.04 | Helped |
| use BOPO instead of SLIM | TSPLIB generalization · TSPLIB 500≤n<1k | Gap: 55.57 -> 22.44 | Helped |
| increase inference samples from B'=100 to B'=512 | BOPO on FJSP · FJSP LA(e-data) | optimality gap (%): 6.1 -> 5.0 | Helped |
| replace hybrid rollout with sampling rollout (ablation) | BOPO preference-pair construction · JSP DMU Avg | optimality gap (%): 13.3 -> 14.4 | Hurt |
| replace uniform filtering with random filtering (ablation) | BOPO preference-pair construction · JSP DMU Avg | optimality gap (%): 13.3 -> 14.0 | Mixed |
| replace uniform filtering with top-K filtering (ablation) | BOPO preference-pair construction · JSP DMU Avg | optimality gap (%): 13.3 -> 15.6 | Hurt |
| replace uniform filtering with bottom-K filtering (ablation) | BOPO preference-pair construction · JSP DMU Avg | optimality gap (%): 13.3 -> 14.1 | Mixed |
| replace best-anchored pairing with full permutation pairing (ablation) | BOPO preference-pair construction · JSP DMU Avg | optimality gap (%): 13.3 -> 14.1 | Mixed |
| add objective-guided scaling to the preference loss (ablation) | BOPO loss · JSP TA | optimality gap (%): 8.5 -> 8.2 | Helped |
| add objective-guided scaling to the preference loss (ablation) | BOPO loss · JSP LA | optimality gap (%): 2.4 -> 2.9 | No clear effect |
Surprising findings
- SimPO performs poorly on the DMU out-of-distribution benchmark, suggested to come from overfitting caused by its target margin term.
- For small-scale TSP (TSP20/50), a small B (20/50) performs comparably to B=128, suggesting the optimal number of rollouts is low at small scales.
Limitations
- Still requires a relatively large number of rollout solutions, similar to SLIM, which costs training-time compute.
- Training is slower to converge in some settings and memory grows with the number of rollouts B.
Experimental setup
Datasets: Taillard (TA) Lawrence (LA) Demirkol (DMU) TSPLIB synthetic JSP instances following SLIM synthetic FJSP instances
Benchmarks: TA LA DMU TSP20/50/100 TSPLIB FJSP LA e-data/r-data/v-data
Metrics: optimality gap (%) solving time
Baselines: SLIM POMO DABL INViT L2D SchN CL L2S TGA NLS PDR (SPT, MOR, MWR) HG
Builds on: direct preference optimization simple preference optimization POMO SLIM REINFORCE
Closest papers by meaning
- Probing Neural Combinatorial Optimization Models (NeurIPS 2025 · similarity 0.88)
- Preference-Driven Multi-Objective Combinatorial Optimization with Conditional Computation (NeurIPS 2025 · similarity 0.87)
- Neural Solver Selection for Combinatorial Optimization (ICML 2025 · similarity 0.87)
- Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning (NeurIPS 2025 · similarity 0.87)
- Neural Combinatorial Optimization for Stochastic Flexible Job Shop Scheduling Problems (AAAI 2025 · similarity 0.87)
- Preference Optimization for Combinatorial Optimization Problems (ICML 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.