BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization
Authors: Darko Drakulic
Sofia Michel
Florian Mai
Arnaud Sors
Jean-Marc Andreoli
Venue: NeurIPS 2023 poster (2023)
Keywords: Combinatorial Optimization
Markov Decision Processes
Bisimulation
Policy Learning
Out-of-Distribution Generalization
Routing Problems
TSP
CVRP
KP.
TL;DR: A novel framework to cast CO problems as equivalent MDPs and a principled way to get more efficient MDPs for a widespread class of CO problems. State-of-the-art generalization results on three classical problems.

Abstract: 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. Our code is available at: [link](https://github.com/naver/bq-nco).

BQ-NCO: Bisimulation Quotienting for Efficient Neural Combinatorial Optimization
Darko Drakulic, Sofia Michel, Florian Mai; Arnaud Sors, Jean-Mare Andreoli
Naver Labs Europe
firstname. Jastname@naverlalle com
Abstract
Despite the success of neural-based combinatorial optimization methods for end-to- end heuristic learning, out-of-distribution generalization remains a challenge. this paper, present novel formulation of Combinatorial Optimization Problems (COPs) as Markov Decision Processes (MDPs) that effectively leverages common symmetries of COPs improve diiitii-iitiiittoonn robustness. Starting from direct MDP formulation of 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 simple attention -based policy network for the BQ- MDPs, which we train by imitation of (near) optimal solutions of small instances from single distribution. We obtain new state-of-the-art results for the five COPs on both synthetic and realistic benchmarks. Notably, 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. Our code is available at: url
Introduction
Combinatorial Optimization Problems (COPs) are crucial in many application domains such as transportation, energy, logistics, etc. Because they are generally NP-hard [[2], their resolution at real-life scales is mainly done by problem-specific heuristics, which heavily rely expert knowledge. Neural combinatorial optimization (NCO) is relatively recent line of research that focuses on using deep neural networks to learn such heuristics from data, possibly exploiting regularities in problem instances of interest [.. Among NCO methods, the so-called constructive approaches view the process of building solution incrementally naturally be modeled with Markov Decision Processes (MDPs). Although many previous works have successfully used this strategy, the process of formulating appropriate MDP (esp. the state and action spaces) is usually specific to each problem (e.g. (2 for routing problems, (49) for jobshop scheduling and (20) for bin packing). These design choices have considerable impact when solving the MDP. In particular, exploiting the COP's symmetries can boost the efficiency and generalization
sequential decision making problem, which can
of neural solvers (c.g. 229 24
leverage the symmetries of routing problems in Euclidean graphs).
In this paper, we present generic and principled framework cast any COP as an MDP and then way to account for common COPs' symmetries to design more efficient MDP. More precisely,
IDIAP Research Institute, Work done during an intersship at Naver Labs Europe
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

given user-defined solution space, we show how to automatically derive a direct MDP, where the states are partial solutions and the actions are the construction steps. While the application of this framework to some COPs encompasses some previously proposed MDPs (e.g [28). for routing problems), to the best of our knowledge, we are the first to provide a way to derive an MDP for any COP and prove the equivalence between the optimal MDP policies and solving the COP.
Next, noting the limitations of using the partial solutions as states, we introduce a generic bisimulation mapping that allows to reduce the state space. In particular, we show that for problems that satisfy a recursion property, the bisimulation simply maps a partial solution to a new (induced) instance, which corresponds to the remaining subproblem when the partial solution is fixed. As many partial solutions can induce the same instance, the resulting bisimulation quotiented (BQ-)MDP has a significantly smaller state space. Also, it enables more efficient learning by avoiding to independently learn the policy at states which are equivalent for the COP at hand. In contrast to previous works ([29 24 ) the
symmetries that we exploit are not linked to the Euclidean nature of the graphs but to the recursive property of the problems, which is very common in CO as includes the Optimality Principle of Dynamic Programming [3] 6].
We illustrate our framework on five well-known COPs: the Euclidean and Asymmetric Traveling Salesman Problems (TSP, ATSP), the Capacitated Vehicle Routing Problem (CVRP), the Orienteering Problem (OP) and the Knapsack Problem (KP). Furthermore, we propose a simple transformer- based architecture [43 for these problems. well-suited to the BQ-MDPs, and requiring only minor variations work for the five problems. For each problem, we train our policy by imitation of expert trajectories derived from (near) optimal solutions of small instances sampled from a single distribution. We test on both synthetic and realistic benchmarks of varying size and node distributions. Our model provides new state-of-the
results on the five problems and exhibits excellent out- of-distribution generalization, especially to larger instances, a well-recognized challenge for NCO Notably with single greedy rollout, our learned policies outperform state-of-the- art end-to-end learning-based approaches for instances with more than 200 nodes. We show that we can further improve the performance with a beam-search (using more computation) while we can significantly speed-up the execution (at the cost of a slight performance drop) by replacing the quadratic transformer model by linear attention- based model, the PerceiverlO [19].
methods 22 (2).
In summary, our contributions are as follows: 1) We present generic and principled framework to derive a direct MDP given any COP with minimal requirements; 2) We propose method to reduce the direct MDPs via symmetry-focuser focusee bisimulation quotienting and define an explicit bisimulation for the class of recursive COPs; 3) We design adequate transformer-bast MDPs, with only minor adaptations to work for the TSP (both Euclidean and asymmetric versions), CVRP, OP and KP: 4) We achieve state-of-the-art generalization performance on these five problems, significantly our-perrorinng other neural-based constructive methods.
architecture for the BQ-
2 Combinatorial Optimization as a Markoy Decision Problem
In this section, we propose a generic framework to represent any Combinatorial Optimization Problem (COP) as a Markov Decision Process (MDP) amenable to standard Machine Learning techniques. We denote a COP instance by:
min f(x), 2EX
where X is the finite, non-empty set of feasible solutions, while the objective f is a real-valued function whose domain contains X. The complexity of CO is due to the cardinality of X, which, although finite, is generally exponential in the problem size. Constructive approaches to CO build solution sequentially by growing a partial solution at each step. A required assumption of constructive heuristies (although often left implicit) is that the feasibility of the final solution can be ensured through tractable conditions on the partial solutions at each step of the construction process.
2.1 Solution Space
Let us denote by X' the set of all possible partial solutions which can be obtained by a given construction procedure. We assume that X is equipped with an operation having a neutral element 6. Informally, is the "emptt" partial solution and if xr, y are partial solutions, then zoy denotes the result of applying the sequence of construction steps yielding æ followed by that yielding y. We
2

---

denote by ZcX' the subset of partial solutions obtained from e by just one construction step. By identification, we call the elements of 2 steps and assume that any partial (a fortiori feasible) solution can be obtained as the composition of sequence of steps. We can now define the structure of the solution space as required by our framework.
Definition 1 (Solution Space), A solution space is tuple (X, o, 6, 2) where (X, D, 6) forms a monoid (see Appendix G. for background), and the step set [c) is a generator of X, such that any element of X has a finite positive number of step decompositions:
Vx E X, 0 < 1121m E 2": =1=2000 2n <00.
(1)
Thus, solving a COP instance (f) given solution space X' containing X amounts to finding a sequence of steps 21:m such that 210 .2. arg m f(x), task which can naturally be modeled as an MDP, as shown below.
Examples of Solution Spaces. We provide examples of solution spaces for two classical COPs. In the Euclidean Traveling Salesman Problem (TSP), an instance is defined by a set of nodes (including depot) associated with points in Euclidean space and the goal is find the shortest tour that starts and ends at the depot and visits each other node exactly once. A partial solution for the TSP can be represented by a sequence of nodes. Therefore we can define XISP as the set of finite sequences of nodes. In the Knapsack Problem (KP), an instance is defined by a set of items associated with weight and value features, and the goal is to select subset of these items such that the sum of their weights does not exceed a given capacity while their cumulated value is maximized. We can define Nkp as the set of finite sets of items. For TSP (resp. KP), the operator o sequence concatenation (resp. set disjoint union), the neutral element is the empty sequence (resp. set) and step is a sequence (resp. set) of length 1. Note that these problems admit other (e.g. graph- based rather than set or sequence-based) solution spaces. In fact, solution space is not intrinsic to problem, nor vice-versa.
2.2 The Direct MDP
Given a solution space o, 2), we consider the set Fx of instances Xf: where the set of feasible solutions X a finite, non-empty subset of X, and the objective function fEE is defined on X' rather than just X, i.e. it is well-defined for any partial solution. Now, given an instance X)x we can derive its direct MDP, denoted M(f.x). as follows. Its state space is the set X Byyx roye of partial solutions which can potentially be expanded into a feasible one. Its action space is Z i.e. an action is either a step or the neutral action. Its transitions are deterministic, and can be represented as a labeled transition system with the following two rules, where the label of each transition consists of its action-reward pair, placed respectively above and below the transition arrow:
σ ((ooa) 2or if zoz E X
and
I 1
Here, x is a state and 2 is step. The condition in each rule determines whether the action is allowed. Thanks to the structure of the solution space captured by Def. the direct MDP of an instance (J, has three key properties, proved in Appendix F.1 (1) From any state, the number of allowed actions is finite (even if 2 is infinite), therefore M(r.x) belongs to the simpler class of discrete-action MDPs. (2) From any state, there is always at least one allowed action (i.e. there are no dead-end states). This assumes that one can guarantee if a partial solution can be expanded into feasible one, as required of the valid states in X. This is a common assumption of constructive heuristics (often left implicit) and it avoids the complications associated with dead ends in MDPs [27]. (3) In any infinite trajectory in Mrr.x), the number of transitions involving step action is finite, while all the other transitions involve the neutral action. Since the neutral action yields a null reward, this means that the return of a trajectory is well defined, without having to discount the rewards. Also, if 1 is the (infinite) sequence of actions of the trajectory, since all but finitely many of them are neutral actions, their composition a oa2o-.. is well defined and is called the outcome of the trajectory. We can now establish the main result of this section, proved in Appendix F2
Proposition 1 (Soundness of the Direct MDP). Given a solution space X and an instance (f, X)EFx, let Mif.x) x be its direct MDP. The set arg minzex I f(x) is exactly the set of x such that there exists an optimal policy x for M(J.x) where is the outcome of a trajectory starting at e under policy
3

---

This result states the exact correspondence between the optimal solutions of a COP instance and the optimal policies of its direct MDP. Thus, the vast corpus of techniques developed search for optimal policies in MDPs in general is applicable to solving COPs. The direct MDP encompasses many previously proposed MDPs, where the state is a partial solution and each action consists of adding an element to the partial solution, e.g. 23 for graph problems and [ for the TSP.
3
Bisimulation Quotienting
3.1 State information and symmetries
Let o,,, 2) be solution space and M(r.x the direct MDP of an instance X)Fxx In trajectory of MMI..)) observe that each non neutral action z "grows" the state from x to roz, as defined by (2). For many COPs, this is counter-intuitive, because it implies that the state information increases while the number of allowed actions generally decreases. For example, in the TSP, the state contains the sequence of visited nodes, which grows at each step, while the allowed actions the set of unvisited nodes, which shrinks at each step. At the end, the state may carry the most information (a full- -rlwn feasible solution). but it is not used in any decision, since there is single allowed action anyway (the neutral action). To address this mismatch between the information carried by the state and the complexity of the decision it supports, the information needed for the continuation of the construction process. To do so, we observe that a partial solution yEX' can be seen both as an operator on partial solutions w->ro which grows its operand, or, alternatively, as the following operator on instances, which reduces its operand:
seek to define
state which captures only
(f,x)~ U, X v)
with: (f+ flyo x) and x+ fxlyoz
In fact, (f+y. Xxy) is the so-called the tail subproblem (6 of instance (f. after partial solution y has been constructed. We observe that for a given tail subproblem X'),x) there can be many pairs of an instance (f, xxxxxx and partial solution x such that (f*2, Xx=) X'). For example in the TSP, the tail subproblem consists of finding the shortest path from the last node e of the partial solution back to the depot of the instance, which visits the set I of not-yet- vissttdd nodes. Therefore we can see that any TSP instance with the same depot o and any node sequence ending at e with not-yet-visited nodes will lead the same tail subproblem. This is strong symmelry with respect to the MDP policy: intuitively it means that an optimal policy should produce the same action for these infinitely many (instance-parti partial solution) pairs. Treating them as distinct states, as in the direct MDP, forces a training procedure to learn the underlying symmetry in order to map them into a common representation.
3.2 Bisimulation Quotiented MDP
In order to leverage the above "reduction operator" view and its potential symmetry, we define the following "reduced" MDP .M. Its state space is the set Fx of instances. Its action space is Z as in the direct MDP. Its transitions are also deterministic, and can be expressed with two rules, dual of those in (2)
Xf, f(e) (f 22 x x if x* and - (f.X) ex
(3)
This MDP is defined at the level of the whole solution space rather than an individual instance. Now, the mapping 1 xxxxx:FFFxx from the direct to the reduced states defined by & (z) X+x)
for all xxX is a bisimulation between M(r,x) and M (background Appendix G.2 and a proof in Appendix F33 Formally, M is isomorphic to the quotient of the direct MDP by the bisimulation (precise statement and proof in Appendix FF3), hence is called the Bisimulation Quotiented (BQ-)MD) By the bisimulation property, for any direct state x, the action-reward sequences spawned from r in M(f.x) and from (f (z) in M are identical. Therefore, there is a one-to-one correspondence between the trajectories of M(r.x) starting at e and those of M starting at ().x)(t==(())) X). Hence, the analogue of Prop. P holds for the BQ-MDP:
Proposition 2 (Soundness of the BQ-MDP). Let M be the BQ-MDP of solution space X, and ()x))Fx an instance. The set arg minzex x I ((x) is exactly the set of x. such that there exists an optimal policy x for M where is the outcome of trajectory starting at (f.X) under policy

---

Impact on model architecture. Although both the direct and BQ-MDPs are equivalent in terms of solving their associated COP, their practical interpretation leads to major differences. In the direct MDP view, it would not make sense to learn each instance-specifie MDP separately. Instead generic MDP conditioned on an input instance learnt, similar to goal-conditioned Reinforcement Learning 40 [3] (the goal is here the input instance). A typical policy model architecture consists of an encoder in charge of computing an embedding of the input instance and a decoder that takes the instance embedding and the current partial solution to compute the next action (Fig. [[eft), e.g. the Attention Model [28] or PointerNetworks [45]. In the rollout of a trajectory, the encoder needs only be invoked once since the instance does not change throughout the rollout. For the BQ-MDP, only one, unconditional MDP is learnt for the whole solution space. The model can be simpler since the distinction between encoder and decoder vanishes (Fig. right). On the other hand, the whole model must be applied to a new input instance at each step of a rollout.
X)
agent
encoder
agent
(f-1)
model
24
2t-1
decoder
+
4
Xf,X)
ft fi- * 2x
X1 Xe-1 * 21
3t
Ft
2
environment
environment
Figure I: Policy model architectures for the direct MDP (left) and BQ-MDP (right).
3.3 Instance parametrization and recursion
For a given COP, instances are generally described by set of parameters, which are used as input to the policy network. In the BQ-MDP, the instance is updated at each step 2, according to the equations X'=X*z and f== In order to implement the BQ-MDP, a key requirement is that (f", X') can be represented in the same parametric space as (f,X), X). In fact, this is the case for COPs that satisfy the tail-recursion property: after applying number of construction steps to an instance, the remaining tail subproblem itself an instance of the original COP. This is very common property in CO and includes in particular the Optimality Principle of Dynamic Programming (3 [ all problems that are amenable dynamic programming satisfy the tail-recursion property. For these tail-recursive COPs, the bisimulation simply maps a partial solution to the tail subproblem instance it induces.
Application to the KP and path-TSP. One can see that the KP naturally satisfies the tail-recursion property. Consider an instance of the KP with capacity e and items (w;, V,)ier described by their weight w, and value v;. A partial solution is subset JC7 of items. In this case, the bisimulation + maps J to a new KP instance with capacity e- Σje, My and item set (wi, w))eer) (see Appendix C). For the TSP, we introduce a slightly more general problem, path-TSP, where the goal is to find shortest path between origin and destination node visiting set of customer nodes, instead of tour. The tail subproblem for a partial path Tisk consists of finding the shortest path from 23 to the destination that visits all the remaining nodes, hence it is also path-TSP instance. Thus pat tail-recursive, and TSP is simply a sub-problem of path-TSSP where origin and destination are associated with the same Fuclidean point (the depot). A similar reasoning holds for CVRP and OP, leading to path-CVRP and path-OP (see in Appendix and B
4 Policy Learning
We now describe our proposed transformer- policy network for the BQ-MDPs. For simplicity, we focus here on the PSt--TSP: the models for path-CV Path-OP and KP differ only slightly and are presented in Appendix A
B and
Neural architecture. For the Euclidean pSth-TSP (Fig. (Fig-[]eftt [[left), the Cartesian coordinates of each node (including origin and destination) are embedded via a linear layer. The remainder of the model is
based on Vaswani et al. 43 with the following differences. First, we do not use positional encoding since the input nodes have no order. Instead, learnable origin (resp. destination) encoding vector is added to the feature embedding of the origin (resp. destination) node. Second, we use ReZero j
5

---

sotimas
bnear hovr
linere laver
Transormer layer
Transformer layer
Sclivation-&LLu BormllizasooRReZZe
LX
Relivation-Rel.a
LX
Graph convolation layer
0kig.
dest.
neights-soomiilzdd travel cast between uodes
Inpui embeeding layer
ofig.
dest.
enc.
enc.
inpui embeooling layer
(re: you
(#d) su)
(#1.91) 91
(Frcc Vv
Node fcotures: Curtesian coordinates
Node feature: rundom identiierr
Figure 2: BQ-MDP policy model architecture for the TSP (left) and ATSP (right); origin in yellow, destination red and the other nodes in blue.
normalization, which leads to more stable training and better performance in our experiments. Finally, a linear layer projects the output of the last attention block into a vector of size N, from which unfeasible actions, corresponding to the origin and destination nodes, are masked out, before applying a softmax operator so as to interpret the scalar node values for all allowed nodes as action probabilities. Note the absence of autoregressive decoder layers. In the asymmetric TSP, node coordinates given, but the travelling cost between nodes is provided through a (possibly asymmetric) matrix. The policy model for path-ATSP (Fig. right) differs slightly from that for path-TSP. Initially, a randomly generated identifier is assigned to each node, which is embedded by a linear layer. The cost matrix is then incorporated by using a weighted graph convolution operation in each layer of the model before applying the attention mechanism. The edge weights of the graph are obtained by some standard normalization of the cost matrix. The use of random node identifiers model input is justified in ATSP by the absence of node specific features. In problems where such features are available, a random identifier can still be added as extra node feature, as that often improves performance.
not
Trajectory generation. We train our model by imitation of expert trajectories, using a cross-entropy loss. Such trajectories are extracted from pre-computed (near) optimal solutions for instances of a relatively small and fixed size. Even for hard problems, we leverage the fact that it is generally possible to efficiently solve small instances (e.g. using MILP solvers). Of course the quality of the learned policy will be assessed on larger and therefore more challenging instances. Note that optimal solutions
directly in the form of trajectories, i.e. sequences of construction steps. While Prop. 2 guarantees that a trajectory exists for any solution, it is usually not unique. In the TSP, an optimal tour corresponds to two possible trajectories (one being the reverse of the other). In the CVRP, each subtour similarly corresponds to two possible trajectories, and in addition, the different orders of the subtours lead different trajectories. We noticed that this final order has an impact on the performance (see Appendix E.3). On the other hand, any sub-sequence from a fixed trajectory solution can be interpreted as the solution of sub-instance. Note that these sub-instances will vary both in size and node distribution, therefore by training on them, we implicitly encourage the model to work well across sizes and node distributions, and generalize better than if such variations were not seen during the training.
Complexity. Because of the quadratic complexity of self-attention, and the fact that call our policy at each construction step, the total complexity of our model, for an instance of size N, is ) whereas closely related wransformer-based models such as the TransformerTSP 77] and the Attention Model (28) have total complexity of O(N2). We experimentally show in Sec. 6 that our model still provides better-quality solutions faster than these baselines. This is because most neural models are called many times per instance in practice. typically for sampling from the learned policy or within a beam search. In contrast, we observe that doing a single rollout of our policy yields excellent results. Intuitively, given the complexity (Nr-hardn of the targeted COPs. it makes sense to spend as much computation as possible at each time step, provided the whole rollout is fast enough. On the other hand, the quadratic attention bottleneck can be addressed by using some linear attention models. In our experiments, we show that replacing the Transformer by the linear PerceiverlO [19 significantly accelerates inference while still providing competitive performance.

---

5 Related Work
Generic frameworks for CO. Generic frameworks have been crucial in the development and adoption of CO since they allow to formulate a COP in certain format and then give it as an input to a (black box) solver. Among the most widespread frameworks are Mixed-Integer Programming [[]] and Constraint Programming [39] On the other hand, Markov Decision Processes are powerful and ubiquitous tool to model sequential decision making problems and make them amenable to Machine Learning. While using MDPs to solve CO is not new, there are very few attempts to make it general framework. Khalil et al. 2 makes a first attempt to define a generic MDP for greedy heuristics on graph problems. Drori et al. [3] also focuses graph problems and provides flexible and efficient GNN based architecture to train with Reinforcement Learning (RL). Unlike these methods, our approach does not assume graph or any structure the COPs to define the (direct and BQ) MDP and we are the first to prove the equivalence between our proposed MDPs and solving the COP.
Neural- based constructive heuristics. Many NCO approaches construct solutions sequentially, via auto- rego-ssgeeee models. Starting with the seminal work by Vinyals et al. [45, which proposed the Pointer network trained in supervised way, Bello et al. [4] trained the same model by RL for the TSP and Nazari et al. (34) adapted it for the CVRP. Kool et al. (28] introduced an Attention- encoder- decoder Model (AM) trained with RL to solve several routing problems. This architecture was reused, with a few extensions, in POMO [29 and further combined with efficient search procedures in [IO]. TransformerTSP 77 uses similar architecture with different decoder for the TSP. While most of these auto-regressive constructive approaches used RL, another line of work focuses on learning, in supervised way, heatmap of solution segments: Nowak et al. 33 trained Graph Neural Network to output an adjacency matrix, which is converted into a feasible solution using beam search; Joshi et al. [21] followed similar framework and trained Graph Convolutional Network instead, that was used by [14 as well. Recently Sun and Yang 442 proposed DIFUSCO, a graph-based diffusion model output the heatmap. Although such non-autoregressive methods are promising for large instances since they avoid the sequential decoding, they generally rely on sophisticated search methods (such as Monte Carlo Tree Search) in order to get high-quality solution from the heatmap. Our paper explores the less common combination of supervised (imitation) learning to train a policy (not a heatmap) and achieves excellent performance without any search. In the context of planning, a similar strategy was successfully used in [16] to learn generalized reactive policies on small planning problems instances while generalizing well to larger ones.
based
Step-wise approaches. Instead of encoding an instance once and decoding sequentially as in the AM (28). Peng et al. (36] proposed update the encoding after each subtour completion for CVRP while Xin et al. [7 updated it after each node selection in TSP. Xin et al. [46] extended on this
idea by introducing the Multi-Decoder Attention Model (MDAM) which contains special layer
to efficiently approximate the re-embedding process Since MDAM constitutes the most advanced version, we employ it as a baseline in our experiments.
Generalizable NCO. Generalization to different instance distributions, and csp. larger instances, is regarded one of the major challenges for current NCO approaches [22 33 Fu et al. [4 trained Graph Convolution model in a supervised manner on small graphs and used it to solve large TSP instances, by applying the model sampled subgraphs and using expensive MCTS search to improve the final solution (At-GCN+MCTS) While this method achieves excellent generalization on TSP instances, MCTS requires lot of computing resources and is essentially a post-learning search strategy. Geisler et al. 15 investigate the robustness of NCO solvers through adversarial attacks and find that existing neural solvers are highly non-robust that one way to address this issue is through adversarial training. In particular, Xin et al.
out-of-distribution examples and conclude
[48) trains a
GAN to generate instances that are difficult to solve for the current model. Manchanda et al. [32 Son et al. (41), Zhou et al. (50) take different approach and leverage meta-learning to learn model that easily adaptable to new distributions. In DIMES, Qiu et al. 38 combines meta-learning with a continuous parametrization of the candidate solutions that allows to solve turge-scale TSP instances. Accounting for symmetries in a given COP a powerful idea to boost the generalization performance of neural solvers. For example, for problems on Euclidean graphs, Sym-NCO 24 make use of solution symmetries, to enforce robust representations while (29 exploits it as part of their loss function during training and at inference time to augment the set of solutions. Note that the above adversarial or meta-learning strategies and data augmentation are orthogonal to our approach of providing an efficient MDP which has beneficial effects irrespective of the training method. Finally,
7

---

some hybrid methods have been successful in solving large-scale routing problems [30 51 [8]; these ate based on the divide-and-conquee principle: they learn how to split large instances into smaller ones, that are then efficiently solved by external specialized solvers.
6 Experimental Evaluation
To evaluate the effectiveness of our method, we test it on four routing problems- - Euclidean TSP, CVRP, OP and Asymmetric TSP and one non-routing problem KP (details and results for the latter are in Appendix C For all routing problems, we train our model and all baselines on synthetic instances of size I00, following the same procedure of data generation as in [28]. For asymmetric TSP. we use Euclidean distance matrices and randomly break symmetries. We choose graphs of size 100 because it is the largest size for which (near) optimal solutions are still reasonably fast to obtain, and such training datasets are commonly used in the literature. Then, we test the trained models on synthetic instances of size 100, 200, 500 and 1K generated from the same distribution, as well as the standard TSPLib and CVRPLib datasets. Except for perceiver- based models and OP (dist), we limit the subgraphs to the 250 nearest neighbours of the origin node at test time. This reduces inference time while not significantly impacting the solution quality (see Appendix DD).
Hyperparameters and training. We use the same hyperparameters for all problems. The model has 9 layers, each built with 12 attention heads with embedding size of 192 and dimension of feed-forwar forward layer of 512. Our model is trained by imitation of expert trajectories, using cross-entropy loss. Solutions of these problems are obtained by using the Concorde solver (T] for TSP. LKH heuristic 17 for ATSP and CVRP, and EA40P heuristic (26] for OP. We use dataset of I million solutions. To sample trajectories out of this dataset, we note that in the case of TSP, any sub-path of the optimal tour is also an optimal solution to the associated path path-TSP sub-problem, hence amenable to our path-TSP model. We therefore form minibatches by first sampling a number n. between 4 and N (path-TSP problems with less than 4 nodes are trivial), then sampling sub-paths of length n from the initial solution set. At each epoch, we sample sub-path from each solution. By sampling subsequences among all possible infixes of the optimal solutions, we automatically get an augmented dataset, which some previous models had to explicitly design their model for [29]. We use a similar sampling strategy for CVRP, OP and KP (see Appendix [A] B and C). Batches of size 1024 are formed, and the model is trained for 500 epochs. We use Adam 25 as optimizer with an initial learning rate of 7.5c-4 and decay of 0.98 every 50 epochs.
Baselines and test datasets. We compare our model with the following methods: OR-Tools [37]. LKH [17, and Hybrid Genetic Search (HGS) for the CVRP 44 as SOTA nen-neural methods; DIFUSCO+2opt, Att-GNN-CTSS and SGBS as hybrid methods; and AM, TransformerTSP MDAM, POMO, DIMES and Sym-NCO as deep learning-
constructive methods. Deseription of all baseline models are provided in Sec. [S) For all deep learning baselines we use the corresponding model trained on graphs of size 100 and the best decoding strategy Following the same procedure as in 14). we generate four test datasets with graphs of sizes 100, 200, 500 and 1000. For CVRP, we use capacities of 50, 80, 100 and 250, respectively. In addition, we report the results on TSPLib instances with up to 4461 nodes and all CVRPLib instances with node coordinates in the Euclidean space. For all models, we report the optimality gap and the inference time. The optimality gap for TSP is based on the optimal solutions obtained with Concorde. For CVRP, although HGS gives better results than LKH, we use the LKH solutions as a reference to compute the "optimality" gap, in order to be consistent (and easily comparable) with previous works. For the OP task, train and test the model using a "distance" " variant of the problem, as described in (88) For fixed maximum lengths, we chose T100 4, 7:000 5, 7000 = 6, and 71000- 7. While the optimality gap is easy to compute and compare, running times are harder to compare since they strongly depend on the implementation platforms (Python, C++), hardware (GPU, CPU), parallelization. batch size, etc. In our experiments, we run all deep learning models on a single Nvidia Tesla V100-S GPU with 24GB memory, and other solvers on Intel(R) Xeon(R) CPU E5 2672 with 256GB memory, in one thread.
Results. Table summarizes our results for Euclidean TSP, CVRP and OP as well as asymmetric TSP. For all problems, model shows superior generalization on larger graphs, even with
2 AAt-GCC+MCTS is originally trained on graph sizes of 50. For DIMES and DIFUSCO authors provide generalization tables just for two types of and on some test datsets, so we report them in our results
decoding (greedy+2opt for DIFUSCO and RL+sampling for DIMES)
8

---

greedy decoding strategy, which generates single solution while all other baselines generate several hundreds (and select the best among them). In terms of running time, with greedy decoding, our model is slightly slower that Sym-NCO baseline, competitive with POMO, and significantly faster than other models. Beam search further improves the optimality gaps, but as expected, it takes more time. On the other hand, our model can be accelerated by replacing the quadratic attention blocks by the PerceiverIO architecture [9] (more details in Appendix [.I). This results a considerable reduction of inference time for larger graphs, at the cost of some performance drop. Even with this trade-off, our model achieves remarkable performance compared with other NCO baselines. Figure 3 shows optimality gap versus running time for models and other baseline models. Our models clearly outperform other models in terms of generalization to larger instances. The only models that competitive with ours are Att- Att-GCN+MCTS and DIFUSCO+2opt, but both are hybrid methods with an expensive search on top of the output of the neural network, and they are 2 to 15 times slower while being designed for TSP only. Finally, in addition to the synthetic datasets, we test our models on TSPLib and VRPLib instances, which are of varying graph sizes, node distributions, demand distributions and vehicle capacities. Table [ shows that our model significantly outperforms the end-to-end baseline policies even with the greedy decoding strategy.
40
SymNCO
TSP 100
140
AM
CVRP 100
SGBS
TSP 200
MDAM
CVRP 200
35
POMO
120
Att GON-MCTS
TSP 1000
OURS transf. (G)
CVRP 1000
Optimalty gae (N)
DIFUSCO
DINES
Optimalty 199
1.00
DURS perc.
OURS transf. (BS)
25
OURS transt (G)
20
OURS transt (BS)
QURS pert.
30
5-
10"
10
10
10a
10
10
10
10
10"
10'
Inference time Instance
Inference time instiance
Figure 3: Generalization results on different graph sizes for TSP (left) and CVRP (right). Lower and further left is better.
7 Conclusion
We proposed principled framework to formulate COPs efficient symmetry-invann invariant MDPs. First, we presented how to derive a direct MDP for any COP that is amenable to a constructive approach, and proved the exact correspondence between the optimal policies of this direct MDP and the optimal solutions of the COP it stems from. Second, for the widespread class of recursive COPs, we introduced bisimulation quotienting to leverage the symmetries of the partial solutions. We showed that the resulting BQ-MDP has a significantly reduced state space while its optimal policies still exactly solve the original COP. We then designed simple Transformer- based architecture as an examplification of a possible policy network for the BQ-MDPs, and applied it to five classical COP problems: (A)TSP, CVRP, OP and KP. The resulting policy generalizes particularly well, and significantly outperforms not only similar end-to-end neural- based constructive solvers but also hybrid methods that combine learning with search. A limitation of our approach, shared with all constructive methods, is that it can only handle problems for which feasibility is easy to ensure throughout the construction process. In order to address problems with more challenging global constraints, approaches which combine learning and constraint programming (e.g. (8) may be promising direction. While training on relatively small instances allowed us to use imitation learning, our proposed MDPs and the associated model could also be trained with Reinforcement Learning. This would be particularly interesting to extend our framework from deterministic to stochastic COPs.
9

---

Test (10k inst.)
Generalization (128 instances)
N=100
N=200
N=500
N=1000
opt. gap
time
opt.
gap
time
opt. gap
time
opt. gap
time
Concorde
0.00%
38m
0.00%
2m
0.00%
40m
0.00%
2.5h
OR-Tools
3.76%
1.th
4.52%
4m
4.89%
31m
5.02%
2.4h
Alt-OCI+MCTSS
0.04%
15m
0.88%
2m
2.54%
6m
3.22%
13m
DIFUSCO G+2opt"
0.24%
2.40%
4m
3.40%
12m
SGBS (10,10)
0.06%
15m
0.67%
lm 11.42%
20m
25.25%
2.9h
AM bs124
2.51%
20m
6.18%
lm 17.98%
8m
29.75%
31m
TSP
TSP bs1024
0.46%
51m
5.12%
lm
34.14%
9m
76.21%
37m
MIAM bs50
0.39%
45m
2.04%
3m
9.88%
13m
19.96%
1.1h
POMO augx8
0.13%
1.57%
58
20.18%
1m 40.60%
10m
DIMES RL++*
16.07%
1m
17.69%
2m
Sym-NCO s100
0.64%
2.28%
2s
21.64%
13s
37.51%
2m
BQ-percelver
0.97%
2.09%
2s
5.22%
8.97%
22s
BO-transformer G
0.35%
0.54%
9s
1.18%
55s
2.29%
2m
BQ-transtormer bs16
0.01%
32m
0.09%
0.55%
1.38%
38m
LKH
0.00%
15.3h
0.00%
30m
0.00%
1.3h
0.00%
2.8h
HGS
-0.51%
15.3h
-1.02%
30m
-1.25%
1.3h
-1.10%
2.8h
OR-Tools
9.62%
1h
10.70%
3m
11.40%
18m
13.56%
43m
AM bs1024
4.18%
24m
7.79%
lm
16.96%
8m
86.41%
31m
CVRP
MDAM b:50
2.21%
56m
4.33%
3m
9.99%
14m
28.01%
1.4h
POMO augx8
0.69%
Im
4.77%
5s
20.57%
1m
141.06%
10m
Sym-NCO s100
1.46%
4.84%
38
18.64%
13s
119.60%
9m
SGBS (4,4)
0.08%
15m
2.47%
1m
14.98%
20m
151.07%
2.9h
KQ-perceiver
5.63%
5.49%
38
6.39%
10.21%
24s
BO-transformer G
2.79%
2.81%
9s
3.64%
55s
5.88%
2m
BO-transformer bs16
0.95%
32m
0.77%
1.04%
2.55%
38m
EA40P
0.00%
1.4h
0.00%
3m
0.00%
1lm
0.00%
45m
OP (DIST.)
bs124
2.19%
7m
8.04%
1m
20.73%
4m
29.96%
15m
MDAM bs50
0.69%
32m
2.98%
49s
15.36%
4m
26.55%
15m
SymNCO <200
0.45%
4m
3.39%
2s
15.23%
37s
26.95%
2m
B()transtormer&
-0.15%
2m
0.62%
8s
3.26%
42s
8.40%
8.9m
BQ-transtormer bs16
-1.19%
35m
-0.84%
2.1m
1.04%
21m
4.81 %
2.2h
LKH
0.00%
1 18m
0.00%
29s
0.00%
2.3m
0.00%
9.4m
ATSP
MatNet s128f
0.93%
45m
124. 20%
4m
BO-GCN-transformee G
1.27%
1m
1.56%
4s
4.22%
12s
11.59%
14s
BO-GCN-transformer bs16
0.96%
19m
1.41%
1m
2.43%
3m
8.26%
7m
Table BQ-models with greedy rollouts (G) or Beam Search (bs) versus classic and neural baselines. The results for models" are taken from the original papers. For a fair comparison, model are evaluated on instances generated from the same distribution the training datasets for this model, which may differ from training and/or test distribution.
MDAM
POMO
BQ (ours)
MDAM
POMO
BQ (ours)
Set (size)
bs50
augx8
greedy
bs16
Size
bs50
x8
greedy
1s
(32-80)
6.17%
4.86%
4.52%
1.18%
< <100
3.06%
0.42%
0.34%
0.06%
(30-77)
8.77%
5.13%
6.36%
2.48%
100-200
5.14%
2.31%
1.99%
1.21%
(44-134)
16.96%
15.49%
6.63%
5.94%
200-500
11.32%
13.32%
2.23%
0.92%
M (100-200)
5.92%
4.99%
3.58%
2.66%
500-1K
20.40%
31.58%
2.61%
1.91%
P (15-100)
8.44%
14.69%
3.61%
1.54%
> >KK
40.81%
62.61%
6.42%
5.90%
(100-1K)
34.17%
21.62%
9,94%
7.22%
AlI
19.01%
26.30%
3.30%
2.55%
All (15-1K)
22.36%
15.58%
7.62%
4.83%
Table 2: Experimental results
TSPLib (left) and CVRPLib (right).
10

---

References
[1] David Applegate, Robert Bixby, Vasek Chvatal, and William Cook. Concorde TSP solver, 2015.
[2] Thomas Bachlechner, Bodhisattwa Prasad Majumder, Henry Mao, Gary Cottrell, and Julian McAuley. ReZero is all you need: Fast convergence at large depth. In Proceedings of the Seirtt- Conference on Uncertainty in Artificial Intelligence, pages 1352-1361. PMLR, December 2021.
[3] Richard Bellman. The Theory of Dynamic Programming. Technical Report P-550, The Rand Corporation, Santa Monica, CA, U.S.A., July 1954.
[4] Irwan Bello, Hieu Pham, Quoe V. Le, Mohammad Norouzi, and Samy Bengio. Neural Com- binatorial Optimization with Reinforcement Learning. 16 [es, stat], January 2017.
[5] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: A methodological tour d'horizon. European Journal of Operational Research, 290(2):405-421, 2021.
[6] Dimitri Bertsekas. Dynamic Programming and Optimal Control: Volume Athena Scientific, 2012. ISBN 978-1-886529-43-44
[7] Xavier Bresson and Thomas Laurent. The Transformer Network for the Traveling Salesman Problem. arXiv:2103.03011 [cs]. March 2021.
[8] Quentin Cappart, Thierry Moisan, Louis-Martin Rousseau, Isabeau Prémont-Schwarz, and Andre Cire. Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization. arXiv:2006. 01610 [cs], June 2020.
[9] Quentin Cappart, Didier Chételat, Elias B. Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial Optimization and Reasoning with Graph Neural Networks. In Twenty- Ninth International Joint Conference on Artificial Intelligence, volume 5, pages 4348 4355, August 2021.
[10] Jinho Choo, Yeong-Dae Kwon, Jihoon Kim, Jeongwoo Jae, Andre Hottung, Kevin Tiemny, and Youngjune Gwon. Simulation- Beam Search for Neural Combinatorial Optimization. In NeurlPS 2022, 2022.
[11] Michele Conforti, Gérard Cornuéjoss, and Giacomo Zambelli. Integer Programming, volume 271 of Graduate Texts in Mathematics. Springer International Publishing. Cham, 2014. ISBN 778-3-319-3843244
[12) William J. Cook, William H. Cunningham, William R. Pulleyblank, and Alexander Schrijver. Combinatorial Optimization. Wiley-Interscience, New York, 1st edition edition, November 1997. ISBN 978-0-471--5594-11
[13] Iddo Drori, Anant Kharkar, William R. Sickinger, Brandon Kates, Qiang Ma. Suwen Ge, Eden Dolev, Brenda Dietrich, David P. Williamson, and Madeleine Udell. Learning to Solve Combinatorial Optimization Problems on
Graphs Linear Time, June 2020.
[14] Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances. Proceedings of the AAAI Conference Artificial Intelligence, 35(8):7474-7482 May 2021. ISSN 2374-3468.
[15] Simon Geisler, Johanna Sommer, Jan Schuchardt, Aleksandar Bojchevski, and Stephan Gün- nemann. Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness. In Advances in Neural Information Processing Systems, December 2022.
[16] Edward Groshev, Maxwell Goldstein, Aviv Tamar, Siddharth Srivastava, and Pieter Abbeel. Learning Generalized Reactive Policies Using Deep Neural Networks. Proceedings of the International Conference on Automated Planning and Scheduling, 28:408 0188,46,,700 June 2018. ISSN 2334-0843.

---

[17] Keld Helsgaun. An Extension of the Lin- Seemiggan-HHlsgaae TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems. Technical report, Roskilde University. Roskilde, Denmark, 2017.
[18] Qingchun Hou, Jingwei Yang, Yiqiang Su, Xiaoqing Wang, and Yuming Deng. Generalize Learned Heuristics to Solve Large-scale Vehicle Routing Problems in Real-time In The Eleventh International Conference on Learning Representations, September 2022.
[19]
Andrew Jaegle, Sebastian Borgeaud, Jean-Baptiste Alayrac, Carl Doersch, Catalin Ionescu, David Ding, Skanda Koppula, Daniel Zoran, Andrew Brock, Evan Shelhamer, Olivier Henaff, Matthew Botvinick, Andrew Zisserman, Oriol Vinyals, and Joao Carreira. Perceiver IO: A General Architecture for Structured Inputs & Outputs. In International Conference on Learning Representations, January 2022.
[20] Yuan Jiang, Zhiguang Cao, and Jie Zhang. Solving 3D Bin Packing Problem via Multimodal Deep Reinforcement Learning. In Proceedings of the 20th International Conference on Au- tonomous Agents and MultiAgent Systems, AAMAS '21, pages 1548-15500 Richland, SC, May 2021. International Foundation for Autonomous Agents and Multiagent Systems. ISBN 978- 178-1-4503-8307-3.
[21] Chaitanya K. Joshi, Thomas Laurent, and Xavier Bresson. An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem. arXiv:1906.000 012277 [cs, stat], June 2019.
[22] Chaitanya K. Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent. Learning the travelling salesperson problem requires rethinking generalization. Constraints, 27(1-2): 70-98, April 2022. ISSN 1383-7133.
[23] Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning Combinatorial Optimization Algorithms over Graphs. In I. Guyon, U. V. Luxburg, Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 6348-6355 Curran Associates, Inc., 2017.
[24] Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization. In Advances in Neural Information Processing Systems, New Orleans, December 2022.
[25] Diederik P. Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization. In Proceedings of the 3rd International Conference on Learning Representations (ICLR), San Diego, May 2015.
[26) Gorka Kobeaga, María Merino, and Jose A. Lozano. An efficient evolutionary algorithm for the orienteering problem. Computers & Operations Research, 90:42-59, February 2018. ISSN 0305-0548.
[27] Andrey Kolobov, Mausam, and Daniel S. Weld. A theory of goal-oriented MDPs with dead ends. Proceedings of the Twenty-Eightt Conference on Uncertainty in Artificial Intelligence, 12, pages 438-447, Arlington, Virginia, USA, August 2012. AUAI Press. ISBN 978-0- 9749039-8-9.
[28] Wouter Kool, Herke van Hoof, and Max Welling. Attention, Learn to Solve Routing Problems! In International Conference on Learning Representations, 2019.
[29] Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. POMO: Policy Optimization with Multiple Optima for Reinforcement Learning. In Advances in Neural Information Processing Systems, volume 33, pages 21188 21 198. Curran Associates, Inc., 2020.
[30] Sirui Li, Zhongxia Yan, and Cathy Wu. Learning to delegate for large-scale vehicle routing, In Advances in Neural Information Processing Systems 34 Preceercce,,, 2021.
[31] Minghuan Liu, Menghui Zhu, and Weinan Zhang, Goal-Conditioned Reinforcement Learning: Problems and Solutions. In Thirty-First International Joint Conference on Artificial Intelligence, volume 6, pages 5502-5511, July 2022.
12

---

[32] Sahil Manchanda, Soñia Michel, Darko Drakulic, and Jean-Mar Andreoli. On the Generaliza- tion of Neural Combinatorial Optimization Heuristics. In European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECMI-PKKD)), Grenoble, France, September 2022.
[33] Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for combinatorial optimization: A survey. Computers & Operations Research, 1054000 October 2021. ISSN 0305-0548.
[34] MohammadReza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takac. Reinforce- ment Learning for Solving the Vehicle Routing Problem. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[35] Alex Nowak, David Folqué, and Joan Bruna. Divide and Conquer Networks. In 6-Th Interna- tional Conference on Learning Representations, Vancouver, Canada, April 2018.
[36] Bo Peng. Jiahai Wang, and Zizhen Zhang. A Deep Reinforcement Learning Algorithm Using Dynamic Attention Model for Vehicle Routing Problems. In Kangshun Li, Wei Li, Hui Wang, and Yong Liu, editors, Artificial Intelligence Algorithms and Applications, Communications in Computer and Information Science, pages 636-650, Singapore, 2020. Springer. ISBN 978981 1555770.
[37] Laurent Perron and Vincent Furnon. OR-tools, 2022.
[38] Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems. In Advances in Neural Information Processing Systems, December 2022.
[39] Francesca Rossi, Peter van Beek, and Toby Walsh. Handbook of Constraint Programming. Elsevier Science Inc., USA, July 2006. ISBN
[40] Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal Value Function Approximators. Proceedings of the 32nd International Conference on Machine Learning, pages 1312-1320. PMLR, June 2015.
[41] Jiwoo Son, Minsu Kim, Hyeonah Kim, and Jinkyoo Park. Meta-SAGE: Scale Meta-Learning Scheduled Adaptation with Guided Exploration for Mitigating Scale Shift on Combinatorial Optimization, June 2023.
[42] Zhiqing Sun and Yiming Yang. DIFUSCO: Graph-based Diffuusion Solvers for Combinatorial Optimization, February 2023.
[43] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is All you Need. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[44] Thibaut Vidal. Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood. Computers & Operations Research, 140:105643, April 2022. ISSN 0305-0548.
[45] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer Networks. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems 28, pages 2692-2700. Curran Associates, Inc., 2015.
[46] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Multi-Decoder Attention Model with Em- bedding Glimpse for Solving Vehicle Routing Problems. Proceedings of the AAAI Conference on Artificial Intelligence, 35(13): 12049, May 2021. ISSN 2374-3468.
[47] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang Step-Wise Deep Learning Models for Solving Routing Problems. IEEE Transactions on Industrial Informatics, 17(7):4861-487 July 2021. ISSN 1941-0050.
[48] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Generative Adversarial Training for Neural Combinatorial Optimization Models, January 2022.
13

---

[49] Cong Zhang, Wen Song, Zhiguang Cao, Jie Zhang, Puay Siew Tan, and Chi Xu. Learning to dispatch for job shop scheduling deep reinforcement learning In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS' 20, pages 1621- 1632, Red Hook, NY, USA, December 2020. Curran Associates Inc. ISBN 978-1-71 978-1-71382-954--
[50]
Jianan Zhou, Yaoxin Wu, Wen Song. Zhiguang Cao, and Jie Zhang. Towards Omni- generaieneali Neural Methods for Vehicle Routing Problems, June 2023.
[51] Zefang Zong, Hansen Wang, Jingwei Wang, Meng Zheng, and Yong Li. RBG: Hierarchically Solving Large-Scale Routing Problems in Logistic Systems via Reinforcement Learning. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 4648-4658, Washington DC USA, August 2022. ACM. ISBN 978-1-483 1-------3988--00
14


Reviews:
[{"review_id": "8UisGIT4fO", "reviewer": "Reviewer_fu7F", "summary": "This paper first present a formulation of Combinatorial Optimization Problems (COPs) as Markov Decision Processes (MDPs) that can leverage symmetries of COPs to improve out-of-distribution robustness. Based on the MDP formulation, the authors then introduce the Bisimulation Quotienting to the MDP, namely BQ-MDP, which can reduce the state space. Finally, the authors introduce a simple attention-based policy network to learn policies in the BQ-MDP. Experiments demonstrate that the proposed method achieves the state-of-the-art performance on both  synthetic and realistic benchmarks. \t", "questions": "Please refer to Weaknesses for my questions.", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. To the best of my knowledge, the idea of introducing the Bisimulation Quotienting (BQ) to exploit symmetries of COPs is novel.  \n2. Experiments demonstrate that the proposed method achieves the state-of-the-art performance on both  synthetic and realistic benchmarks. Moreover, the method achieves impressive generalization performance to much larger instances than seen during training.\n", "weaknesses": "The presentation could be improved. \n1. The authors claim that their formulation is generic for any CO problems. However, the formulation seems specific for the binary integer linear programming problems. Thus, it would be more convincing if the authors could explain how the proposed formulation applies to production planning problems with both continuous and discrete variables. \n2. The details about the proposed method are unclear to me. For example, the authors may want to explain why and how introducing Bisimulation Quotiented can exploit the symmetries of COPs. Moreover, the details about the impact of the BQ-MDP on model architecture is unclear. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful feedback and respond below to their questions and will be happy to further clarify any point. \n\nW1. **\"The formulation seems specific for the binary integer linear programming problems. Thus, it would be more convincing if the authors could explain how the proposed formulation applies to production planning problems with both continuous and discrete variables.\"**\n\nThe proposed formulation only applies to \"purely\" combinatorial problems, i.e. where each instance has a finite set of feasible solutions (as stated L72). This assumption is essential, and is repeatedly used in the proofs of all the properties (Appendix E). It would apply to Integer Linear (or non-linear) programs which are equivalent to binary integer programs. An extension of the framework to problems with both continuous and discrete variables, although outside of the scope of the paper, would be interesting to explore as future work.\n\nW2. **\"the authors may want to explain why and how introducing Bisimulation Quotiented can exploit the symmetries of COPs.\"**\n\nThe symmetry that we seek to exploit is that many pairs of an instance and a partial solution lead to the same tail subproblem and therefore an optimal policy should produce the same action at such pairs. Bisimulation quotienting allows to reduce the state space from (instance - partial solution) pairs to tail subproblems while preserving the equivalence between the MDP solving and the original COP solving.\n\nW2. **\"the details about the impact of the BQ-MDP on model architecture is unclear.\"**\n\nAs model architecture we use a transformer, similar to previous work. When dealing with states that are (instance - partial solution) pairs, previous works usually start by encoding the instance once and then mimic the autoregressive construction of the partial solution in decoding. With BQ-MDP, the input of the model is an instance and the output is one action leading to a new instance (tail subproblem). Thus we get rid of the autoregressive decoder, but we call the model at each step of the construction process, with the tail subproblem as input."}, {"review_id": "ZT3KblNOsZ", "reviewer": "Reviewer_cBr6", "summary": "The paper presents a generic framework for deriving direct MDPs for a given combinatorial optimization problem (COP) and propose a method for reducing the MDP using symmetry-focused bisimulation quotienting. Specifically, the paper presents a generic bisimulation that can be applied to a wide range of recursive problems. The paper presents an instantiation of the approach to three well known problems: TSP, CVRP, and Knapsack using a simple Transformer-based architecture with minor adaptation per application. The experiments show that the proposed approach obtains significantly better performance in generalizing to larger problems.", "questions": "I would appreciate the authors' response to my main concerns listed above.", "limitations": "There is no explicit discussion of limitation, however I have no concerns about the work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Novel and interesting approach to enhance neural combinatorial optimization problem by exploiting the recursive nature of many COPs.\n- The proposed technical approach seems to be relatively generic and can potentially be applied to a range of combinatorial optimization problems.\n- Experiments show significant improvement in generalizing to larger problems compared to the baselines.", "weaknesses": "- Experiments in the paper are limited to three benchmarks domains. While these are important and somewhat diverse domains, previous work has also considered combinatorial optimization problems like maximum cut, maximum independent set, etc. Further, as TSP and CVRP are highly related and the results for KP show somewhat different performance patterns, it is not clear how well this approach works beyond the limited set of benchmarks. Specifically, the results on KP that are only presented in the appendix show more limited improvement over POMO compared to TSP and CVRP (no other baselines). Taking into account that POMO is a relatively poor baseline on TSP/CVRP in terms of generalizing to larger instances, this raises the concern that the proposed method may not perform as well on domains beyond TSP/CVRP.\n\n - Comparison with previous symmetry-related enhancements such as Sym-NCO is missing. While the authors note that such approaches are \"orthogonal to our approach\", it is still important to evaluate the benefit of the proposed approach in presence of these augmentations.\n\n- The approach still requires optimal solutions for training. Such optimal solutions are typically intractable to compute beyond certain problem size. While the proposed approach shows very good performance in generalizing to larger problems, there may be a limit to the scalability (the paper presents results for up to one order of magnitude larger test problems). It is interesting to see if this can be paired with RL fine-tuning to further improve performance on larger instances.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful and constructive feedback. It inspired us to make more experiments that we believe make the paper stronger. We address here the main concerns:\n\nW1. **\"Experiments in the paper are limited to three benchmarks domains...\"**\nNew experiments with the Orienteering Problem and Asymmetric TSP have been added. See general response above and pdf attached to rebuttal.\n\nW2. **\"Comparison with previous symmetry-related enhancements such as Sym-NCO is missing...\"**\nThank you for pointing out this baseline. Comparison with Sym-NCO has been added. See general response above and pdf attached to rebuttal.\n\nW3. **\"The approach still requires optimal solutions for training... It is interesting to see if this can be paired with RL fine-tuning to further improve performance on larger instances.\"**\nWe currently solve instances with up to 4000 nodes (TSPlib). RL-finetuning would indeed be interesting to explore. We note that current neural models that achieve a good performance on even larger graphs such as TSP10,000 rely on improvement heuristics on top of the neural model (MCTS or 2-opt for AttGCRN, DIMES, DIFUSCO), which would be another possibility for future work.\n"}, {"review_id": "NBzFaI9zT6", "reviewer": "Reviewer_8qf4", "summary": "The paper proposes to use the notion of bisimulation quotienting (BQ) to define state spaces with the minimal information that is required to solve a combinatorial optimization (sub)problem. This results in a simpler architecture for the model used in training. Empirically, the methods advance state-of-the-art performance on a couple of routing problems.\n", "questions": "See the weaknesses section.\n\nThis paper seems relevant to this work: https://arxiv.org/pdf/2006.01610.pdf\nMight be good to discuss its relevance in the paper.\n\nIs the method more sample efficient that the other works? Intuitively, this should be one of the benefits because you are reducing states that are essentially the same but with different representations of partial solutions. ", "limitations": "I don't see any limitations other than those pointed out already.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper rigorously formulates BQ-MDP for CO problems. I find this method applicable to a wide range of CO problems whenever it could be formulated as dynamic programming.\n\nThe empirical results show that the method can generalize to larger instances than training. \n\nThe paper includes many baselines, including some recent ones e.g. DIFFUSCO. \n\nI also like the idea of testing the method with a lightweight version of transformers.\n", "weaknesses": "This method is limited to problems where finding feasible solutions are easy since it is mainly a construction heuristic.  Other problems like 3-SAT  (decision version of the Satisfiability problem, as opposed to MAX-SAT) that have a much constrained solution space might not be suitable for this method, though the BQ-MDP formulation is still applicable.\n\nFor people who are familiar with dynamic programming (DP), the idea behind the approach is pretty straightforward — In DP, it is crucial to identify the minimal state representation to solve a subproblem to reduce complexity. This paper formulates this idea in a more mathematical fashion.  \n\nI find this method applicable to a wide range of CO problems whenever it could be formulated as dynamic programming. But the authors didn’t emphasize this enough — it simply states it as a generic framework for COP. It is not obvious to readers how widely this method is applicable to COP. \n\n\nIn experiments, it would be nice to also report variances. The benchmarks used are mostly in euclidean space, which gives the readers an impression that this might only work for this case. Are there non-euclidean routing problem benchmark that you could test your approach on?\n\nIt seems that the method is not restricted to a particular learning algorithm or architecture. Imitation learning is just a way to go, but it wasn’t clear in the paper. In other words, would other learning methods like RL also be applicable?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful and detailed feedback. We address their concerns and questions below.\n\nW1. **\"This method is limited to problems where finding feasible solutions are easy since it is mainly a construction heuristic. Other problems like 3-SAT ... that have a much constrained solution space might not be suitable for this method, though the BQ-MDP formulation is still applicable.\"** Indeed we assume that feasibility of a final solution can be ensured through conditions on the partial solutions at each step of the construction process (L72 and L121). We argue that it is a necessary condition for all constructive approaches, although it is often not mentioned explicitly. This assumption may not hold for problems with complex, global constraints. In that case, the MDP may have dead-end states, which not all training algorithms are capable of dealing with (ref [23] on L124). We plan to make this assumption more explicit in the introduction.\n\nW2. **\"For people who are familiar with dynamic programming (DP), the idea behind the approach is pretty straightforward — In DP, it is crucial to identify the minimal state representation to solve a subproblem to reduce complexity. This paper formulates this idea in a more mathematical fashion.\"** Although we agree that the idea of restricting the state to the most compact representation may be intuitive, we believe that the mathematical formulation allows to prove the soundness of the approach and points out its requirements — e.g. the feasibility assumption (L121) and the need of a uniform instance parametrization (Sec 3.3).\n\nW3. **\"I find this method applicable to a wide range of CO problems whenever it could be formulated as dynamic programming. But the authors didn’t emphasize this enough — it simply states it as a generic framework for COP. It is not obvious to readers how widely this method is applicable to COP.\"**\n\nWe claim that the direct MDP framework (Sec 2) is generic and could be applied to any COP. The BQ-MDP is also generic in its abstract form (Sec 3.2). However, in order to implement the BQ-MDP, the optimality principle of dynamic programming is needed (Sec 3.3). We plan to emphasis this more in the introduction.\n\nW4. **\"In experiments, it would be nice to also report variances.\"**\nIn our experience, the variances are pretty small. Similarly to all previous works on the same benchmarks (e.g. AM, POMO, MDAM, DIMES, DIFUSCO etc) we did not report them in the table because of lack of space. However we could add them in the Appendix.\n\nW5. **\"The benchmarks used are mostly in euclidean space, which gives the readers an impression that this might only work for this case. Are there non-euclidean routing problem benchmark that you could test your approach on?\"**\n\nYes, non-Euclidian (actually not even symmetric) routing results have been added. See the general response and the pdf attached to the rebuttal.\n\nW6. **\"It seems that the method is not restricted to a particular learning algorithm or architecture. Imitation learning is just a way to go, but it wasn’t clear in the paper. In other words, would other learning methods like RL also be applicable?\"**\n\nAbsolutely. Indeed the BQ-MDP, formulated as a bisimulation of the direct MDP, is not tied to a training procedure and therefore could be solved with RL. We mention this in the conclusion (L382) but could mention it earlier in the paper.\n\nQ1. **\"Discussion of https://arxiv.org/pdf/2006.01610.pdf\"**\n\nOur paper focuses exclusively on MDP-based solutions to COP, while admittedly there are many more approaches, including the hybrid CP-DRL approach proposed in this reference. Thanks to its CP component, this approaches may handle COP with more challenging feasibility constraints. It would make sense to mention it indeed in the paper as an alternative for those problems.\n\nQ2. **\"Is the method more sample efficient that the other works? Intuitively, this should be one of the benefits because you are reducing states that are essentially the same but with different representations of partial solutions.\"**\n\nWe use 1M training instances per problems (TSP100, CVRP100 and KP100). Our training is definitely more sample efficient than RL-based approaches (e.g. AM/POMO training uses 128M/20M TSP100 instances) but this is certainly due to the supervision. When we compare to other SL-based methods, we used the same training datasets as Joshi et al 2019/DPDP of 1M instances while DIFUSCO used about 1.5M instances for TSP100. However the sample efficiency is more obvious at a higher level since the generalization ability of our model allows us to only train one model per problem while all the models above are trained separately for each instance size.\n"}, {"review_id": "aKIoFTmWWj", "reviewer": "Reviewer_e3VL", "summary": "Based on Bisimulation Quotienting (BQ), this paper proposed a new MDP formulation named BQ-MDP, to better formalise the process of solution construction in neural constructive solvers for CO problems. The proposed BQ-MDP reduces the state space and is designed to better reflect the symmetry of sub-problems encountered during solution construction. A new deep model named BQ-Transformer (based on Transformer) is designed according to the BQ-MDP, which is leveraged to solve CO problems including TSP, CVRP, and KP. The deep model is trained via supervised learning and the results showed better generalization performance of the learned model across problem sizes and distributions compared to several baselines.", "questions": "- Are the test datasets the same as DIEMS and DIFUSCO? How many instances are in the test datasets? Why have the objective values, in addition to the gaps, not been reported in Table 1?\n\n- What are the principal differences between the proposed model architecture and the one in reference [4]? Can we apply [4] to reflect the features of BQ-MDP?\n\n- The claim about the generality of BQ-MDP seems to be overstated. Are there certain Combinatorial Optimization Problems (COPs) that the MDP might struggle to handle? For instance, how would the MDP manage problems where the feasibility of the solution can only be determined when the solution is complete, as in some Simulation Optimization tasks?\n\n- Can the authors clarify the mathematical notations mentioned above? It may be beneficial to include examples (for instance, toy TSP-5 instances) to illustrate the new concepts introduced.\n\n- I could not find the correct Appendix; the current zip file contains the submitted manuscript for ICLR23, not the NeurIPS appendix.\n", "limitations": "The limitation mentioned in the weakness above should be discussed in the revised paper.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The introduction of BQ into MDP formulations for neural constructive solvers is novel and interesting.\n- While several works like POMO (NeurIPS-20) [1], Sym-NCO (NeurIPS-22) [2] and Pointformer (AAAI-23) [3] have tried to explore the symmetries of CO problems, the idea of exploiting the symmetries during the recursive construction process is novel.\n- The proposed model showed impressive generalization performance across size and distribution, outperforming several baselines.\n- The exploration of BQ-PerceiverG to reduce computational complexity.\n", "weaknesses": "\n- The clarity of the paper, particularly the mathematical formulations in Section 2.1 and Section 3.1, is limited. Examples include but are not limited to: the concept of the \"step set Z\" being “a set of partial solutions obtained by one construction step” is unclear, as it is not explicitly stated whether this step is based on an empty solution or an existing partial solution; It is said that “if x, y are partial solutions, x◦y denotes the result of applying the sequence of construction steps yielding x followed by that yielding y”, but I did not follow this definition. If x = z_1◦ · · · ◦ z_n,  does it means that z_i are partial solutions?\n\n- The novelty (about the model architecture) may be limited. The proposed architecture seems to share similarities to an earlier exploration in [4] which also suggests re-encoding the sub-problems during solution construction. Furthermore, in the model designs, the claim about the elimination of the autoregressive decoder may not be compelling. Essentially, the proposed model, similar to AM and POMO, also requires multiple calls to select nodes for solution construction. And the proposed model still follows the encoder-decoder structure, as the last linear layer (used for generating the probability of selecting nodes via softmax) is the decoder.\n\n- The model is trained using imitation learning, which necessitates labeled data and pre-existing solvers to generate high-quality solutions. It is thus not clear if the credits for better performance should be given to the imitation learning/labeled data, or the proposed new architecture.\n\n- The experimental comparisons raise several concerns which make the advantages of the proposed method unclear:\n1. On TSP-100 and CVRP-100 (without generalization), the BQ-Transformer performs worse than POMO despite using a longer runtime, particularly on CVRP. The BQ-Transformer seems to struggle with handling VRP constraints effectively. \n2. Furthermore, when BQ-Transformer is equipped with beam search, there is no comparison made with POMO under similar settings, e.g., the POMO + beam search as proposed in the SGBS paper (NeurIPS2022) [5]. \n3. Are the test datasets the same as DIEMS and DIFUSCO? How many instances are in the test datasets? The reported performance gaps of DIMES and DIFUSCO may be inaccurate, as I could not locate the reported gaps in their papers. \n4. Since the models are trained on size 100, in Table 1, it would be clearer to label TSP200, TSP500, and TSP1000 as performance under generalization, rather than mixing them up, which could lead to confusion.\n5. While the proposed model exhibits better generalization on larger-scale instances, it is unclear whether the model has the ability to further reduce the objective values (gaps) given a longer time budget, and how good the performance would be when compared to baselines with longer run time.\n\nReferences: \n\n[1] Kwon, Yeong-Dae, et al. \"Pomo: Policy optimization with multiple optima for reinforcement learning.\" Advances in Neural Information Processing Systems 33 (2020): 21188-21198.\n\n[2] Kim, Minsu, Junyoung Park, and Jinkyoo Park. \"Sym-nco: Leveraging symmetricity for neural combinatorial optimization.\" Advances in Neural Information Processing Systems 35 (2022): 1936-1949.\n\n[3] Jin, Yan, et al. \"Pointerformer: Deep Reinforced Multi-Pointer Transformer for the Traveling Salesman Problem.\" arXiv preprint arXiv:2304.09407 (2023).\n\n[4] Xin, Liang, et al. \"Step-wise deep learning models for solving routing problems.\" IEEE Transactions on Industrial Informatics 17.7 (2020): 4861-4871.\n\n[5]  Choo, Jinho, et al. \"Simulation-guided beam search for neural combinatorial optimization.\" Advances in Neural Information Processing Systems 35 (2022): 8760-8772.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed feedback. We answer below their questions and clarify important points.\n\nW1/Q4. **\"about the step set Z\"** We understand the ambiguity and confirm that a step is a partial solution obtained by one construction step *starting from the empty solution*.\n\nW1/Q4. **\"About the definition of x◦y and that it may be beneficial to include examples\"** It is important to remember that in our definition, *partial solutions* are not linked to an instance but just a CO problem (L79). We provide examples of the introduced concepts in the paragraph \"Examples of Solution Spaces\" L93. In particular, we mention that for TSP a step is simply a singleton node, a partial solution a sequence of nodes and  x◦y denotes the concatenation of two node sequences.\n\nW1/Q4. **\"If $x = z_1◦ · · · ◦ z_n$, does it means that $z_i$ are partial solutions?\"** Yes, here $z_i$ are steps and therefore by definition partial solutions.\n\nW2. **\"What are the principal differences between the proposed model ... and [4]?\"** [4] is specific to TSP/CVRP, where they simply drop visited nodes, while our approach works with any problem amenable to DP. In fact, for CVRP, they need to keep a trace of the visited nodes to restrict the feasible actions; we don't have this issue: it is dealt with by the tail sub-problem mechanism of DP. Please refer to Appendix D.2 for more comparisons. [4] suggest an approximation where part of the encoder is fixed while top layers are recomputed with a mask on already visited nodes. We have tried this approximation in our context and observed a drop in performance, suggesting that solving the precise BQ-MDPs is key to our results.\n\nW2 **\"the claim about the elimination of the autoregressive decoder may not be compelling...the proposed model still follows the encoder-decoder structure, as the last linear layer (used for generating the probability of selecting nodes via softmax) is the decoder.\"**\nWhile we agree that the last linear layer could be viewed as a decoder, since the whole model is called at each construction step, it seems artificial to us to separate the encoding from the decoding. This is in contrast to AM/POMO where the encoder is called once per instance and then the decoder many times.\n\nW3. **\"It is thus not clear if the credits for better performance should be given to the imitation learning/labeled data, or the proposed new architecture.\"** First, please note that we do not claim proposing a novel architecture. It is a simple transformer model, similar to previous works, with slight adaptations of input and output layers to match the BQ-MDP. The novelty is in the BQ-MDP framework. Also the results are consistent with different architectures (transformer, perceiver and the combination of transformer and GCN as introduced in the General Response above). Experimentally, we show that the combination of efficient imitation training with our models works very well. Note that the BQ-models outperform some other approaches that rely on labeled data (Att-GCN and DIFUSCO).\n\n**\"when BQ-Transformer is equipped with beam search, there is no comparison made with POMO under similar settings, e.g., the POMO + beam search as proposed in the SGBS paper [5]\"**. We added this baseline in the Table in the rebuttal document. The BQ-transformer + beam search outperforms SGBD on 7 out of 8 datasets, e.g. with a reduction of the opt gap from 25% (in 6h) to 1.38% (in 38min) on TSP1000.\n\n**\"C3/Q1. Are the test datasets the same as DIEMS and DIFUSCO? How many instances are in the test datasets? The reported performance gaps of DIMES and DIFUSCO may be inaccurate, as I could not locate the reported gaps in their papers.\"** Yes same datasets (introduced in Fu et al 2021). They contain 10k instances for TSP100 and 128 for TSP200/500/1000. The reported results in our Table 1 correspond to the \"interpolation results\" presented in Table 5 of the DIMES paper and Figure 3 in DIFUSCO paper. The objective values are not reported to save space and because find the optimality gap to be the most informative. However we can add them in the Appendix. \n\nC5. **\"While the proposed model exhibits better generalization on larger-scale instances, it is unclear whether the model has the ability to further reduce the objective values (gaps) given a longer time budget and how good the performance would be when compared to baselines with longer run time.\"** Given a longer time budget, one could use a search procedure or improvement heuristic on top of our model. We do this already with a simple beam search (see \"BQ-Transformer bs16\" in Tables 1,2) and obtain a significant performance gain at the cost of a somewhat reasonable increase of computing time (from less than 2 min to at most 38 min). With the beam-search, our model outperforms the baselines for TSP, CVRP, ATSP, OP and KP on the vast majority of the test datasets, outperforming baselines that use 2-opt (DIFUSCO) or MCTS (Att-GCN). Tests with even longer running times and more sophisticated search methods such as Active Search are possible but outside the scope of this paper.\n\nQ3. **\"Are there certain Combinatorial Optimization Problems (COPs) that the MDP might struggle to handle? For instance, how would the MDP manage problems where the feasibility of the solution can only be determined when the solution is complete..\"** As stated L64: \"We present a generic and principled framework to derive a direct MDP given any COP with minimal requirements\". And indeed we make the assumption (L76) that the feasibility of the solution can easily be ensured during the construction process. This is a necessary condition for constructive approaches to work and it is not specific to the BQ-MDP.\n\nQ5. **\"I could not find the correct Appendix; the current zip file contains the submitted manuscript for ICLR23, not the NeurIPS appendix.\"**\nWe double-checked and confirm that the appendix is accessible through the supplementary material link in the submission page."}]

Author rebuttal:
We thank the reviewers for their insightful feedback. We are encouraged that they appreciated the **novelty of the BQ-MDPs** (fu7F,cBr6,e3VL), the **wide applicability of our approach** (cBr6,8qf4) and its **impressive generalization results** (fu7F,e3VL) with the simple transformer model as well as its **efficiency with the lightweight perceiver** architecture (8qf4,e3VL).

A **common concern was the limited set of benchmark problems**, questioning whether the excellent generalization performance would hold beyond the tested problems. Indeed cBr6 noted the limitation to 3 problems, 8qf4 the limitation of TSP/CVRP to the Euclidian setting and e3VL mentioned that our model may struggle with the CVRP constraints. 

To address these concerns, we have applied our approach to **two more problems**: the **Orienteering Problem (OP)** (which has another kind of constraints) and the **Asymmetric TSP (Asym-TSP)** (non-Euclidian routing problem). We present in the rebuttal PDF file a new table with:

* the original paper results (for TSP, CVRP, KP) with 2 additionnal baselines: Sym-NCO [1] (suggested by cBr6) and SGBS [2] (suggested by e3VL).
* the new results for the OP and Asym-TSP with the appropriate neural baselines and classic solvers (see Details below).

The results for OP and ATSP are consistent with those of TSP, CVRP and KP: the greedy rollout of the BQ models already gives a very good generalization performance; with a beam search (with beam width of 16), our model outperforms the neural baselines for 7 out of 8 test datasets. Notably, BQ-GCN-transformer is the first model, to the best of our knowledge, that is able to solve ATSP instances of sizes 500 and 1000. And for OP100 and 200, the BQ-transformer model outperforms even the state-of-the-art classic solver Compass [4] (hence the negative opt gap). This confirms the versatility of the BQ-MDPs.

### Details about new OP and Asym-TSP experiments:

Both problems satisfy the recursivity property which enables our BQ-MDP approach. The BQ-MDPs for Asym-TSP is the same as for TSP. For OP, a construction step is the selection of a node. The BQ-MDP state is (the tail subproblem) OP instance consisting of the remaining nodes and with the maximal distance updated by subtracting the length of the partial solution.

Since an Asym-TSP instance is parametrized by a distance matrix (instead of node coordinates), we had to slightly update our model architecture to accommodate that new input format: we have simply intertwined Graph Convolutional Network layers (1st order model in [3]) with the original attention layers. A diagram of this modified architecture is included in the rebuttal PDF. We kept the model hyperparameters the same as for TSP, CVRP and OP.

### Datasets:

We train our models on 1M instances of ATSP100 (resp. OP100) and the associated high-quality solutions provided by the standard solvers LKH (resp. Compass [4]). The synthetic instances for ATSP are generated following a distribution inspired by (i.e. matching the statistics of) the provided datasets of the recent competition [6].

### Baselines: 

For OP, we use the state-of-the-art Compass [4] solver as well as three neural approaches: AM, MDAM and SymNCO [1].
For ATSP, MatNet [5] is the only neural approach. We tested the provided MatNet model (trained on ATSP100) on ATSP100/200 but it could not be applied on instances with 500 and 1000 nodes. The lack of flexibility of the model w.r.t. graph sizes is in fact explained in the paper (Sec 3.3).

[1] Kim, et al, "Sym-NCO: Leveraging symmetricity for neural combinatorial optimization", NeurIPS 2022.  
[2] Choo et al, "Simulation-guided Beam Search for Neural Combinatorial Optimization", NeurIPS 2022.  
[3] Kipf and Welling, "Semi-Supervised Classification with Graph Convolutional Networks", ICLR 2017.  
[4] Kobeaga et al. "An efficient evolutionary algorithm for the orienteering problem", Computers & Operations Research 2018.  
[5] Kwon et al, "Matrix Encoding Networks for Neural Combinatorial Optimization",  NeurIPS 2022.  
[6] EURO Meets NeurIPS 2022 Vehicle Routing Competition.  


Meta-review: All reviewers are supportive of accepting this work, and I agree.

I would suggest the authors incorporate the feedback and suggestions provided by the reviewers in preparation of their camera-ready version.
Decision: Accept (poster)