2025/03/10 by Zijun Liao, Jinbiao Chen, Liao, Zijun +7 · 4 citations
Computer Science · #Advanced Multi-Objective Optimization Algorithms #Advanced Neural Network Applications #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Data Classification
paper · pdf · doi:10.48550/arxiv.2503.07580
openalex publication_date 2025/03/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.