Neural Combinatorial Optimization via Preference Optimization
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 Preference Optimization for Combinatorial Optimization (POCO), a training paradigm that leverages solution preferences via objective values. It introduces: (1) an efficient preference pair construction for better explore and exploit solutions, and (2) a novel loss function that adaptively scales gradients via objective differences, removing reliance on reward models or reference policies. Experiments on Job-Shop Scheduling (JSP), Traveling Salesman (TSP), and Flexible Job-Shop Scheduling (FJSP) show POCO outperforms state-of-the-art neural methods, reducing optimality gaps impressively with efficient inference. POCO is architecture-agnostic, enabling seamless integration with existing NCO models, and establishes preference optimization as a principled framework for combinatorial optimization.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationJob Shop SchedulingSchedulingSimilar Papers 제목 키워드 기반
Preference Optimization for Combinatorial Optimization Problems
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 pr…
Combinatorial OptimizationReinforcement Learning (RL)Traveling Salesman ProblemRethinking Efficiency in Neural Combinatorial Optimization: Batched Preference Optimization with Mamba
We study efficiency as a first-class objective in Neural Combinatorial Optimization (NCO) and present ECO, an efficient learning framework that combines batched preference optimization with a Mamba backbone. Instead of t…
UCPO: A Universal Constrained Combinatorial Optimization Method via Preference Optimization
Neural solvers have demonstrated remarkable success in combinatorial optimization, often surpassing traditional heuristics in speed, solution quality, and generalization. However, their efficacy deteriorates significantl…
Preference Conditioned Neural Multi-objective Combinatorial Optimization
Multiobjective combinatorial optimization (MOCO) problems can be found in many real-world applications. However, exactly solving these problems would be very challenging, particularly when they are NP-hard. Many handcraf…
Combinatorial OptimizationTraveling Salesman ProblemAutoPref: Automatic Discovery of Task-Specific Preference Objectives for Neural Combinatorial Optimization
Combinatorial optimization problems (COPs) underpin many real-world decisions, but their exponentially large search spaces make high-quality solutions costly to obtain. Neural combinatorial optimization (NCO) learns fast…
Reinforcement Learning