BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization
This addresses a bottleneck in neural combinatorial optimization for researchers and practitioners, offering an incremental improvement over existing RL-based methods.
The paper tackled the problem of low sample efficiency in neural combinatorial optimization by proposing BOPO, a training paradigm that uses solution preferences based on objective values, which outperformed state-of-the-art methods on problems like JSP, TSP, and FJSP with reduced optimality gaps.
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.