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:
- 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.
- 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.
2. Two-Level Constructive Search
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.
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