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

Kaixi Yang, Linbo Qiao, Wei Shang, Yanqi Shi, Dongsheng LiarXiv 2026 · arXiv

TL;DR

APO2CS introduces a more nuanced way to train neural solvers for combinatorial optimization by moving beyond simple "better or worse" binary comparisons. By incorporating the magnitude of solution quality differences (advantage-awareness) and providing feedback at both the final solution and intermediate construction steps (two-level supervision), it achieves near-optimal results on classic benchmarks like the Traveling Salesman Problem.

What Problem Does This Paper Address?

Combinatorial Optimization Problems (COPs)—like finding the shortest route for a delivery truck (TSP) or packing a knapsack (KP)—are notoriously difficult because their solution spaces are discrete and exponentially large. Traditional deep learning approaches often use Reinforcement Learning (RL), but recently, Preference Optimization (PO) has emerged as a powerful alternative. Instead of needing absolute reward values, PO learns by comparing pairs of solutions.

However, existing PO methods have two major flaws:

  1. Binary Blindness: They typically use binary labels (Solution A is better than Solution B), completely ignoring how much better it is. A 10% improvement is treated the same as a 0.01% improvement, which wastes valuable training signal.
  2. Sparse Supervision: They usually only compare complete solutions. For a constructive solver that builds a solution step-by-step, this "macro-level" feedback is sparse and makes it hard to learn which specific early decisions led to a final success or failure.

Methods

The authors propose APO2CS (Advantage-aware Preference Optimization for Two-level Constructive Search) to bridge these gaps. The framework consists of two core innovations:

1. Advantage-Aware Preference Objective

Instead of a standard binary cross-entropy loss, APO2CS uses an enhanced Bradley-Terry model. It incorporates a normalized quality gap (the "advantage") directly into the preference score. This ensures that pairs with a larger difference in quality exert a stronger influence on the model's gradient updates.

The model is supervised at two distinct levels simultaneously:

  • Macro-level: Compares complete solutions based on their final objective values (e.g., total tour length). This ensures the model stays aligned with the global goal.
  • Micro-level: Decomposes trajectories into local segments. It compares partial constructions from different solutions, providing "denser" feedback throughout the sequential building process.
Figure 1: Overview of the APO2CS framework. Given a COP instance 𝑥, the constructive policy 𝜋𝜃generates candidate solutions and log-probabilities, from which advantage-aware macro-level preferences over complete solutions and micro-level preferences over trajectory segments are constructed. These two preference losses are integrated into the APO2CS objective to update 𝜋𝜃 via back-propagation.

The final training objective is a weighted combination of these two losses, allowing the model to learn both "what a good final solution looks like" and "which local steps lead there."

Datasets

The authors evaluated APO2CS on three fundamental combinatorial benchmarks:

  • Traveling Salesman Problem (TSP): Tested on scales of 20, 50, and 100 nodes.
  • Capacitated Vehicle Routing Problem (CVRP): Tested on scales of 20, 50, and 100 nodes.
  • Knapsack Problem (KP): Tested on scales of 50, 100, and 200 items.

They compared their results against strong traditional heuristics (like Concorde and LKH3) and state-of-the-art neural baselines (like POMO, AM, and other preference-based solvers like BOPO and POCO).

Key Insights and Ideas

  • Magnitude Matters: The "aha moment" here is that the magnitude of improvement in COPs often reflects meaningful optimization progress. By making the loss "advantage-aware," the model learns a more expressive representation of the solution space.
  • Local Guidance Prevents Myopia: While global rewards are essential, they can be noisy for long sequences. Micro-level preferences act as a "local compass," helping the model avoid locally favorable but globally suboptimal decisions.
  • Theoretical Grounding: The authors prove that their objective implicitly induces a gap-modulated policy update. This effectively turns preference learning into a form of pairwise optimization that mirrors the benefits of advantage-based RL without needing a separate value function (critic).

Key Results

APO2CS consistently outperformed existing neural baselines across all tasks:

  • Near-Optimal Performance: On TSP-100, APO2CS achieved a tiny 0.10% optimality gap (without augmentation) and an impressive 0.01% gap with 8-fold augmentation, nearly matching the exact solver Concorde while being significantly faster.
  • Superior to Binary PO: In ablation studies, the advantage-aware macro-level loss alone reduced the TSP-100 gap from 0.59% (standard binary PO) to 0.36%.
  • The Power of Two Levels: Adding the micro-level supervision further slashed that gap from 0.36% down to 0.10%, proving that local trajectory feedback is a critical "missing link" in constructive search.
  • Flexibility: The method works well both when training from scratch ("cold-start") and when fine-tuning a pre-trained model ("warm-start"), showing high adaptability.

Limitations and Future Work

The primary limitation noted is that the micro-level preference pairs rely on predefined trajectory segmentation (fixed-length segments). This rigid segmentation might not always align with the most informative decision boundaries in every problem domain.

The authors suggest that future work could explore adaptive mechanisms for constructing local preference signals and extending the framework to handle more complex, constrained, or heterogeneous combinatorial problems, such as those found in parallel and distributed training environments.

Summary updated

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.
BibTeX
@misc{yang2026apo,
  author = {Kaixi Yang and Linbo Qiao and Wei Shang and Yanqi Shi and Dongsheng Li},
  title = {{APO2CS: Advantage-Aware Preference Optimization for Two-Level Constructive Search in Combinatorial Optimization}},
  year = {2026},
  eprint = {2611.11792},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.11792},
}
Figure