mlsanityData to 7 Oct 2026

BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization

arXiv 2503.07580 ↗First posted 10 Mar 2025cs.LGcited by 14

On the map: LLM alignment / RLHF / preference optimisation → LLM preference optimization methods

Abstract (arXiv)

Neural Combinatorial Optimization (NCO) has emerged as a promising approach for NP-hard problems. However, prevailing RL-based methods suffer from low sample efficiency due to sparse rewards and underused solutions. We propose Best-anchored and Objective-guided Preference Optimization (BOPO), a training paradigm that leverages solution preferences via objective values. It introduces: (1) a best-anchored preference pair construction for better explore and exploit solutions, and (2) an objective-guided pairwise loss function that adaptively scales gradients via objective differences, removing reliance on reward models or reference policies. Experiments on Job-shop Scheduling Problem (JSP), Traveling Salesman Problem (TSP), and Flexible Job-shop Scheduling Problem (FJSP) show BOPO outperforms state-of-the-art neural methods, reducing optimality gaps impressively with efficient inference. BOPO is architecture-agnostic, enabling seamless integration with existing NCO models, and establishes preference optimization as a principled framework for combinatorial optimization.

Key facts. Cited by 14 papers in the map (data through 7 Oct 2026). Placed in LLM preference optimization methods, one of 10 directions in LLM alignment / RLHF / preference optimisation. Builds on 46 of its 76 references that are in the map. First posted on arXiv 10 Mar 2025.

Builds on

46 of 76 references.

Closest ancestors · 4

Same direction, newest first

  1. 2024SimPO: Simple Preference Optimization with a Reference-Free Reward23 May
  2. 2023Some things are more CRINGE than others: Iterative Preference Optimization with the Pairwise Cringe Loss27 Dec
  3. 2023Preference Ranking Optimization for Human Alignment30 Jun
  4. 2022Training language models to follow instructions with human feedback4 Mar

Other references · 42

  1. 2017Attention Is All You Needcited by 59,932
  2. 2017Proximal Policy Optimization Algorithmscited by 14,441
  3. 2017Graph Attention Networkscited by 8,854
  4. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Modelcited by 7,916
  5. 2020Learning to summarize from human feedbackcited by 2,562
  6. 2015Pointer Networkscited by 882
  7. 2023RAFT: Reward rAnked FineTuning for Generative Foundation Model Alignmentcited by 672
  8. 2018Attention, Learn to Solve Routing Problems!cited by 646
  9. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 612
  10. 2020POMO: Policy Optimization with Multiple Optima for Reinforcement Learningcited by 341
  11. 2020Reinforcement Learning for Combinatorial Optimization: A Surveycited by 235
  12. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 216
30 more
  1. 2019Learning Improvement Heuristics for Solving Routing Problemscited by 162
  2. 2023Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalizationcited by 140
  3. 2020Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learningcited by 139
  4. 2021Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformercited by 108
  5. 2023Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Optcited by 81
  6. 2023BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimizationcited by 80
  7. 2024MVMoE: Multi-Task Vehicle Routing Solver with Mixture-of-Expertscited by 69
  8. 2022Winner Takes It All: Training Performant RL Populations for Combinatorial Optimizationcited by 57
  9. 2021Learning to schedule job-shop problems: Representation and policy learning using graph neural network and reinforcement learningcited by 52
  10. 2024UDC: A Unified Neural Divide-and-Conquer Framework for Large-Scale Combinatorial Optimization Problemscited by 45
  11. 2024INViT: A Generalizable Routing Problem Solver with Invariant Nested View Transformercited by 43
  12. 2025Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimizationcited by 43
  13. 2023Combinatorial Optimization with Policy Adaptation using Latent Space Searchcited by 41
  14. 2021ScheduleNet: Learn to solve multi-agent scheduling problems with reinforcement learningcited by 31
  15. 2024Self-Improved Learning for Scalable Neural Combinatorial Optimizationcited by 29
  16. 2024Learning to Handle Complex Constraints for Vehicle Routing Problemscited by 29
  17. 2023ASP: Learn a Universal Neural Solver!cited by 27
  18. 2024Self-Labeling the Job Shop Scheduling Problemcited by 23
  19. 2023Efficient Meta Neural Heuristic for Multi-Objective Combinatorial Optimizationcited by 21
  20. 2022Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop Schedulingcited by 20
  21. 2023Distilling Autoregressive Models to Obtain High-Performance Non-Autoregressive Solvers for Vehicle Routing Problems with Faster Inference Speedcited by 19
  22. 2022Learning to Control Local Search for Combinatorial Optimizationcited by 18
  23. 2019A concise guide to existing and emerging vehicle routing problem variantscited by 17
  24. 2023Neural Multi-Objective Combinatorial Optimization with Diversity Enhancementcited by 13
  25. 2023Residual Scheduling: A New Reinforcement Learning Approach to Solving Job Shop Scheduling Problemcited by 12
  26. 2023An End-to-End Reinforcement Learning Approach for Job-Shop Scheduling Problems Based on Constraint Programmingcited by 11
  27. 2024Hierarchical Neural Constructive Solver for Real-world TSP Scenarioscited by 9
  28. 2024Collaboration! Towards Robust Neural Methods for Routing Problemscited by 9
  29. 2023Symmetric Replay Training: Enhancing Sample Efficiency in Deep Reinforcement Learning for Combinatorial Optimizationcited by 6
  30. 2024Learning Topological Representations with Bidirectional Graph Attention Network for Solving Job Shop Scheduling Problemcited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 2; 2026: 12.

14 papers.

Sort:

By area:

  1. 2025Preference-Driven Multi-Objective Combinatorial Optimization with Conditional Computationcited by 6
  2. 2026CADO: From Imitation to Cost Minimization for Heatmap-based Solvers in Combinatorial Optimizationcited by 1
  3. 2026Learning with Foresight: Enhancing Neural Routing Policy via Multi-Node Lookahead Predictioncited by 1
  4. 2026Reinforcement Learning Enhanced LLM Agents for Complex Vehicle Routing Problemscited by 1
  5. 2025Instance-Aware Algorithm Selection for Maximum Clique via a Dual-Channel Graph Neural Architecturecited by 0
  6. 2026Rethinking Efficiency in Neural Combinatorial Optimization: Batched Preference Optimization with Mambacited by 0
  7. 2026Enhancing Cross-Problem Vehicle Routing via Federated Learningcited by 0
  8. 2026FiLMMeD: Feature-wise Linear Modulation for Cross-Problem Multi-Depot Vehicle Routingcited by 0
  9. 2026WeCon: An Efficient Weight-Conditioned Neural Solver for Multi-Objective Combinatorial Optimization Problemscited by 0
  10. 2026MViewRouter: Internalizing Geometric Equivariance via Multi-view Alternating Attention for Combinatorial Routingcited by 0
  11. 2026TSP with Predictions: Heatmap to Tour with Provable Guaranteescited by 0
  12. 2026AutoPref: Automatic Discovery of Task-Specific Preference Objectives for Neural Combinatorial Optimizationcited by 0
2 more
  1. 2026SSPO: Structure-Aware Similarity-Weighted Preference Optimization for Neural Combinatorial Optimizationcited by 0
  2. 2026Improving Cross-Problem Vehicle Routing with Locally Augmented Preferences and Representation Disentanglementcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Unsupervised Training of Diffusion Models for Feasible Solution Generation in Neural Combinatorial Optimization
  2. 2025Preference Optimization for Combinatorial Optimization Problems
  3. 2024Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvement
  4. 2026Baseline-Free Policy Optimization for Neural Combinatorial Optimization
  5. 2025FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimization
  6. 2025Preference Elicitation for Multi-objective Combinatorial Optimization with Active Learning and Maximum Likelihood Estimation
  7. 2025Boosting Cross-problem Generalization in Diffusion-Based Neural Combinatorial Solver via Inference Time Adaptation
  8. 2026Offline Decision Transformers for Neural Combinatorial Optimization: Surpassing Heuristics on the Traveling Salesman Problem