cs.LGNov 9, 2026

APO2CS: Advantage-Aware Preference Optimization for Two-Level Constructive Search in Combinatorial Optimization

Authors: Kaixi Yang, Linbo Qiao, Wei Shang, Yanqi Shi, Dongsheng Li

Organizations: National University of Defense Technology, Changsha, China

Abstract

Preference optimization has emerged as a promising alternative to reward-based training for neural combinatorial optimization. However, existing methods typically rely on binary pairwise labels, which discard the magnitude of solution-quality differences and provide supervision only at the complete-solution level. We propose Advantage-aware Preference Optimization for Two-level Constructive Search (APO2CS), a preference-based training objective for constructive neural solvers that integrates both macro-level and micro-level supervision. At the macro level, APO2CS enriches pairwise preferences with an advantage term derived from objective-value differences. At the micro level, it compares partial trajectories, thereby providing denser supervision throughout the sequential construction process. The resulting objective can be used either to train a policy from scratch or to fine-tune a pretrained one. Experimental results show that APO2CS improves the expressiveness and search capability of preference learning for combinatorial optimization, while demonstrating strong effectiveness and adaptability across multiple combinatorial optimization tasks.

Figures & tables

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. AutoPref: Automatic Discovery of Task-Specific Preference Objectives for Neural Combinatorial Optimization

    Jul 30, 2026Shengda Gu, Kai Li, Xinyi Ke +3Automated Algorithm DiscoveryPairwise Preference Evaluation

  2. SSPO: Structure-Aware Similarity-Weighted Preference Optimization for Neural Combinatorial Optimization

    Aug 12, 2026Yuanyu Li, Jintao Xu, Zijiang Liu +6Combinatorial OptimizationPreference Optimization

  3. Reward-Weighted Preference Optimization for Selective Combinatorial Optimization Problems

    Oct 22, 2026Haohui Zhang, Xinyu Hu, Wouter van Heeswijk +2RL for Combinatorial OptimizationCombinatorial Optimization