BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization

Author name not available (Why is that?)

Publication date: 9 January 2023

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.

Has companion code repository: https://github.com/naver/bq-nco

This page was built for publication: BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6422911)