pipette
ENEnglish

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

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

Preprint

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: martes, 10 de noviembre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 10 pages, 2 figures