Preference Optimization for Combinatorial Optimization Problems
This addresses inefficiencies in RL-based combinatorial optimization for researchers and practitioners, though it appears incremental as it builds on existing RL frameworks.
The paper tackles the problem of inefficient exploration and diminishing reward signals in reinforcement learning for combinatorial optimization by proposing Preference Optimization, which transforms quantitative rewards into qualitative preference signals. The method achieves superior convergence efficiency and solution quality on benchmarks including TSP, CVRP, and FFSP.
Reinforcement Learning (RL) has emerged as a powerful tool for neural combinatorial optimization, enabling models to learn heuristics that solve complex problems without requiring expert knowledge. Despite significant progress, existing RL approaches face challenges such as diminishing reward signals and inefficient exploration in vast combinatorial action spaces, leading to inefficiency. In this paper, we propose Preference Optimization, a novel method that transforms quantitative reward signals into qualitative preference signals via statistical comparison modeling, emphasizing the superiority among sampled solutions. Methodologically, by reparameterizing the reward function in terms of policy and utilizing preference models, we formulate an entropy-regularized RL objective that aligns the policy directly with preferences while avoiding intractable computations. Furthermore, we integrate local search techniques into the fine-tuning rather than post-processing to generate high-quality preference pairs, helping the policy escape local optima. Empirical results on various benchmarks, such as the Traveling Salesman Problem (TSP), the Capacitated Vehicle Routing Problem (CVRP) and the Flexible Flow Shop Problem (FFSP), demonstrate that our method significantly outperforms existing RL algorithms, achieving superior convergence efficiency and solution quality.