PaperlayerView exact revision on arXiv

Source-linked AI summary

BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization

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

arXiv:2301.03313v3cs.LGmath.OC

TL;DR

Neural combinatorial optimization has had success learning heuristics, but out-of-distribution generalization remains a challenge. This paper derives direct MDPs for constructive COPs and reduces their states through bisimulation quotienting, with a specialization for recursive problems. Across five COPs, the authors report state-of-the-art results and strong generalization to much larger instances than seen in training, without additional search.

  • Problem

    Out-of-distribution generalization remains a challenge for neural combinatorial optimization methods that learn heuristics from data.

    Source: §1 · p. 1

  • Method

    The paper derives a direct MDP for constructive COPs and uses bisimulation quotienting to reduce its state space, specializing the mapping for recursive problems.

    Source: §1 · p. 2, §3.2 · p. 4, §3.3 · p. 5

  • Results

    Across five COPs, the learned policies achieve new state-of-the-art results and generalize to much larger instances than seen in training without additional search.

    Source: §1 · p. 2, §7 · p. 9

  • Takeaways & Limitations

    For recursive COPs, the reduced MDP retains optimal policies that exactly solve the original problem while merging states that represent equivalent remaining subproblems.

    Source: §1 · p. 2, §7 · p. 9

    The direct MDP assumes final feasibility can be ensured through tractable conditions on partial solutions.

    Source: §2.2 · p. 3

Abstract

from arXiv · show

Despite the success of neural-based 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 Problems (COPs) as Markov Decision Processes (MDPs) that effectively leverages common symmetries of COPs to improve out-of-distribution robustness. Starting from a direct MDP formulation of a constructive method, we introduce a generic way to reduce the state space, based on Bisimulation Quotienting (BQ) in MDPs. Then, for COPs with a recursive nature, we specialize the bisimulation and show how the reduced state exploits the symmetries of these problems and facilitates MDP solving. Our approach is principled and we prove that an optimal policy for the proposed BQ-MDP actually solves the associated COPs. We illustrate our approach on five classical problems: the Euclidean and Asymmetric Traveling Salesman, Capacitated Vehicle Routing, Orienteering and Knapsack Problems. Furthermore, for each problem, we introduce a simple attention-based policy network for the BQ-MDPs, which we train by imitation of (near) optimal solutions of small instances from a single distribution. We obtain new state-of-the-art results for the five COPs on both synthetic and realistic benchmarks. Notably, in contrast to most existing neural approaches, our learned policies show excellent generalization performance to much larger instances than seen during training, without any additional search procedure.

1 Introduction

Neural combinatorial optimization learns heuristics from data, but out-of-distribution generalization remains challenging. The paper derives direct MDPs for constructive COPs, reduces their states through bisimulation quotienting, and reports state-of-the-art results with strong generalization across five problems.

1 Introduction

  • The framework derives a direct MDP for any COP with a user-defined solution space, using partial solutions as states and construction steps as actions.The authors prove that optimal policies of this MDP correspond exactly to optimal COP solutions.Source: §1 · p. 2
  • For recursive COPs, bisimulation maps partial solutions to their remaining subproblems, reducing the state space by merging states that induce the same instance.The paper says this exploits recursive symmetries rather than symmetries tied to Euclidean graphs.Source: §1 · p. 2
  • On five classical COPs, the learned policies achieve new state-of-the-art results and generalize to much larger instances, including instances above 200 nodes with a single greedy rollout.The paper also reports improved performance with beam search and faster execution with a slight performance drop using PerceiverIO.Source: §1 · p. 2

2 Combinatorial Optimization as a Markov Decision Problem

The paper models constructive COP solving as sequential decisions over partial solutions. It defines solution spaces to represent construction steps, then derives a direct MDP whose optimal policies correspond to optimal solutions.

2.1 Solution Space

  • A solution space is a monoid of partial solutions with a neutral element and a generating step set, where every element has finitely many step decompositions.The paper illustrates alternative representations with node sequences for TSP and item subsets for Knapsack.Source: §2.1 · p. 3

2.2 The Direct MDP

  • Solving a COP amounts to finding a sequence of construction steps that yields a feasible solution minimizing the objective.The paper proves that optimal policies of the direct MDP produce exactly the optimal solutions of the COP.Source: §2.1 · p. 3, §2.2 · pp. 3–4
  • A direct MDP represents partial solutions as states and construction steps or a neutral action as actions; its transitions are deterministic.The framework assumes final feasibility can be ensured through tractable conditions on partial solutions, avoiding dead-end states.Source: §2.2 · p. 3

3 Bisimulation Quotienting

The paper replaces partial-solution states with induced tail subproblems, merging states that share the same continuation problem. For tail-recursive COPs, this BQ-MDP preserves optimal solutions while representing the remaining subproblem as an instance of the original problem.

3.1 State information and symmetries

  • A partial solution can be viewed as transforming the original instance into its tail subproblem, so distinct instance–partial-solution pairs may share the same continuation state.For TSP, the remaining problem depends on the current endpoint and unvisited nodes, not the full sequence of visited nodes.Source: §3.1 · p. 4

3.2 Bisimulation Quotiented MDP

  • The BQ-MDP uses instances as states and maps each direct-MDP state to its induced tail subproblem, quotienting states related by this bisimulation.Action-reward sequences and trajectories are preserved, and the BQ-MDP's optimal policies yield exactly the COP's optimal solutions.Source: §3.2 · p. 4

3.3 Instance parametrization and recursion

  • The reduction applies to tail-recursive COPs, where each remaining tail subproblem can be represented in the same parametric space as the original instance.After each construction step, the instance is updated to encode the remaining problem; the paper notes that problems amenable to dynamic programming have this property.Source: §3.3 · p. 5
  • For Knapsack, the reduced instance subtracts selected-item weight from capacity and removes those items; path-TSP, path-CVRP, and path-OP are also tail-recursive.TSP is a path-TSP subproblem whose origin and destination coincide.Source: §3.3 · p. 5

4 Policy Learning

The policy is trained by imitation on trajectories derived from precomputed near-optimal solutions, using sub-sequences as examples of sub-instances. Its attention-based architecture predicts the next construction action directly, with a stated cubic rollout complexity that can be reduced using linear attention.

Neural architecture

  • For path-TSP, the model embeds node coordinates and uses learned origin and destination encodings instead of positional encodings, then predicts probabilities over allowed next nodes without an autoregressive decoder.For path-ATSP, it uses random node identifiers and incorporates the cost matrix through weighted graph convolutions.Source: §4 · pp. 5–6, Figure 2 · p. 6

Trajectory generation

  • Training uses imitation of trajectories extracted from precomputed near-optimal solutions for small, fixed-size instances.Sub-sequences become sub-instance examples with varying sizes and node distributions, which the authors say implicitly encourages generalization across them.Source: §4 · p. 6

Complexity

  • The policy has total complexity O(N^3) because self-attention is quadratic and is called at every construction step.Replacing the Transformer with linear-attention PerceiverIO significantly accelerates inference while retaining competitive performance.Source: §4 · p. 6

5 Related Work

Prior work includes general CO frameworks and neural constructive methods, but the paper positions its contribution as a structure-agnostic MDP formulation with a proof connecting optimal policies to COP solutions. It also contrasts its imitation-trained policy approach with methods that rely on search or adaptation for generalization.

Generic frameworks for CO

  • MIP and constraint programming are widespread CO frameworks, while prior generic MDP attempts focus on graph problems; this paper says its formulation assumes no graph or other COP structure.It also claims to be the first to prove equivalence between its MDPs and solving the COP.Source: §5 · p. 7

Neural-based constructive heuristics

  • Neural constructive methods include autoregressive policies trained by reinforcement learning and supervised methods that predict solution-segment heatmaps.The paper contrasts its imitation-trained policy with heatmap approaches that generally rely on sophisticated search to obtain high-quality solutions.Source: §5 · p. 7

Step-wise approaches

  • Step-wise approaches re-encode after subtour completion or node selection, and MDAM adds a layer to approximate re-embedding efficiently.The paper uses MDAM as a baseline.Source: §5 · p. 7

Generalizable NCO

  • Prior generalization strategies include adversarial training, meta-learning, and symmetry-based methods; the paper describes these as orthogonal to its MDP approach.The related work notes that Att-GCN+MCTS generalizes to large TSP instances but uses an expensive post-learning search strategy.Source: §5 · p. 7
  • Some hybrid routing methods use divide-and-conquer, learning to split large instances for external specialized solvers to solve.Source: §5 · p. 8

6 Experimental Evaluation

The evaluation compares models trained on size-100 synthetic instances against larger synthetic graphs and realistic libraries. The authors report strong generalization for their policy, including comparisons with end-to-end and hybrid methods, while also describing training and test conditions that qualify the results.

Hyperparameters and training

  • Training uses imitation of expert trajectories from a dataset of 1 million solutions, with a shared model setup across problems.The described model has 9 layers, 12 attention heads, embedding size 192, and is trained for 500 epochs.Source: §6 · p. 8

Baselines and test datasets

  • Models are tested on synthetic graphs of sizes 100, 200, 500, and 1,000, as well as TSPLib and CVRPLib instances.Training uses synthetic size-100 instances; tests also include TSPLib instances up to 4,461 nodes and CVRPLib instances with Euclidean coordinates.Source: §6 · p. 8
  • The evaluation compares against classical solvers, hybrid methods, and neural constructive policies, reporting optimality gap and inference time.For CVRP, LKH solutions are used as the optimality-gap reference for consistency with prior work, although HGS is reported to give better results than LKH.Source: §6 · p. 8

Results

  • Across Euclidean TSP, CVRP, OP, and asymmetric TSP, the model shows superior generalization on larger graphs even with greedy decoding; its only competitive models are TSP-only hybrids, 2 to 15 times slower.On TSPLib and VRPLib instances, it significantly outperforms end-to-end baseline policies even with greedy decoding.Source: §6 · pp. 8–9

7 Conclusion

The framework derives direct MDPs for constructive COPs and quotient MDPs for recursive problems, reducing state space while preserving optimal solutions. Its policy generalizes particularly well and significantly outperforms neural constructive solvers and learning-plus-search methods.

7 Conclusion

  • The resulting policy generalizes particularly well and significantly outperforms neural constructive solvers and learning-plus-search methods.Table 1 compares BQ models with classic and neural baselines; Table 2 reports results on TSPLib and CVRPLib.Source: §7 · p. 9, Table 1 · p. 10, Table 2 · p. 10
  • For recursive COPs, bisimulation quotienting reduces the state space while preserving optimal policies that exactly solve the original problem.The framework also derives a direct MDP for constructive COPs, whose optimal policies correspond exactly to optimal COP solutions.Source: §7 · p. 9

A Application to the Capacitated Vehicle Routing Problem

  • CVRP is handled through path-CVRP, whose tail subproblem updates the origin and remaining capacity after each selected node.Selecting a customer subtracts its demand; selecting the depot resets capacity to full, provided the resulting capacity is nonnegative.Source: A Application to the Capacitated… · p. 15
  • The CVRP BQ state is the induced path-CVRP instance, with the origin moved to the partial route's endpoint and capacity reduced by demand served since the depot.The example's remaining capacity is full capacity 12 minus demands 3+2+4+1.Source: A Application to the Capacitated… · p. 15

B Application to the Orienteering Problem

  • For OP, each selected node updates the origin and reduces the remaining distance budget, and construction ends when that budget is exceeded.Unlike TSP and CVRP, OP's number of construction steps is not known in advance.Source: B Application to the Orienteering… · p. 16

C Application to the Knapsack Problem

The knapsack application maps partial solutions to residual instances and uses a closely related model architecture. It achieves stronger overall performance than POMO and significantly better performance on specified out-of-distribution datasets.

C Application to the Knapsack Problem

  • The KP bisimulation removes picked items and subtracts their total weight from the remaining capacity.The model takes item values, weights, and remaining capacity as input, and masks items too heavy for the remaining capacity.Source: C Application to the Knapsack Problem · pp. 16–17
  • At each construction step, any item in the ground-truth solution is a valid choice, so training uses multi-class cross-entropy.Source: C Application to the Knapsack Problem · p. 17
  • The model achieves better overall performance than POMO and significantly better performance on size-1000 and capacity-10 out-of-distribution datasets.POMO builds N solutions per instance and selects the best, while this model generates one solution per instance.Source: C Application to the Knapsack Problem · p. 17, Table 3 · p. 17

D Impact of k-nearest-neighbor heuristic on model performance

  • Restricting inference to nearest neighbors reduces execution time and sometimes improves optimality gap; for KP, candidates can instead be ranked by value or value-to-weight ratio.Table 4 reports experiments using different neighbor counts during inference.Source: D Impact of k-nearest-neighbor… · p. 17

E.1 PerceiverIO architecture

The model's repeated attention computations yield O(N^3) total complexity, which may limit use on large graphs. PerceiverIO shifts computations to a latent space to reduce input-length complexity to linear.

E.1 PerceiverIO architecture

  • Repeated policy calls require N steps with N^2 attention matrices per step, giving O(N^3) total complexity that may limit application to large graphs.Source: §E.1 · p. 17
  • Restricting inference to different numbers of nearest neighbors reduces execution time and can sometimes improve optimality gap.Table 4 compares inference results at different neighbor counts.Source: Table 4 · p. 18
  • PerceiverIO replaces standard attention with input-to-latent cross-attention and latent self-attention, making operations linear rather than quadratic in input length.The implementation uses a 64×48 latent space, nine attention layers, eight heads, and embedding size 192.Source: §E.1 · p. 18

E.2 Approximated model

The paper tests a faster approximation that recomputes only top model layers, and finds that preprocessing expert trajectories can substantially improve CVRP performance.

E.2 Approximated model

  • The approximated model runs 1.6 times faster but raises TSP100 optimality gap to 8.175%, versus 0.35% for the original model.The approximation fixes bottom layers and recomputes only the top layer with visited-node masking and updated origin and destination tokens.Source: §E.2 · p. 18

E.3 On the impact of expert trajectories

  • Sorting CVRP expert subtours by remaining vehicle capacity yields an almost twofold performance improvement over arbitrary subtour order.The first subtour has the smallest remaining capacity, usually zero, and the last has the largest.Source: §E.3 · p. 18

F Proofs

The proofs establish that the direct MDP has well-behaved trajectories, that its optimal policies solve the associated COP, and that the reduced MDP is a bisimulation quotient. They also provide the monoid and bisimulation foundations used by the construction.

F.1 Properties of the direct MDP

  • The direct MDP has finitely many allowed actions per state, no dead ends, and only finitely many non-null actions in any trajectory.The proofs use the finite solution space and finite step decompositions to establish these properties.Source: §F.1 · p. 19

F.2 Soundness of the direct MDP

  • A direct-MDP trajectory’s optimal outcome is an optimal COP solution, because total reward is the negative objective value of its outcome.The proof derives this from the transition rewards and the surjective mapping from trajectories to solutions.Source: §F.2 · p. 20

F.3 Bisimulation between the direct MDP and the BQ-MDP

  • The reduced MDP is isomorphic to the quotient of the disjoint union of direct MDPs by their bisimulation mappings.The mappings commute with transitions, preserve rewards, and agree on which step actions are allowed.Source: §F.3 · pp. 20–21

G.1 Monoids

  • A monoid combines an associative operation with an identity; finite sequences under concatenation and the empty sequence provide an example.The sequence-to-product mapping is independent of parenthesization.Source: §G.1 · p. 21

G.2 Bisimulation

  • Bisimulation supports quotienting states into equivalence classes, and a surjective bisimulation yields a quotient isomorphic to the target transition system.Bisimulation also persists under transitive closure, with quotienting and transitive closure commuting.Source: §G.2 · pp. 22–24

H Plots of some TSPLib and CVRPLib solutions

The plots compare the model’s solutions with optimal or best-known solutions and report opt_gap values for the model and two baselines. The examples cover four plotted instances.

H Plots of some TSPLib and CVRPLib solutions

Related papers

Loading 2301.03313v3…