# BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization

arXiv: https://arxiv.org/abs/2301.03313 · HTML: https://mlsanity.com/paper/2301.03313/

## Key facts

- Cited by 82 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 56 references that are in the map.
- First posted on arXiv 9 Jan 2023.

## Builds on (most cited first, 30 of 32)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Perceiver IO: A General Architecture for Structured Inputs & Outputs](https://mlsanity.com/paper/2107.14795/) (2021)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [POMO: Policy Optimization with Multiple Optima for Reinforcement Learning](https://mlsanity.com/paper/2010.16011/) (2020)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [ReZero is All You Need: Fast Convergence at Large Depth](https://mlsanity.com/paper/2003.04887/) (2020)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances](https://mlsanity.com/paper/2012.10658/) (2020)
- [Goal-Conditioned Reinforcement Learning: Problems and Solutions](https://mlsanity.com/paper/2201.08299/) (2022)
- [Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning](https://mlsanity.com/paper/2010.12367/) (2020)
- [DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems](https://mlsanity.com/paper/2210.04123/) (2022)
- [Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhood](https://mlsanity.com/paper/2012.10384/) (2020)
- [Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization](https://mlsanity.com/paper/2205.13209/) (2022)
- [Learning to Delegate for Large-scale Vehicle Routing](https://mlsanity.com/paper/2107.04139/) (2021)
- [Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problems](https://mlsanity.com/paper/2012.10638/) (2020)
- [Learning the Travelling Salesperson Problem Requires Rethinking Generalization](https://mlsanity.com/paper/2006.07054/) (2020)
- [Simulation-guided Beam Search for Neural Combinatorial Optimization](https://mlsanity.com/paper/2207.06190/) (2022)
- [Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization](https://mlsanity.com/paper/2006.01610/) (2020)
- [The Transformer Network for the Traveling Salesman Problem](https://mlsanity.com/paper/2103.03012/) (2021)
- [Learning Generalized Reactive Policies using Deep Neural Networks](https://mlsanity.com/paper/1708.07280/) (2017)
- [Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time](https://mlsanity.com/paper/2006.03750/) (2020)
- [Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness](https://mlsanity.com/paper/2110.10942/) (2021)
- [A Deep Reinforcement Learning Algorithm Using Dynamic Attention Model for Vehicle Routing Problems](https://mlsanity.com/paper/2002.03282/) (2020)

## Built on by (most cited first, 30 of 82)

- [ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution](https://mlsanity.com/paper/2402.01145/) (2024)
- [HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs](https://mlsanity.com/paper/2412.14995/) (2024)
- [RouteFinder: Towards Foundation Models for Vehicle Routing Problems](https://mlsanity.com/paper/2406.15007/) (2024)
- [Ant Colony Sampling with GFlowNets for Combinatorial Optimization](https://mlsanity.com/paper/2403.07041/) (2024)
- [GOAL: A Generalist Combinatorial Optimization Agent Learner](https://mlsanity.com/paper/2406.15079/) (2024)
- [Rethinking Light Decoder-based Solvers for Vehicle Routing Problems](https://mlsanity.com/paper/2503.00753/) (2025)
- [PolyNet: Learning Diverse Solution Strategies for Neural Combinatorial Optimization](https://mlsanity.com/paper/2402.14048/) (2024)
- [Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvement](https://mlsanity.com/paper/2403.15180/) (2024)
- [Self-Improved Learning for Scalable Neural Combinatorial Optimization](https://mlsanity.com/paper/2403.19561/) (2024)
- [Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives](https://mlsanity.com/paper/2406.00415/) (2024)
- [DPN: Decoupling Partition and Navigation for Neural Solvers of Min-max Vehicle Routing Problems](https://mlsanity.com/paper/2405.17272/) (2024)
- [Destroy and Repair Using Hyper Graphs for Routing](https://mlsanity.com/paper/2502.16170/) (2025)
- [Learning to Reduce Search Space for Generalizable Neural Routing Solver](https://mlsanity.com/paper/2503.03137/) (2025)
- [BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization](https://mlsanity.com/paper/2503.07580/) (2025)
- [MTL-KD: Multi-Task Learning Via Knowledge Distillation for Generalizable Neural Vehicle Routing Solver](https://mlsanity.com/paper/2506.02935/) (2025)
- [Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning](https://mlsanity.com/paper/2506.02392/) (2025)
- [DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problems](https://mlsanity.com/paper/2406.19705/) (2024)
- [Preference Optimization for Combinatorial Optimization Problems](https://mlsanity.com/paper/2505.08735/) (2025)
- [Learning to Insert for Constructive Neural Vehicle Routing Solver](https://mlsanity.com/paper/2505.13904/) (2025)
- [Instance-Conditioned Adaptation for Large-scale Generalization of Neural Routing Solver](https://mlsanity.com/paper/2405.01906/) (2024)
- [Collaboration! Towards Robust Neural Methods for Routing Problems](https://mlsanity.com/paper/2410.04968/) (2024)
- [An Efficient Diffusion-based Non-Autoregressive Solver for Traveling Salesman Problem](https://mlsanity.com/paper/2501.13767/) (2025)
- [GREAT: A Graph Edge Attention Network for the Electric Vehicle Routing Problem with Asymmetric Costs](https://mlsanity.com/paper/2408.16717/) (2024)
- [Rethinking Neural Combinatorial Optimization for Vehicle Routing Problems with Different Constraint Tightness Degrees](https://mlsanity.com/paper/2505.24627/) (2025)
- [URS: A Unified Neural Routing Solver for Cross-Problem Zero-Shot Generalization](https://mlsanity.com/paper/2509.23413/) (2025)
- [RADAR: Learning to Route with Asymmetry-aware DistAnce Representations](https://mlsanity.com/paper/2603.03388/) (2026)
- [PARCO: Parallel AutoRegressive Models for Multi-Agent Combinatorial Optimization](https://mlsanity.com/paper/2409.03811/) (2024)
- [Learning for routing: A guided review of recent developments and future directions](https://mlsanity.com/paper/2507.00218/) (2025)
- [VRPAgent: LLM-Driven Discovery of Heuristic Operators for Vehicle Routing Problems](https://mlsanity.com/paper/2510.07073/) (2025)
- [Multi-Task Vehicle Routing Solver via Mixture of Specialized Experts under State-Decomposable MDP](https://mlsanity.com/paper/2510.21453/) (2025)

## Abstract (arXiv)

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.