BQ-NCO: Bisimulation Quotienting for Generalizable Neural Combinatorial Optimization

Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, Jean-Marc Andreoli

TL;DR

Neural Combinatorial Optimization (NCO) methods often fail when evaluated on problem instances larger or differently distributed than those seen during training. This paper introduces BQ-NCO, a framework that applies bisimulation quotienting to Markov Decision Process (MDP) formulations of combinatorial problems, collapsing redundant historical states that share identical future decision spaces. Combined with a simple, decoder-free Transformer that re-encodes remaining subproblems at each step, BQ-NCO delivers state-of-the-art out-of-distribution generalization on TSP, CVRP, and Knapsack benchmarks with up to thousands of nodes.

What Problem Does This Paper Address?

Constructive neural heuristics build solutions incrementally—for example, picking one city at a time in the Traveling Salesman Problem (TSP). Typically modeled as MDPs, these neural solvers perform well on instance sizes they were trained on (e.g., graphs with 100 nodes), but their performance sharply deteriorates on larger graphs (e.g., 500 to 1,000+ nodes) or on realistic, non-uniform distributions.

A root cause is poor state representation: standard constructive MDPs maintain the entire history of visited nodes. However, for future optimization, the exact route taken through previously visited interior nodes is completely irrelevant. Storing this unneeded information inflates the state space and forces neural networks to learn identical continuation policies across formally distinct, but functionally equivalent, states.

Methods

The authors introduce a principled reformulation of combinatorial optimization using Bisimulation Quotienting (BQ):

  • Bisimulation Quotienting (BQ): In transition systems, two states are bisimilar if they generate identical future action-reward sequences. BQ quotients the state space by this equivalence relation ($\equiv_\Phi$), discarding internal history while retaining only what is strictly necessary to decide future actions:
  • TSP: Discards visited intermediate nodes, retaining only the path's origin, destination, and the set of unvisited nodes (path-TSP).
  • CVRP: Retains unvisited nodes, endpoint nodes, and the vehicle's remaining capacity.
  • Knapsack (KP): Retains only the remaining item pool and residual knapsack capacity.
  • Decoder-Free Transformer Architecture: Because intermediate nodes are forgotten, the model eliminates auto-regressive decoders. Instead, a Transformer encoder processes the current subproblem state at every construction step, augmented with learned origin and destination tokens and ReZero normalization. A linear projection and masked softmax select the next action.
  • Subproblem Imitation Learning: Models are trained using behavior cloning on trajectories derived from exact/heuristic solvers (Concorde for TSP, LKH for CVRP, dynamic programming for KP). Because any sub-path of an optimal tour is an optimal path-TSP solution, training batches are sampled from arbitrary sub-paths of length $n \in [4, N]$, exposing the network to diverse problem sizes and node densities automatically.
Standard MDP State (Full History):
[Start] -> (A) -> (B) -> (C) -> [Current] ... [Unvisited Nodes]

Bisimulation Quotiented State (BQ-NCO):
[Start] ----------------------> [Current] ... [Unvisited Nodes]
          (History collapsed)

Datasets

  • Synthetic Benchmarks: Uniformly generated instances of sizes 100, 200, 500, and 1,000 nodes for TSP and CVRP (capacities 50, 80, 100, and 250), as well as Knapsack instances of 200, 500, and 1,000 items (capacities 25 and 50). All models were trained only on size-100 instances (size-200 for Knapsack).
  • Realistic / Standard Benchmarks:
  • TSPLib: Standard benchmark instances containing up to 4,461 nodes.
  • CVRPLib: Benchmark sets (A, B, F, M, P, and X) featuring varied node densities, customer demands, and capacities (15 to 1,000+ nodes).

Key Insights and Ideas

  • Symmetries as Information Forgetting: Recognizing that past decisions do not constrain future costs beyond boundary conditions enables drastic state compression without losing optimality guarantees.
  • Free Data Augmentation: Framing the problem as path-completion allows the extraction of valid, optimal sub-instances of varying sizes from a single solved instance, naturally teaching the policy to handle different scales and local topologies.
  • The Value of Quadratic Step Compute: Standard models encode the full graph once ($O(N^2)$) and take cheap decoding steps ($O(t)$). BQ-NCO re-encodes the remaining $t$ nodes at each step ($O(t^2)$ compute per step, totaling $O(N^3)$). An ablation replacing self-attention with the linear-time HyperMixer severely degraded out-of-distribution scaling, showing that allocating compute proportional to the remaining subproblem's complexity is a crucial inductive bias.

Key Results

  • TSP Generalization: On synthetic TSP1000, BQ with greedy decoding achieved a 2.335% optimality gap, and 1.311% with beam size 16. In contrast, POMO (with $\times 8$ augmentation) degraded to 40.603%, and MDAM reached 19.965%. On TSPLib instances over 1,000 nodes, BQ achieved an 8.61% gap (beam size 16) versus POMO's 62.61%.
  • CVRP Generalization: On CVRP1000, BQ (beam size 16) achieved a 2.048% gap relative to LKH, whereas POMO collapsed to 141.058% and MDAM reached 28.015%. On CVRPLib Set X, BQ achieved 8.35% versus POMO's 21.62%.
  • Knapsack: Across all tested problem sizes up to 1,000 items, greedy BQ achieved an overall optimality gap of 1.980%, outperforming POMO evaluating across all trajectories (2.648%).

Limitations and Future Work

  • Computational Cost: Calling the Transformer encoder at every decision step scales overall construction time to $O(N^3)$ (though the authors show $k$-nearest-neighbor pruning can mitigate inference latency).
  • Deterministic Focus: The theoretical formulation and equivalence proofs currently apply only to deterministic combinatorial optimization problems; extending BQ to stochastic environments remains open.
  • Dependency on Expert Trajectories: Training relies on pre-computed solutions from classical solvers via behavior cloning. While reinforcement learning could theoretically replace imitation, its sample efficiency under this formulation was not evaluated.
  • CVRP Trajectory Ordering Bias: For CVRP, the arbitrary order in which distinct vehicle subtours are presented in expert demonstration data influenced final model performance.

Summary updated

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 and Capacitated Vehicle Routing 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.
BibTeX
@inproceedings{drakulic2023bq,
  author = {Darko Drakulic and Sofia Michel and Florian Mai and Arnaud Sors and Jean-Marc Andreoli},
  title = {{BQ-NCO: Bisimulation Quotienting for Generalizable Neural Combinatorial Optimization}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=5ZLWi--i57},
}

Loading related content...

Figure