Abstract
Despite the success of Neural Combinatorial Optimization methods for end-to-end heuristic learning, out-of-distribution generalization remains a challenge. In this paper, we present a novel formulation of combinatorial optimization (CO) problems as Markov Decision Processes (MDPs) that effectively leverages symmetries of the CO problems to improve out-of-distribution robustness. Starting from the standard MDP formulation of constructive heuristics, we introduce a generic transformation based on bisimulation quotienting (BQ) in MDPs. This transformation allows to reduce the state space by accounting for the intrinsic symmetries of the CO problem and facilitates the MDP solving. We illustrate our approach on the Traveling Salesman, Capacitated Vehicle Routing and Knapsack Problems. We present a BQ reformulation of these problems and introduce a simple attention-based policy network that we train by imitation of (near) optimal solutions for small instances from a single distribution. We obtain new state-of-the-art generalization results for instances with up to 1000 nodes from synthetic and realistic benchmarks that vary both in size and node distributions.
Introduction
Combinatorial Optimization Problems (COPs), such as the Traveling Salesman Problem (TSP) or the Knapsack Problem, are fundamental challenges in computer science and operations research. While neural networks have emerged as powerful tools for learning heuristics to solve these NP-hard problems, they often struggle with generalization. A model trained on small instances (e.g., 50 nodes) typically fails when applied to significantly larger ones (e.g., 500 nodes).
The core issue lies in how these problems are represented. Most existing methods use ad-hoc Markov Decision Process (MDP) formulations that do not naturally account for problem symmetries. BQ-NCO addresses this by introducing a principled framework that exploits structural symmetries through "Bisimulation Quotienting," focusing the model on the remaining subproblem rather than the entire history of the partial solution.
Methodology: Bisimulation Quotienting and MDP Reformulation
The BQ-NCO framework involves two primary steps. First, any COP is cast as a generic MDP where states represent partial solutions and actions represent construction steps. Second, the authors apply Bisimulation Quotienting (BQ) to collapse equivalent states.
In many COPs, different partial solutions lead to functionally identical "tail subproblems." For instance, in a TSP, if two different paths have visited the same set of cities and ended at the same city, the remaining task is identical regardless of the previous path taken. BQ identifies these symmetries, drastically compressing the state space and allowing the model to learn the "essence" of the task.
Architecture and Training
Because the BQ-MDP state is essentially a smaller instance of the original problem, BQ-NCO avoids complex encoder-decoder architectures. Instead, it utilizes a simple Transformer-based policy network. For extremely large instances, the authors experiment with PerceiverIO to mitigate the computational bottleneck of standard attention mechanisms.
The model is trained via Imitation Learning. Rather than complex Reinforcement Learning, the network is trained to mimic (near) optimal solutions on small instances (e.g., N=100) using standard cross-entropy loss. This approach naturally provides "data augmentation" as the model sees sub-sequences of optimal trajectories, effectively training on problems of varying sizes and distributions.
Key Results and Generalization
BQ-NCO demonstrates remarkable zero-shot generalization capabilities across several classic COPs, including TSP, CVRP, and the Knapsack Problem.
- Scaling to Large Instances: On 1,000-node TSP instances, a single greedy rollout achieved an optimality gap of only 2.29%, significantly outperforming other end-to-end models like POMO and Sym-NCO, which often see gaps exceed 30%.
- Real-World Benchmarks: On the CVRPLib benchmark, BQ-NCO achieved an average gap of 4.83%, a substantial improvement over previous state-of-the-art methods like MDAM (22.36%) and POMO (15.58%).
- Efficiency: The integration of PerceiverIO allows the model to maintain high accuracy while significantly speeding up inference on large-scale graphs compared to standard Transformers.
Conclusion
By focusing on recursive symmetries through Bisimulation Quotienting, BQ-NCO provides a robust framework for neural combinatorial optimization. The method's ability to solve instances up to 10x larger than those seen during training marks a significant step toward practical, generalizable AI solvers for complex logistics and planning problems. Future work will explore extending this framework to stochastic problems and reducing the dependency on expert solvers for training data.
Summary updated