BQ-NCO: Bisimulation Quotienting for Generalizable Neural Combinatorial Optimization
Authors: Darko Drakulic
Sofia Michel
Florian Mai
Arnaud Sors
Jean-Marc Andreoli
Venue: Submitted to ICLR 2023 (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 and Capacitated Vehicle Routing Problems. We present a BQ reformulation of these problems and introduce a simple attention-based policy network that we train by imitation of (near) optimal solutions for small instances from a single distribution. 
We obtain new state-of-the-art generalization results for instances with up to 1000 nodes from synthetic and realistic benchmarks that vary both in size and node distributions.

Under review as a conference paper at ICLR 2023
BQ-NCO: BISIMULATION QUOTIENTING FOR GENER-
ALIZABLE NEURAL COMBINATORIAL OPTIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
Despite the success of Neural Combinatorial Optimization methods for end-to- end heuristic learning, out-of-distributtin generalization remains a challenge. In this paper, we present novel formulation of combinatorial optimization (CO) problems as Markov Decision Processes (MDPs) that effectively leverages sym- metries of the CO problems to improve out-of-distributie 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 BQ reformulation of these problems and introduce sim- ple attention-ban 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.
INTRODUCTION
Combinatorial Optimization problems are crucial in many application domains such as transporta- tion, energy, logistics, etc. Because they are generally NP-hard (Cook et al.) [997], their resolution real-life scales is mainly done by heuristics. which are efficient algorithms that generally produce good quality solutions (Boussaid et al., 2013). However, strong heuristics are generally problem- specific and designed by domain experts. Neural Combinatorial Optimization (NCO) is a relatively recent line of research that focuses on using deep neural networks to learn such heuristics from data, possibly exploiting information on the specific distribution of problem instances of interest (Bengio cet al. 2021: Cappart et al. 2021). Despite the impressive progress in this field over the last few years, their out- distributitiiitioonnn generalization, especially to larger instances, remains a major hurdle (Johh et al. 2022 Manchanda et al. (2022).
In this paper, we are interested in constructive NCO methods, which build a solution incrementally, by applying sequence of elementary steps. These methods often quite generic, see e.g. the seminal papers by Khalil et al.] (2017); Kool et al. (2019). Most CO problems can indeed be rep- resented in this way, although the representation is not unique as the nature of the steps is, large extent, a matter of choice. Given a choice of step space, solving the CO problem amounts to computing an optimal policy for sequentially selecting the steps in the construction. This task can typically be performed in the framework of Markov Decision Processes (MDP), through imitation or reinforcement learning. The exponential size of the state space, inherent to the NP-hardness of combinatorial problems, usually precludes other methods such as (tabular) dynamic programming. Whatever the learning method used to solve the MDP, its efficiency, and in particular its out-of- distribution generalization capabilities, greatly depends the state representation. The state space often characterized by deep symmetries, which, they are not adequately identified and lever- aged, hinders the training process by forcing it to independently learn the policy at states which in fact are essentially the same (modulo some symmetry).
In this work, investigate type of symmetries which often occurs in MDP formulations of con- structive CO heuristics. We first introduce a generic framework to systematically derive a naive CO problem-specific MDP. We formally demonstrate the equivalence between solving the MDP and

---

Under review as a conference paper at ICLR 2023
solving the CO problem and highlight the flexibility of the MDP formulation, by defining mini- mal set of conditions for the equivalence to hold. Our framework is general and easy to specialize to encompass previously proposed learning-basse construction heuristics. We then show that the state space of this naive MDP is inefficient because it fails to capture deep symmetries of the CO problem, even though such symmetries transform the naive MDP, based on the concept of bisimulation quotienting (BQ), in order to get reduced state space, which is easier to process by the usual (approximate) MDP solvers. We il- lustrate our approach on three well-known CO problems, the Traveling Salesman Problem (TSP), the Capacitated Vehicle Routing Problem (CVRP) and Knapsack Problem (KP). Furthermore, we propose simple transformer-based architecture for these problems. that we train by imitation of expert trajectories derived from (near) optimal solutions. In particular, we show that our model is well-suited for our BQ formulation: it spends a monotonically increasing amount of computation as a function of the subproblem size (and therefore complexity), in contrast to most previous models. Finally, extensive experiments confirm the validity of our approach, and in particular its state-of-the- art out-of diit----iitiitttioon generalization capacity. In summary, our contributions are as follows: 1) We present generic and flexible framework to define construction heuristic MDP for arbitrary CO problems; 2) We propose a method to simplify commonly used "naive" MDPs for constructive NCO via cymmetry-focusee bisimulation quotienting: 3) We design an adequate transformer- archi- tecture for the new MDP, for the TSP, CVRP and KP; 4) We achieve state-of-ther of-the--rtttttt--e art generalization performance on these three problems.
easy identify. Therefore, we propose method to
COMBINATORIAL OPTIMIZATION AS A MARKOV DECISION PROBLEM
In this section, we present generic formalization of constructive heuristics which underlies their MDP formulation. A deterministic CO problem is denoted by a pair (F, where F is its ob- jective function space and X' its (discrete) solution space. A problem instance feF is mapping (oo)) with the convention that f(=)=oo if x is infeasible for instance f. A solver for problem (F, X²) is functional:
SOLVE: F + X
satisfying
SOLVE(f) arg min fx)) =EX
(1)
Incremental solution construction Constructive heuristics for CO problems build a solution se- quentially, starting at empty partial solution and expanding it at each step until finalized solution is reached. Many NCO approaches are based on a formalization of that process as an MDP, e.g. Khalil al. (2017): Kool al. (2019); Zhang al. (0020). Such an MDP can be obtained, for an arbitrary CO problem (F, using the following ingredients:
Steps: T is a set of available steps construct solutions. A partial solution is a pair (f.tim) fimm)) of a problem instance feF and sequence of steps t1m (the set of sequences of elements of T). Observe that a partial solution (in F Fx)") not a solution (in X),, but may represent one.
Representation: SO1:FFX"*=Xuf } is mapping that takes partial solution and returns ei- ther a feasible solution (in which case the partial solution is said to be finalized), or otherwise. Evaluation: VAL:FxT' - } is a mapping that takes partial solution and returns esti- mate of the minimum value of its expansions into finalized solutions. If the returned value is finite, the partial solution is said to be adnissible.
In order to define an MDP using these ingredients, we assume they satisfy the following axioms:
vEE f(x) < 0o < M1mm E T such that SOI. (1m)) = F, VJEF,ImET
(2a)
(OL()))m)) #1 + Vme (mm-1: SOL (1:m) = d,
(2b)
YfFF,timeT ,EX, sf = {
VAL t1..) = f(z), vm E (1:n-1}, VAI((f, < co.
(2c)
Equation 2a states that the feasible solutions are exactly those represented by a finalized partial solution; Equation states that if a partial solution is finalized then none of its preceding partial solutions in the construction can also be finalized; Equation st that the evaluation of a finalized partial solution is the value of the solution it represents, and all its preceding partial solutions are admissible.
We call a triplet (T, SOL, VAL) satisfying the above axioms a specification of problem (F,X). Note that specification is not intrinsic to the problem. The step space 'I results from choice
2

---

Under review as a conference paper at ICLR 2023
of how construct a solution sequentially. Once T is chosen, SOL is determined, and must satisfy Equation Iqquation2aaamn and 2b Then VAL is only loosely constrained by Equation 2c and can be chosen among wide range of alternatives, including the following straightforward, uninformed one and the ideal, but intractable one (and, more likely, somewhere in between these two extremes):
VAL uninformed (S, (1m) aer (xx if [s (mm) = x + 1 else O,
VAI. VAI.deul (S, h.:) der (i)( X, 3.1m T s.t. SOT (f,,,,,,))) (1: (1:mm x);
with the convention min -000. Value 0 in the uninformed case can be replaced by any constant.
Solution construction as an MDP Using a specification (T, SOL, VAL) of problem (F,X), one can derive a "naive" MDP as follows. States are partial solutions (in FxT"); actions are steps (in T); state is terminal if it is a finalized partial solution; transitions: action uET applied to a non-terminal state (f, (m leads to state (f. (1 where u is appended to the sequence so far, with reward VAL(f, (1.m)) (fL u), conditioned on VAL (1m))) being finite. Note that VAL has the double role of providing a reward and specifying the set of allowed actions. The number of these is expected to be linear, or worst polynomial, in the size of the instance, since picking step should not be as complex as solving the whole problem.
Now, assume have access to generic solver SOLVE which, given MDP M and of its states 8a. returns an optimal trajectory starting at that state, i.e. arg max, R(T) where T ranges over the -M-trajectories starting at S, and ending in terminal state, and R(T) denotes its cumulated reward. Note that because we are dealing with deterministic MDPs, looking for an optimal policy is the same looking for an optimal trajectory for given set of initial states. That is why SOLVE is defined here directly in terms of trajectories rather than policies. SOLVE MDP can then be specialized into a solver for the specific CO problem (F.2):
Let M. be the naive MDP obtained from specification (T,SOL, VAL). The proce- dure defined as follows (where denotes the empty sequence) satisfies the requirement of equation
Proposition 1.
SOLVE(S E F) -dd {s)Lss))s is the last state of the trajectory MDP (MMM (f)e))}.
In other words, solving the naive MDP is equivalent to solving the CO problem. The detailed proof of Proposition]] is in Appendix F Of course, procedure SOLVEMDP may be approximate, in which case so is procedure SOLVE. Moreover, its performance depends on that of MDP esp. its out- of-distribution generalization capacity, but also the choice of specification, esp. of action space. It is a distinguishing feature of CO from an MDP perspective that the action space is not prescribed by the problem.
The impact of the choice of the VAI. mapping depends on the type of learning used by MDP When MDP learns by reinforcement, VAL essential, as it provides the rewards which guide the resolution. For example, VAL uninlormedd leads to the notoriously hard case of sparse rewards, while VALidal ideal (were it tractable) would lead to the trivial case where myopic policy (greedy in its immediate reward) is optimal. Although we do not provide generic method to design VAL, we argue that there are natural candidates, typically based on extending the objective function to partial solutions (not just finalized ones). When SOP learns by imitation instead, the choice of VAL has a much more limited impact: it only serves to define the allowed actions. The critical factor in that case is the construction of the training dataset of expert trajectories to imitate.
Example on TSP Consider the widespread CO problem known as the Traveling Salesman Prob- lem (TSP) in Euclidian space V. TSP solution (in X') is path, i.e. finite sequence of pairwise distinct nodes. A TSP instance (in F) is given by finite set D of nodes as points in V, and maps any solution (path) to the length of that path (closed at its ends) if visits exactly all the nodes of D, and oo otherwise (infeasible solutions).
A simple specification (T, SOL, VAL) for the TSP is given by: the step space T is the set of nodes; for given instance and sequence fimm of steps, SOL(f, (1m) is either the sequence fu.m if it forms a path which visits exactly all the nodes of f. or 1 otherwise; and VAL(f. f1:)) is either the length of path ti.m (closed at its ends) if it forms path which visits only nodes of f (maybe not all), or co otherwise. It is easy to show that we thus obtain a specification (as defined by the axioms above) of the TSP. In TSP-MDP the naive MDP obtained from it, the reward of taking action (a node)
3

---

Under review as a conference paper at ICLR 2023
stepl (a++)
step (=(a+e)
step (-(a+))
Figure I: An example of bisimulation commutation in TSP-MDP, and the corresponding path-TSP- MDP transition. The step is the same in all three transitions: it is the end node of the dashed arrow. And the reward is also the same: depends only on the distances a, u, v, and not on any of the previously visited nodes.
at state (f, is ( f1) - (6 u) u (1)) where by is the node distance measured on the corresponding points of in f, conditioned on fimm being pairwise distinct nodes of f. Observe that when allowed, the reward depends only on the start and end nodes f fa of the step sequence.
3 BISIMULATION QUOTIENTING FOR COMBINATORIAL OPTIMIZATION
In our context of deterministic CO problems and therefore deterministic MDPs, the general notion of bisimilarity is simplified (Givan et al., 2003); states said to be bisimilar if they spawn exactly the same action-reward sequences. Likewise, the notion of a binary relation R on states being bisimulation reduces to a commutation between the (deterministic) transitions of the MDP and that relation: if 81 RR2 and action a applied to state leads to state s with reward then action a applied to state 82 leads state 8/ with the same reward r, and s Rssg An illustration given in Fig Bisimilarity is equivalently defined the largest bisimulation (see Appendix H.I
-antmlllarii--inueee symmetries problem, state is partial solution and carries the whole information about the "past" decisions (steps) leading to it, which may not all be useful for the "future" decisions, i.e. the completion that partial solution. Consider for example the following of steps of the partial solution is represented as directed path in red among some of the problem instance nodes:
the naive MDP obtained from a specification of given CO
states in TSP-MDP, in which the sequence
81
$2
Observe that $1, 82 differ only in the inner nodes of the red path (black diamond-shapp nodes). Now, it is easy they each consist
that the successful completions of these two partial solutions identical:
path visiting the (same) unvisited (blue) nodes, starting at the end node of the red path and ending its start node, with the same rewards defined by VAL.. Consequently, in the MDP, the two states $1 82 spawn exactly the same action-reward sequences and form a bisimilar pair. This is the kind of deep symmetries of the problem which we want the MDP to leverage. Of course, there exist other kinds of symmetries, e.g. rotational symmetries: if 82 is obtained from by applying an isometric transformation all the points in the problem instance, then $1, $2 also form bisimilar pair. However, the latter symmetry is specific to the Euclidian version of the TSP. We focus here on the former kind of symmetry as it more general. Although has previously been noted for routing problems (Peng et al. 2020 Xin et al. 2021c), we show here that it is an inherent characteristic of constructive CO approaches.
Bisimulation quotienting A classical result MDPs GGivan et al. 2003) states that all such symmetries in any MDP can be leveraged by quotienting it by its bisimilarity relation, i.c. the set of all bisimilar pairs. Of course, there is no free lunch: constructing the bisimilarity of MDP is in
4

---

Under review as a conference paper at ICLR 2023
general intractable. Still, the result remains valuable because it holds for any bisimulation, not just the bisimilarity. Therefore one can control the amount of symmetries captured in the quotienting by carefully choosing the bisimulation, trading off its closeness to full bisimilarity for tractability.
We now assume that, for a given CO problem (F, X)) we have access not only to a specification ,OL, VAL) with its associated naive MDP, but also to a mapping $:Fx7"-S from partial solutions to some new space S. Typically, ((f.4.)) should capture, within the partial solution (f. a piece of information as small as possible but sufficient to determine the set of action- reward sequences it spawns in the MDP - in other words, a summary of its "past" which is sufficient to determine its "future". We can then define an equivalence relation = where two partial solutions equivalent if they have the same image by o. For to be bisimulation, + must satisfy:
VuET, (($11)=$($2u) and VALL(S)--VA((TT)==-aa VAL
11s, 52 ((8))
(3)
Under that assumption, we can construct ulation) which is equivalent, as far as policy optimization is concerned, to the original one, but captures more symmetries of the problem. This allows reduce the state space and should lead to a better performance, whatever the generic MDP solver used afterwards. Furthermore, by construc- tion, the equivalence classes are in one-to-one correspondence with the states in S, so that the new MDP can be formulated on that space directly.
MDP (the quotient of the original one by the bisim-
Application to the TSP, CVRP and KP Let & be the mappings from TSP-MDP states (TSP states for short) into new objects called "path-TSP" TSP" states, informally described by the following diagram:
stgo
path-TPP
The inner nodes (black diamonds) on the red path of visited nodes in the TSP state removed, leaving only the two ends of the red path which constitute two distinguished nodes in the path-TSP state. Mapping & has been designed to satisfy equation 3 so it induces bisimulation on TSP-MDP (see Figure T. and TSP-MDP can be turned into an equivalent "path-TSP-MDP on path-TSP states. This path- path-TSP--M TSP-MDP can be viewed as solving a variant of the TSP known as path-TSP, hence its name. However it is not the naive MDP for that variant since it forgets as it progresses, while naive MDPs always accumulate.
With the CVRP, we define step as the pair of a node and binary flag specifying whether that node is reached via the depot or directly. We can define mapping 4 similarly to the TSP case, except it is not sufficient to summarize the "past" (the visited nodes) by just the two ends of their path: to guarantee Ban the bisimulation property, an additional piece of information must be preserved from the past, namely the remaining capacity the end of the current path. For the KP, intuitively, the summary of the "past" is captured by the remaining items and the remaining knapsack capacity. This idea can be leveraged design bisimulation. Formal descriptions of the specifications and bisimulation quotienting for the CVRP and KP are provided in Appendices A and B respectively.
NEURAL ARCHITECTURE FOR PATH-TSP
Model We now describe our proposed policy network for the path-TSP-MDP above. Figure (Appendix) provides a quick overview. The models for path-CVRP and BQ-KP differ only slightly and are presented in Appendix A and B Most neural models for TSP utilize an encoder-decoder architecture, in which the encoder computes a representation of the entire graph once, and the decoder constructs a solution by taking into consideration the representation and the partial solution, e.g. Attention Model (Kool et al. 2019). or PointerNetworks (Vinyals) cet al., 2015). In our case, the path-TSP TSP formulation allows us to forget the nodes in the graph that have already been visited, except the distinguished origin and destination nodes. As corollary,
the whole graph
5

---

Under review as a conference paper at ICLR 2023
it also requires re-encoding the remaining nodes at each prediction step hence removing the need for a separate auto-regressive decoder. To encode a path-TSP state, we use a Transformer model (Vaswani et al. 2017). Each node is represented by its (z. coordinates, so that the imput feature matrix for an N-node state is an X matrix. We emhed these features via a linear layer. The remainder of the encoder is based on Vaswani et al.] (2017) with the following differences. First, we do not use positional encoding since the input nodes have no order. Instead, we learn an origin (resp. destination) embedding that is added to the feature embedding of the origin (resp. destination) node. Second, we use ReZero (Bachlechner et al. 2021) normalization, which leads to more stable training and better performance in our experiments (see ablation study in Appendix (D). Finally, a last linear layer projects the encoder's 's output into vector of size N, from which unfea- sible 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.
Training We train our model by imitation of expert trajectories, using plain cross-entropy loss (behaviour cloning). Such trajectories are extracted from pre-computed optimal (or near optimal) solutions for instances of (relatively small) fixed size. Note that (optimal) solutions are not directly in the form of trajectories. Equation 2a guarantees that a trajectory exists for any solution, but is usually far from unique. Besides, optimal solutions are costly, so we seek make the most out of each of them. In the TSP case, we observe that given an optimal tour, any sub-path of that tour is also an optimal solution to the associated path-TSP sub-problem, hence amenable to our path- 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 the same n for all the minibatch entries so as to simplify batching from the initial solution set. For the CVRP, the procedure is similar, except that, first, the extracted sub-paths must end at the depot, and, second, they can follow the sub-tours of the full solution in any order. We observed experimentally that the way that order is sampled has an impact on the performance (see Appendix
Complexity Because of the quadratic complexity of self-attention. and the fact that we call our model at each construction step, the total complexity is O(N3 where N is the instance size. Note that closely related Transformer-baste based models such as the TransformerTSP (Bresson & Laurent 2021) and the Attention Model (Kool et al. 2019) have total complexity of O(N" At each deciston step, for t remaining nodes, our model has a budget of O(P) compute whereas previous models only spend O()). We believe that this is useful inductive bias, which enables better generalization in particular for larger problem sizes. This hypothesis is supported by the fact that replacing the self-attention component with a linear time alternative (i.e., spending O(t) operations per step) drastically degrades the generalization ability to larger instances, as we show in Appendix D
Summary By reformulating TSP-MDP into Path-TSP-MiN the state is made to contain only very concise summary of the "past" of partial solution (how it was formed) as two distinguished nodes, but sufficient to determine its "future" (how it can be completed). Furthermore, at train time, we sample optimal solutions and associated path-TSP states amongst all the possible infixes of solutions of full problems. These proposed modifications go hand-in-hande Thanks to the transformation to 1ith-TSP-MDD our model enables better generalization in two important ways: (i) Due to encoding at each step, the encoder produces a graph representation that is specific to the current path-TSP-MDD MDD state. Graphs in these states vary in size and distribution, implicitly encouraging the model to work well across sizes and node distributions, and generalize better than if such variations were not seen during the training. In this regard, our model is similar the SW-AM model (Xin) et al. 2021c), except that they only approximate the re- re-embedding process in practice. (ii) By sampling subsequences from our training instances, we automatically get an augmented dataset, which some previous models had to explicitly design their model for (Kwon et al. 202T).
I Moore precisely, the complexity is proportional to ΣN 12 N(N + 1)(2N + 1)/6 hence the ( After an encoder of complexity O(N2), the decoder has linear complexity O(N - -t) step t.

---

Under review as a conference paper at ICLR 2023
5
RELATED WORK
NCO approaches Many NCO approaches construct solutions sequentially, via auto-regressive models. Starting with the seminal work by Vinyals et al. (2015), which proposed the Pointer network that was based on RNNs and trained in supervised way, Bello et al. (2017) trained the same model by RL for the TSP and Nazari et al. (2018) adapted it for the CVRP. Kool et al. (2019) introduced an attention-based encoder-decoder architecture (AM) trained with RL to solve several variants of routing problems - which is reused by Kwon et al. (202T) along with a few extensions |Bresson (POMO). TransformerTSP Bresson & Laurent (2021) use similar architecture with different decoder on TSP problems. Another line of works is concerned with directly producing a heat-map of solution segments: NNwak al. (2018) trained Graph Neural Network in supervised manner to output an adjacency matrix, which is converted into a feasible solution using beam search. Joshi et al. (2019) followed a similar framework and trained deep Graph Convolutional Network instead, that was used by (Fu et al. 2020) as well.
Step-wise methods methods/Peng et al. (2020) first pointed out the limitation of the original AM (Kool et al. 2019) approach in representing the dynamic nature of routing problems. They proposed to update the encoding after each subtour completion for the CVRP. [iin et al. (202Tc) proposed similar step-wise strategy but the encodings recomputed after each decision. In practice, their architecture the most similar ours for the TSP. However, thanks to our principled MDP transformations based on bisimulation quotienting, we obtain a superior representation for CVRP: In contrast to our approach, their CVRP architecture only provides censored information by omitting the remaining vehicle capacity and simply restricting the state to the nodes whose demand is below the remaining capacity. Xin et al. (202Tb) extended on this idea by proposing the Multi-Decoder Attention Model (MDAM) that in particular contains special layer to efficiently approximate the re-embedding process. As MDAM constitutes the most advanced version, we employ it as a baseline in our experiments.
Generalizable NCO Generalization to different instances distributions, and esp. larger instances, is regarded as one of the major limitations of current NCO approaches (Joshi et al. [0022] Mazyavkina cet al. 2020). Fu et al. (2020) trained a Graph Convolution model a supervised manner on small graphs and used it to solve large TSP instances, by applying the model on sampled subgraphs and us- ing an expensive MCTS search to improve the final solution (Att-GCN) MCTP) 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. (002)) investigate the robustness of NCO solvers through adversarial attacks and find that existing neural solvers are highly non-robust. to out-of-distribution examples. They conclude that one way to address this issue is through adver- sarial training. In particular, Xin et al. (2021a) trains GAN to generate instances that are difficult to solve for the current model. Manchanda et al. (2022) take different approach and leverage meta- leamning to learn a model in such a way that is easily adaptable to new distributions. Accounting for symmetries in given CO problem is a powerful idea to boost the generalization performance of Knn
neural solvers. Both Kwon et al. (202T) and Kim et al. (2022) make use of solution symmetricity as part of their loss function during training. Problem instance symmetry can be used at training time to augment the dataset (Kwon et al. 2022] or enforce robust representations (Kim et al. 2022). or can be used at inference time to augment the set of solutions (Kwon et al. 2021).
Please note that all of the above are orthogonal to our approach: rather than augmenting data or changing the training paradigm, our approach simplifies the state space by transforming the MDP, which has beneficial effects irrespective of the method of training.
6 EXPERIMENTS
To verify the effectiveness of our method, we test it on TSP, CVRP and KP. This section presents experimental results for TSP and CVRP, while results for KP are presented in Appendix
We train our model and all baselines synthetic TSP and CVRP instances of size 100, generated as in Kool et al. (019). 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 evaluate trained models on synthetic instances of size 100, 200, 500 and 1K generated from the same distribution, well as the standard TSPL. and CVRPLib datasets.
7

---

Under review as a conference paper at ICLR 2023
Hyperparameters and training procedure We use the same hyperparameters for all problems. The model has 9 layers, each built with 8 attention heads with embedding size of 128 and dimension of feed-forward layer of 512. Our model is trained on I million instances with 100 nodes split into batches of size 1024, for 1000 epochs. Solutions of these problems are obtained by using the
Concorde solver (Applegate et al.] (213) for TSP and LKH heuristic (Helsgaun (017) for CVRP.
We use Adam (Kingma & Bal 2017) as optimizer with an initial learning rate of 7.5e-4 4 and decay of 0.98 every 20 epochs.
Evaluation We compare our model with existing state-of-the-an art methods: OR-Tools (Perron & Furnon 2022), LKH (Helsgaun, 2017), and Hybrid Genetic Search (HGS) for the CVRP (Vidal 2022) as traditional non-neural methods; At-GGNNMCTS and NeuralRewriter (Chen & Tian 2019 as hybrid methods for TSP and CVRP respectively; and deep learning-
constructive methods: AM, TransforerrSS. MDAM and POMO, which were discussed in Section 5 For all deep learning baselines we use the model trained on graphs of size 100 and the best decoding strategy. Following the same procedure as in Fu et al. (2200) 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 the optimality gap and the inference time. The optimality gap for TSP is based solutions obtained with Concorde. For CVRP, although HGS gives better results than LKH, we use the LKK solution as reference compute the "optimality" gap, in order to be consistent (and easily comparable) with previous works. While the optimality gap is easy to compute and compare, measurements of running times are much harder: they may vary due to the implementation platforms (Python, C++), hardware (GPU, CPU), parallelization, batch size, etc. Therefore, we also report the number of solutions generated by each of the constructive deep learning models. 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-2670 with 256GB memory, in one thread.
the Euclidian space. For all models, we report
the optimal
Results Tables and Tb summarize our results on TSP and CVRP, respectively. For both problems, our model shows superior generalization on larger graphs, even with the greedy decoding strategy, which generates only a single solution while all others generate several hundreds (and select the best among them). In terms of running time with greedy decoding, our model is competitive with the POMO baseline, and significantly faster than other models. Beam search decoding with beam size 16 further improves the quality of solutions, but as expected, it takes approximately 16 times longer. Figure shows optimality gap versus running time for our model and other baseline models. Our model clearly outperforms other models in terms of generalization to larger instances. The only model that is competitive with ours is ACt-GCN+MCTS, but it is 2-15 times slower and is designed for TSP only. In addition to synthetic datasets, we test our model on TSPLib and VRPLib instances, which are of varying graph sizes, node distributions, demand distributions and vehicle capacities. Table [c| shows our model's strength over MDAM and POMO, even with the greedy decoding strategy. The effectiveness of our MDP transformation method and the resulting neural architecture is confirmed by the results. Thanks to our more principled approach that leads to better state representations and a simpler architecture without a decoder, by generating a single solution, it is able to outperform MDAM (with 250 solutions), which is closest to our model conceptually. Moreover, an ablation study in Appendix(Dsuugeene suggests that spending appropriate amounts of compute for each subproblem is crucial factor in our model.
7 CONCLUSION
We have presented flexible framework to derive MDPs that sequentially construct solutions to CO problems. Starting from a naive MDP, we introduced generic transformation using bisim- ulation quotienting, which reduces the state space by leveraging its symmetries. We applied this transformation on the TSP and CVRP, for which we also designed a simple attention- model, well-suited to the transformed state representation. We show experimentally that this combination of state representation, simple model, and training procedure yields state-of-the-an generalization re- sults diverse benchmarks. While training on relatively small instances allowed to use imitation learning, our approach and model could be similarly used with reinforcement learning. Finally, we have focused on deterministic CO problems, leaving the adaptation of our framework stochastic problems as future work.
8

---

Under review as a conference paper at ICLR 2023
Table 1: Summary of the experimental results. The bold values represent the best optimality gap (lower better) and fastest inference time. The underlined cells represent the best ratio between the quality of the solution and the inference time. #s refers to number of generated solutions.
#s
TSPI00
TSP200
TSP500
TSP1000
Concorde OR-Tools
0.000%
38m
0.000%
2m
0.000%
40m
0.000%
2.5h
3.765%
1.1h
4.516%
4m
4.891 %
31m
5.021%
2.4h
Att-GCN+MCTS*
0.037%
15m
0.884%
2m
2.536%
6m
3.223%
13m
AM bs 1024
1024
2.510%
20m
6. 6.176%
mm
17.978%
8m
29.750%
31m
TransTSP 1024
1024
0.456%
51m
5.121%
1m 36.142%
9m
76.215%
37m
MDAM bs50
250
0.395%
45m
2.044%
3m
9.878%
13m
19.965%
1.1h
POMO augx8
8N
0.134%
1m 1.572%
5s
20.182%
1m 40.603%
10m
BQ (ours) greedy
0.540%
1m
0.793%
5s
1.425%
1m 2.335%
7m
BQ (ours) bs16
16
0.032%
18m
0.166%
1m
0.682%
15m
1.311%
1.8h
(a) Experimental results on TSP.
Wee could not run AI--GCN+MCTS code on our architecture so we report
results from the original paper.
#s
CVRPI00
CVRP200
CVRP500
CVRP1000
LKH HGS
0.000%
15.3h
0.000%
30m
0.000%
1.3h
0.000%
2.8h
-0.510%
15.3h
-1.024%
30m
-1.252%
1.3h
-1.104%
2.8h
OR-Tools
9.617%
15.3h
10.700%
30m
11.403%
1.3h
13.559%
2.8h
NeuRewriter
3,456%
1.1h
29.460%
9m
25.051%
32m
29.542%
1.8h
AM bs 1024
1024
4.180%
24m
7.786%
Im
16.964%
8m
86.410%
31m
MDAM bs50
250
2.206%
56m
4.332%
3m
9.994%
14m
28.015%
1.4h
POMO augx8
8.V
0.689%
1m 4.767%
58
20.575%
1m
141.58%%
10m
BQ (ours) greedy
4.832%
1m 3.723%
5s
3.429%
Im 6.809%
7m
BQ (ours) bs16
16
1.798%
18m
1.375%
Im
0.817%
15m
2.048 %
1.8h
(b) Experimental results on CVRP. "We could not reproduce reported results NeuRewriter, so for
CVRP100 we report results from the original paper and for other sizes we report the best result we got.
MDAM
POMO
BQ (ours)
MDAM
POMO
BQ (ours)
Size
bs50
x8
greedy
bs16
Set (size)
bs50
augx8
greedy
bs16
(32-80)
6.17%
4.86%
5.85%
1.96%
<100
3.06%
0.42%
0.38%
0.06%
(30-77)
8.77%
5.13%
7.04%
3.50%
100-200
5.14%
2.31%
2.82%
1.61%
(44-134)
16.96%
15.49%
7.20%
3.04%
200-500
11.32%
13.32%
3.31%
2.07%
(100-200)
5.92%
4.99%
6.69%
1.85%
500-1K
20.40%
31.58%
10.08%
3.04%
(15-100)
8.44%
14.69%
4.71%
1.32%
> 1K
40.81%
62.61% %
11.87%
8.61%
(100-1K)
34.17%
21.62%
10.74%
8.35%
All
19.01 56
26.30%
6.22%
3.94%
All (15-TK)
22.36%
15.58%
8.58%
5.60%
(c) Experimental results TSPLib (left) and CVRPLib (right).
AM bs1024
TSP100
140
AM bs1024
CVRP100
MDAM bs50
TSP200
MDAM bs50
CVRP200
POMO augx8
TSP500
120
POMO augx8
CVRP500
Att-GCN+ MCTS
MCTS
TSP1000
NeuralRewriter
CVRP1000
BQ (ours) greedy
BQ (ours) greedy
100
BQ (ours) bs16
Optimality gap
BQ (ours) bs16
80
60
40
L0
10
10-2
10
100
10
10"
10
10-1
10
Inference time (per Instance, in seconds)
Inference time (per Instance, In seconds)
Figure 2: Generalization results on different graph sizes for TSP (left) and CVRP (right). Lower and further left is better.

---

Under review as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
In order to ensure the reproducibility of our approach, we have:
described precisely our generic theoretical framework (Section 2 and provided detailed proof of Proposition in Appendix F This should in particular serve adapt the frame- work to other CO problems;
explained in detail our proposed model (Section 4 for TSP and Appendix A for CVRP),
described precisely the training procedure and listed the hyperparameters (Section
used public datasets referenced in Section
Furthermore, we plan make code public upon acceptance.
REFERENCES
David Applegate, Robert Bixby, Vasek Chvatal, and William Cook. Concorde TSP solver. Univer- sity of Waterloo, 2015.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. Layer Normalization, July 2016.
Thomas Bachlechner, Bodhisattwa Prasad Majumder, Henry Mao, Gary Cottrell, and Julian McAuley. ReZero is all you need: Fast convergence at large depth. Proceedings of the Thirty- Seventh Conference Uncertainty in Artificial Intelligence, pp. 1352-1361. PMLR, December 2021.
Irwan Bello, Hieu Pham, Quoe V. Le, Mohammad Norouzi, and Samy Bengio. Neural Combinato- rial Optimization with Reinforcement Learning. 1XXv:1611.00944 [es, stat], January 2017.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial opti- mization: A methodological tour d' d'horizon. European Journal of Operational Research, 290(2): 405-421, 2021.
Ilhem Boussaid, Julien Lepagnot, and Patrick Siarry. A survey on optimization metaheuristics. Information Sciences, 237:82-117, July 2013. ISSN 0020-0255. doi: 1tt.:ij.inn.211.02.000
Xavier Bresson and Thomas Laurent. The Transformer Network for the Traveling Salesman Prob- lem. arXiv:2103.03012 [cs], March 2021.
Quentin Cappart, Didier Chételat, Elias Khalil, Andrea Lodi, Christopher Morris, and Petar Veličkovié. Combinatorial optimization and reasoning with graph neural networks. arXiv:2102.09544 [cs, math, stat], February 2021.
Xinyun Chen and Yuandong Tian. Learning to Perform Local Rewriting for Combinatorial Opti- mization. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
William J. Cook, William H. Cunningham, William R. Pulleyblank, and Alexander Schrijver: Com- binatorial Optimization. Wiley-Interscience, New York, 1st edition edition, November 1997. ISBN 978-0-471-558944
Zhang-Hou Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize a Small Pre-trained Model to Arbitrar- ily Large TSP Instances. 20X2::2012.10653 [cs]. December 2020.
Simon Geisler, Johanna Sommer, Jan Schuchardt, Aleksandar Bojchevski, and Stephan Günneemann. Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness, March 2022.
Robert Givan, Thomas Dean, and Matthew Greig. Equivalence notions and model minimization in Markov decision processes. Artificial Intelligence, 147(1):163-2) 223,, July 2003. ISSN 0004-3702. doi: 10.
10

---

Under review as a conference paper at ICLR 2023
Keld Helsgaun. An Extension of the ing Salesman and Vehicle Routing Problems. Technical report, Roskilde University, Roskilde, Denmark, 2017.
TSP Solver for Constrained Travel-
Sergey loffe and Christian Szegedy. Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift. In Proceedings of the 32nd International Conference Machine Learning, pp. 448-456. PMLR, June 2015.
Chaitanya K. Joshi, Thomas Laurent, and Xavier Bresson. An Efficient Graph Convolutional Net- work Technique for the Travelling Salesman Problem. arXiv: 01227 [cs, stat], June 2019.
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, doi: 10. 11863/CAMM.81177
April 2022. ISSN 1383-7133.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning Combinatorial Opti- mization Algorithms over Graphs. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, Curran Associates, Inc., 2017.
pp. 4348-6358.
Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization, May 2022.
Diederik P. Kingma and Jimmy Ba. Adam: A Method for Stochastic Optimization, January 2017.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, Learn to Solve Routing Problems! In International Conference on Learning Representations, 2019.
Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seung- jai Min. POMO: Policy Optimization with Multiple Optima for Reinforcement Learning. arXiv:2010.1601 16011 [cs], July 2021.
Florian Mai, Arnad Pannatier, Fabio Fehr, Haolin Chen, Francois Marelli, Francois Fleuret, and James Henderson. HyperMixer: An MLP-based Green AI Alternative to Transformers, March 2022.
Sahil Manchanda, Sofia Michel, Darko Drakulic, and Jean-Mare Andreoli. On the Generalization of Neural Combinatorial Optimization Heuristics. In European Conference Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML-PKDD), Grenoble, France, September 2022.
Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement Learning for Combinatorial Optimization: A Survey. arXiv:2003.03600 [cs, math, stat], March 2020.
MohammadReza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takac. Reinforcement Learning for Solving the Vehicle Routing Problem. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
Alex Nowak, David Folqué, and Joan Bruna. Divide and Conquer Networks, In 6-Th International Conference on Learning Representations, Vancouver, Canada, April 2018.
Bo Peng, Jiahai Wang, and Zizhen Zhang. A Deep Reinforcement Learning Algorithm Using Dy- namic Attention Model for Vehicle Routing Problems. arXiv:2002.03288 [cs, stat], February 2020.
Laurent Perron and Vincent Furnon. OR-tools. Google, 2022.
Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler. Efficient Transformers: A Survey. ACM Computing Surveys, April 2022. ISSN 0360-0300. doi: 1053345/353
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention Is All You Need. 1rXiv:1706.0377 [cs], June 2017.
11

---

Under review as a conference paper at ICLR 2023
Thibaut Vidal. Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood. Computers Operations Research, 140:105643. April 2022. ISSN 0305-0548. doi: 10.10166j.c02222110555..
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer Networks. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Pro- cessing Systems 28, pp. 2692-2706 Curran Associates, Inc., 2015.
Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Generative Adversarial Training for Neural Combinatorial Optimization Models, September 2021a.
Liang Xin, Wen Song. Zhiguang Cao, and Jie Zhang. Multi-Decoder Attention Model with Embed- ding Glimpse for Solving Vehicle Routing Problems. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 1352 1361. PMLR, May 2021b.
Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Step-Wist Deep Learning Models for Solving Routing Problems. IEEE Transactions on Industrial Informatics, 17(7):46114471,, July 2021c ISSN 1941-0050. doi: 10.1109971..00233331449.
Cong Zhang, Wen Song, Zhiguang Cao, Jie Zhang, Puay Siew Tan, and Chi Xu. Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning. arXiv:2010.12367 [cs, stat], October 2020.
12

---

Under review as a conference paper at ICLR 2023
A APPLICATION TO THE CVRP
Problem definition and specification The Capacitated Vehicle Routing Problem (CVRP) is a vehicle routing problem in which vehicle (here, single one) with limited capacity must deliver items from a depot location to various customer locations. Each customer has an associated demand, which represents an amount of items, and the problem is for the vehicle to provide all the customers in the least travel distance, returning as many times as needed to the depot to refill, but without ever exceeding the vehicle capacity.
Formally. we assume given a set of customer nodes, each with a demand (positive scalar), plus a depot node. A CVRP solution (in X²) is a finite sequence of nodes starting at the depot, which are pairwise distinct except for the depot, and respecting the capacity constraint: the total demand of any contiguous aub-sequence of customer nodes is below the vehicle capacity. CVRP instance (in F) is given by finite set D of nodes, including the depot, their coordinates in the Euclidian space V. and maps any solution to the length of the corresponding path using the distances in V, the path visits exactly all the nodes of D, or otherwise (unfeasible solutions).
A possible specification (T, SOL, VAL) for the CVRP is defined as follows. The step space T is the set of pairs of a non depot node and binary flag indicating whether that node is to be reached via the depot or directly. The extension i of a step is either the singleton of its node component if its flag is 0 or the pair of the depot node and its node component if its flag is 1. For a given problem instance f and sequence fim of steps, SoL(f. which visits exactly all the nodes of f or L otherwise. VAL(f, (1:)) ) is either the total length of 11.. (closed at its end) if it forms a d-path which visits only nodes of f (maybe not all), or oo otherwise. It is easy to show that (T, SOL, VAL) forms a specification for the CVRP (i.e. satisfies the axioms of specifications introduced in Section 2 The naive MDP obtained from it is denoted CVRP-MDP.
is either the sequence f f it forms a d-path
Bisimulation quotienting Just as with TSP, we can define a mapping c from CVRP-MDP states to new "path-CVRP" state space, informally described by the following diagram.
CVRP state
path-CiVR state
/
C=110
C=3o
Here, the capacity of the vehicle is C=10, shown next to the (colourless) depot node, and the demand of each node shown next to it, in orange. The black dotted line indicates that the action which introduced the node with demand 2 was via the depot: its flag was set to I (all the other actions had their flag set to 0 in this simple example). The green dotted line indicates how the path is closed to measure its length. After the node with demand 2, the path of visited nodes (in red) continues with nodes with demand 4 and 1, respectively, so that the remaining capacity at the end of the path is C-(2+4+1)=3, Compared to TSP. this is the additional piece of information in the summary of the "past" (path of visited nodes) which is preserved in the path-CVRP state, together with the origin and destination of the path. Mapping & thus defined satisfies Equation 3] hence induces bisimulation on CVRP-MDP states, and by quotienting, one obtains an MDP which can be defined directly on path-CVRP states.
Model architecture for CVRP The model architecture for CVRP is almost the same as for TSP; with a slight difference in the input sequence and in the output layer. In the TSP model, the input to the node embedding layer for a --node state is 2x N matrix of coordinates. For CVRP, we use two additional channels: one for node demands, and one for the current vehicle capacity, repeated across all nodes. The demand is set to zero for the origin and destination nodes. We obtain 4x N matrix of features, which is passed through a learned embedding layer. As for TSP, a learned orggin-ignnallng (resp. destination destination-sinnallnng vector is added to the corresponding embeddings. The rest of the architecture, in the form of attention layers, is identical to TSP, until after the action scores projection layer. In the case of TSP, the projection layer returns vector of N scores, where each score, after
13

---

Under review as a conference paper at ICLR 2023
softmax, represents the probability of choosing the node as the next step in the construction. In the case of CVRP, the model returns a matrix of scores of dimension N x2, corresponding to each possible actions (node-flag pair) and the softmax scopes over this whole matrix. As usual, mask is always applied to unfeasible actions before the softmax operator: those which have higher demand than the remaining vehicle capacity, as well the origin and destination nodes.
B APPLICATION TO THE KNAPSACK PROBLEM
Problem definition and specification The Knapsack Problem (KP) is classical combinatorial op- timization problem in which we need to pack items, with given values and weights, into a knapsack with a given capacity. The objective is to maximize the total value of packed items. Formally, assume given set of items, each with a value and weight. A KP solution (in X) a subset of the items which respects capacity constraint ("c-subset"": total weight of the items of the subset must not exceed the knapsack capacity. A KP instance (in F) is given by a finite set of items and maps any c-subset the sum of values of its items.
A simple problem specification SOL, VAL.) can be defined as follows. The step space T is equal to the set of items, For partial solution (f, f1:)), if the selected items satisfy the capacity con- straints and adding any of the remaining items results in an infeasible solution, then SOL(f, tim) returns the subset of selected items; otherwise returns I. Finally, VAL(f, fim) is either the sum of the values of the items in f1:n if they satisfy the capacity constraint and co otherwise. Similarly the TSP and CVRP cases, it is easy show that (T, SOL, VAL) forms a specification for the KP. The naive MDP obtained from it is denoted MDP-KP.
Bisimulation quotienting As it was the case for TSP and CVRP, we can define mapping + from KP-MDP state to a new "BQ-KP" state space, informally described by the following diagram.
20
C
values
9
2
8
6
7
6
7
weights
3
7
9
5
8
8
4
5
8
KP-state
BQ-KP-state
Here, capacity of the knapsack is C = 20 and each item is defined by its weight (bottom cell) and value (top cell). Mapping & for KP is straightforward simply saying, it removes all picked items and update the remaining capacity by subtracting total weight of removed items from the previous capacity.
Model architecture for KP The model architecture for KP is again very similar to previously described models for TSP and CVRP. The input to the model is 3 N tensor composed of items properties (values, weights) and the additional channel for the remaining knapsack's 's capacity. By definition, the solution has order (the result is set of items), so there no need to add tokens for origin and destination. A part from excluding these tokens and different input dimensions, the rest of the model is identical to the TSP model. The output is a vector of N probabilities over all items with a mask over the unfcasible ones (with weights larger than remaining knapsack's 's capacity). In the training, at each construction step, any item of the ground-truth solution a valid choice. Therefore we use a multi-class cross-entropy loss.
Experimental results for KP We generate the training dataset as described in Kwon et al. (2021) We train our model on IM KP instances of size 200 and capacity 25, with values and weights ran- domly sampled from the unit interval. We use the dynamic programming algorithm from ORTools to compute the ground-truth optinal solutions. As hyperparameters, we use the same as for the TSP. Then, we evaluate our model on test datasets with the number of items equal 200, 500 and 1000 and capacity of 25 and 50, for each problem size. Table B shows the performance of our model compared to POMO, one of the best performing NCO models on KP. Although our model does not outperform it in every dataset, it achieves better overall performance. It should be noted again that POMO builds N solutions per instance and choose the best one, while our model generate a single solution per instance but still achieves better results.
14

---

Under review as a conference paper at ICLR 2023
Optimal value
POMO (single traj.)
POMO (all traj.)
BQ (greedy)
value
opt gap
value
opt gap
value
opt gap
N=200
C=25
58.023
57.740
0.476%
58.007
0.017%
57.970
0.08 I %
C=50
80.756
79.483
1.544%
79.787
1.170%
80.710
0.056%
N=500
C=25
90.986
85.309
6.217%
86.516
4.897%
90.150
0.904%
C=50
129.326
128.950
0.291
129.272
0.042%
128.369
0.739%
N=1000
C-25
128.692
120.757
5.386%
123.572
3.973%
121.217
5.808%
C=50
182.898
170.920
6.545%
172.427
5.724%
175.093
4.267%
All
3.552%
2.648%
1.980%
Table 2: Experimental results on KP.
Greedy
Beam size 16
Beam size
64
Full graph 0.79%
5s
0.17%
1m
0.08%
5m
TSP200
100KNNs
1.31%
3s
0.23%
33s
0.10%
3m
Full graph 1.71%
1m
0.68%
15m
0.54%
1h
TSP500
100KNNs 2.58%
18s
0.92%
3m
0.69%
12m
250KNNs 1.56%
32s
0.67%
9m
0.53%
30m
Full graph
2.34%
7m
1.31% %
1.8h
1.19%
7.3h
TSP1000
100KNNs
3.34%
25s
1.69%
6m
1.45%
24m
250KNNs
2.53%
1m
1 1.43%
23m
1.19%
1.4h
Full graph
4.80%
5s
2.42%
1m
1.82%
5m
CVRP200
100KNNs
5. 5.18%
3s
2.12%
33s
1.68%
3m
Full graph
4.74%
Im
2.10%
15m
1.59%
1h
CVRP500
100KNNs
5.14%
18s
2.02%
3m
1.74%
12m
250KNNs 4.58%
32s
1.86%
9m
1.14%
30m
Full graph
8.00%
7m
3.19%
1.8h
2.39%
7.3h
CVRP1000
100KNNs
8.25%
25s
4.76%
6m
3.58%
24m
250KNNs
7.51%
1m
3.08%
23m
2.28%
1.4h
Table 3: Improving the model performance using k-nearestt-eiighoor heuristic.
C IMPROVING THE MODEL PERFORMANCE WITH A k-NEAREST-NEIGHBOR HEURISTIC
Our decoding strategy could be further improved by using a n-nearest-neighhbrr heuristic restrict the search space and reduce the inference time. For both greedy and beam search strategies, at every step, is possible to reduce the remaining graph by considering only a certain number of neighbouring nodes. Table presents the experiments on TSP and CVRP where we apply the model just on certain number on nearest neighbours of the origin. This approach clearly reduces the execution time, but also in some cases even improves the performance in terms of optimality gap- The same heuristic can be applied on Knapsack problem, where model could be applied just on certain number of items with highest values.
D ABLATION STUDY
D.I TRANSFORMER VS HYPERMIXER AS MODEL
In Section 6 we have shown that our model has an excellent generalization ability to graphs of larger size. In Section g we hypothesize that this has to do with the fact that subproblem of size spends (tt²) computation operations due to the quadratic complexity of the Transformer encoder's self-attention component, which is responsible for mixing node representations. To test this hypothesis, we experiment with replacing self-attention with an efficient mixing component (see Tay et al. (2022) for overview), namely the recent linear-ting time HyperMixer (Mai et al. 2022). We chose this model because does not assume that the input is ordered, unlike e.g. sparse attention alternatives.
15

---

Under review as a conference paper at ICLR 2023
Seed
TSPI00
TSP200
TSP500
TSPI000
I
2.10%
8.38%
34.91%
71.30%
2
1.38%
3.54%
98.59%
628.71%
3
1.93%
4.14%
120.18%
216.77%
4
1.37%
4.54%
46.23%
104.85%
5 1.25%
3.66%
61.99%
524.43%
Table 4: Experimental results on TSP with HyperMixer for five different seeds.
Experimental Details For comparability, we set the model and training parameters to the same as for Transformers, the experiments only differ in token mixing component that is used. The only other difference is that we used Layer Normalization Ba et al. (2016) instead of ReZero Bachlechner al. (202I). which leads more stable training for HyperMixer. Since we observed relatively large sensitivity to model initialization, we are reporting the results for 5 different seeds.
Results Table shows the result for HyperMixer with greedy decoding. While the model reaches lower but acceptable performance than Transformers TSP100, it generalizes poorly instances of larger size. Moreover, performance is very sensitive to the seed. These results suggest that the computation spent by self-attention is indeed necessary to reach the generalization ability of model, which increases the compute with the size of the (sub)problem.
D.2 APPROXIMATED MODEL
As mentioned in Section 5 existing works have also noted the importance of accounting for the change of the state after each action: Xin et al. (2021c b) claimed that models should recompute the emheddings after each action. However because of the additional training cost, they proposed the following approximation: fixing lower encoder levels and recomputing just the top level with mask of already visited nodes. They hypothesis a kind of hierarchical feature extraction property that may make the last layers more important for the fine- mee-igri next decision. In contrast, we call our entire model after each construction step; effectively recomputing the embeddings of each state. We hypothesis that this property may explain the superior performance (Table 1) w.r.t MDAM model et al. (b021b). In order to support this hypothesis, we have implemented an approximated version of our model as follows. We fixed the bottom layers of our model and recomputed just the top layer, by masking already visited nodes and adding the updated information (origin and destination tokens for TSP). As expected, inference time 1.6 times shorter, but performance is severely degraded: we obtained optimality gap of 9.833% (vs 0.540% with original model) TSP100.
D.3 REZERO BATCHNORM AS NORMALIZATION
Most NCO works that transformer networks KKol et al. 2019 K won et al. 2021) (Xin et al. 2021b) use batch normalization & Szegedy 2015) rather than layer normalization (Ba et al, 2016) in attention layers. We find ReZero normalization Bachlechner al. 2021) work even bet- ter. Figure shows the effect of using ReZero compared to batch normalization in our Transformer network. Using it leads to more stable training, better performance, and drastically lower variance between seeds.
E ON THE IMPACT OF EXPERT SOLUTIONS
Our datasets consist of pairs of problem instance and a solution (tour). On the other hand, in this paper, we use imitation learning, which requires instead pairs of problem instance and (expert) trajectory in the MDP. Now, solution may be obtained from multiple trajectories in the MDP. For example, with TSP, a solution a loop in a graph, and one has to decide at which node its construc- tion started and in which direction it proceeded. With CVRP, the order in which the subtours constructed needs also to be decided. Hence, all our datasets are pre-pon pre-processed to transform solu- tions into corresponding construction trajectories (a choice for each experimentally observed that this transformation has an impact on the performance. For example, with CVRP, choosing, for each solution, the construction in the order in which LKH3 displays it,
all possible ones). We
16

---

Under review as a conference paper at ICLR 2023
BatchNorm, seed
BatchNorm, seed 1
ReZero, seed 0
20
ReZero, seed 1
Optimality gap
15
10
5
0
400
600
800
1000
Epochs
Figure 3: Training curves showing the effect of the choice of normalization layer on validation performance
which does not seem arbitrary, yields to 1.3 point better opt-gap performance compared to following random ordering of the sub-tours. We hypothesize that if there is any bias in the display of the optimal solution for example, shorter tour first, closest node first it requires slightly less model capacity learn action imitation for this display rather than for all possible displays.
F PROOF OF PROPOSITION (SOUNDNESS OF THE NAIVE MDP)
We show here that procedure SOLVE satisfies SOLVE(J)= arg minnex f(x). We first show the following general lemma:
Let y S (RUCOO) be arbitrary mappings, s is surjective then
arg min argmin #Ex f(x) (arg min ((()))
yey
Simple application of the definition of arg min (as a set). The subscript denotes the steps where the assumption that & a surjection is used:
x' E (arg min f(v()))) iff
By E arg min f(v(w)) x' v0/)
By' x' v'y') Vy f(b(y)) S f(v(v)) iff By z' v((') Vy f(z') s f(v(v)) iff. Yy f(z') s f(v(v)) iff. Va f(z)
iff
iff x' arg min f(x)
Let (F,X)) x be CO problem with specification (T, VAL) and M the naive MDP obtained from it. For each feF, let =y= e), (xE (x))) and let y/ be the set of M-trajectories which start (f)e) and end stop state.
17

---

Under review as a conference paper at ICLR 2023
softmax
Linear
Transformer encoder
ReLU normalization
dest. emb.
arigin emb.
input embedding layer
(xr,))
(a,, 1/%
(2.00
Figure 4: Computation flow the 1-th time step, when partial solution of length 1 already exists. The input state consist of the destination node (i.e. the first and last node in the TSP tour), the origin node (i.e., the most recent node in the tour), and the set of remaining nodes. After passing all input nodes through an embedding layer, we add special, learnable vector embeddings to the origin and current node signal their special meaning. Finally, Transformer encoder followed by a linear classifier head selects the next node at step
For any M-trajectory S=stg/is11 ... tnnns in Y/,, define vb(T) =der SOL(S,). Since reVr, f. have (f and 8n is stop state, i.e. (OI((s)==(TTEZ,, and by Equa- tion 2a (()(T))<oo. Hence w:yy + Xz.
By construction, mm= f1mm for meL: and each transition in has a finite reward (condition for it to be valid). Hence the cumulated reward is given Now, VAL(s))=Ug which independent and by Equa-
by R(T)= (oo--AAL))-V-(((( tion 2c VAL (f(())) Henee ((((T))=oy-R()
Let's show that s is surjective. Let zEX,, Equation 2a ensures that z=SOL(f, t1m) for some ET= For each m0:): let sm=(f. L 1:om) and consider the sequence hence ends in stop state and starts at (f.c). By Equation we we have VAL = f(x). hence VAL(s,, ( and vAL(s <oo for all me (0: And And by Equation 2b (S )= hence all the transitions in are valid in M. Hence T and by definition, (b(T)=
T=sut1r111 ..,,,,, S... Now, cOL(s))=155
Therefore we can apply the lemma proved above:
arg min zEX, f(x) barr min [(v(T))) (arg min uy R(()) rEV,
rEl; (arg max R(7)) (SSLLVE (f.c)) SOLVE(F) rEV,
Now, obviously, arg mingex ((x) = arg millgex, f(x), since by definition is infinite on X²)
18

---

Under review as a conference paper at ICLR 2023
G PLOTS OF SOME TSPLIB AND CVRPLIB SOLUTIONS
[3] Optimal solution
Our model (8516). opt 0.549%
(C) MOAN (8550), Dap 31.501%
(4) PONO (xl). ott_gap 18.14%
Instance pr1002
Optimal solution
model (BS16). on 4.235
1/1 MINA (ACON) can 30 S1AG.
1411 POWO (od) and nan PAASS
19

---

Under review as a conference paper at ICLR 2023
Instance X/2284 k15
Optimal solition
model (8516), opt ggg
1O NOAM (8550), opt.ap 45.669%
(d) POMO (XB1, apt_aap 11,416%
Instance X-n513-k21
(a) Dest
model (8516),
NDAM (8550),
20

---

Under review as a conference paper at ICLR 2023
H BACKGROUND ON
H.1 BISIMULATION IN LABELLED TRANSITION SYSTEMS
Bisimulation is very broad concept which applies to arbitrary Labelled Transition Systems (LTS). has been declined in various flavours of LTS, such as Process Calculi, Finite State Automata, Game theory, and of course MDP (initially deterministic MDP such as those used here, later extended to stochastic MDP which we are not concerned with here). A bisimulation is binary relation R among states which "commutes" with the transitions of LTS in the following diagram, which should informally be read as follows: if the pair of arrows connected to (resp. exists then so does the "opposite" pair (w...t the centre the diagram).
L
p
p'
RL
R
t.
q'
The notation - p' means the transition from p to p' with label is valid. Thus, formally, Definition 1. A binary relation R. on states is bisimulation if for all label and states p, q such that pRq
dp' s.t. p - p' Ed s.t. q - o. p'Rq'
Val s.1. 9 2 of 3p' S.t. - p' p'Rq
Note that this definition extended to the "heterogeneouss" case where R. is bi-partite, relating the state spaces of two LTS L1, L2 sharing the label space. One just forms whose state space is the disjoint union of the state spaces of L1, L2 and the transitions are those of L1, C2 in their respective (disjoint) component. An heterogeneous bisimulation L1, C2 then (homogeneous) bisimulation on L. Most results below also have a heterogeneous version.
LTS L
Proposition 2. The set of bisimulations (subset of the set of binary relations on states) is stable by union, composition, and inversion, hence also by seffexive-ymmmetrii-traan trannstircttransiiivve closure.
In particular, the union of all bisimulations, called the bisimilarity of the LTS, is itself a bisimulation, and it also an equivalence relation.
Proof. (outline) Let's detail stability by composition. the other cases similarly obvious. If R1, R2 are the two bisimulations being composed, apply the commutation property to each cell of the following diagram (from top bottom).
p'
R1
Ri
+
r
x
rl
R₂
Rs
g'
Definition 2. Given an LTS L, its transitive closure is another LTS denoted L on the same state space, where the labels are the sequences of labels of L and the transitions are defined by
p bim p if 3oon such that p = Po
81
En-1
ln Pm. = p
p
Pn-1
(C*)
(C)
(C)
(C)
Proposition 3. R is a bisimulation on L. then it is also bisimulation L*
Proof. (outline) This is essentially shown by successively applying the commutation property to each cell of the following diagram (from left to right):
21

---

Under review as a conference paper at ICLR 2023
ln
P0
pi
Pn-1
Pr.
R.
1
R4
R
R
L
ln
y q1
9n-1
9n
Definition 3. Given an LTS C and an equivalence relation on its state space, can define the quotient LTS C/R with the same label space, where the states are the R-equivalence classes and the transitions are defined. for any classes p. V, by
if ApEpEN'E P r
P
C/R
Proposition 4. Lei R be equivalence the state space of L. R is bisimulation on L if and only if a (heterogeneous) bisimulation on L, C/R.
Proof. We show both implications:
Assume is bisimulation on C.
Let p q and p S p'. Let q E q. Hence yięq and p S p'. Since R is a bisimulation, there exists q' such that 9 - g' and p'Rq'. Hence for all q E q, there exists of E F such that - q'. Hence by definition q - p' while p' E p'.
Let p E q and q & q'. Hence by definition, there exists p' E d' such that p S p'.
Assume E is (heterogeneous) bisimulation on C/
Let pRq and - p'. Hence q and p - p'. Since E is bisimulation, there exists j' such that p' E q' and 4 q'. Now E q. hence, by definition, there exists g' E q' such that - q'. And p'Ra' since p' E
Let pRq and 1 g'. Hence qRp and 4 d' and we are in the previous case up to permutation of variables.
Proposition 5. Let R be equivalence relation the state space of L. IfR is bisimulation C. then for any C-state p. R/R-state P and C -label
(C/R)* p and only if
3p' p'
c
Proof. Simple combination of Propositions and erogeneous bisimulation on C/R (Proposition hence also heterogeneous bisimulation on L" (C/R)* (Proposition heterogeneous version).
R is bisimulation on L. hence E is het-
p', since pEp and e is bisimulation, we have - for some p' E'p. If p (C/RY-
- p' for some p'e'', since pEp and is bisimulation, have π (C/RR)" o' and p Eÿ' for some q'. Now p' n'j hence =²= and (c/R)-
Conversely, -
1l
H.2 BISIMULATION IN DETERMINISTIC MDP
Definition 4. An MDP a pair T) where C LTS with label space R for some action space A (action-reward pairs denoted a)r) and T is subset of states (the stop states). It is said to be deterministic if
if alrs 8 and alrs on then ri T2 and 8/ 8/2
22

---

Under review as a conference paper at ICLR 2023
Given C-trajectory T, L.e. a sequence 80017181 ...... "nnnnnn where 8;-1 adlr, for all iE (1:n), its cumulated reward is defined by =(T)=>in ri. The generic problem statement of the MDP solution framework is, given MDP (L, and one of its states So. to solve the following optimi- sation:
SOLVE T), s,) arg max R(()) T a C-trajectory starting at so and ending in T
This definition of MDP and the standard textbook one coincide only in the deterministic case (in the standard definition, an MDP is deterministic if the distribution of output state-reward pairs for given input state and allowed action is "one-hot"), The non deterministic case in the definition above does not match the standard definition: it would be wrong interpret two distinct transitions for the same input state 8 and action a as meaning that the outcome of applying a to state s distributed between the two output reward-state pairs according in the problem statement, the objective R(T) has no expectation, which, with the standard definition, only makes sense in the case of deterministic MDP. Similarly, the standard problem statement is expressed in terms of policies rather than trajectories directly, but in the deterministic case, the two equivalent. Observe that there is one-to-one correspondence between trajectories in L and transitions in the LTS L so the problem statement can be formulated equivalently as
specific distribution (c.g. uniform). Also,
SOLVE ((C, T), 8n) = arg max R(E) 3s E T, 8,
(4)
Proposition 6. Let (C,T) be an MDP and R equivalence relation on its state space.
1. (C/R, is also MDP, where [=) and if L is deterministic, so is L/R.
2. IfR is bisimulation on & preserving T (i.e. USET 3= TT),, then for any stute so and label
L we have
E E T,80
E. i+ ifand only if 3$ E T,
(C/R)*
Proof. The second property is a direct consequence of Proposition and the assumption that T is preserved by R. For the first, assume that L deterministic. Let 8, $1, 82 be L/R states, such that Hence, by definition, there exist $yE and 82E82 such 81 and 8 alrz, 82. Since L is deterministic, we have r1=12 and 81 =1=2288 E& N&2, hence
alm 81 and á alrs 82. Choose
that 8 alrı $1 $2. Hence L/R is also deterministic.
Therefore, when R is a bisimulation equivalence on L preserving T, the generic MDP problem statement of Eq. equation caan be reformulated as
MDP ((C, T), so) = SOLVE: ((C/R, T), = arg max R(E) 3& E T,80 (C/R)"
(5)
Note that bisimulation on L preserving T is simply a bisimulation on the LTS É defined as follows: has the same state space as L and an additional transition + for each se T, where "." is distinguished label not present in C.
A bisimulation R on E captures some symmetries of the state space of É. If is taken be the bisimilarity of É. i.e. the union of all the bisimulations on L, i.e. the union of all the bisimulations on L preserving T, then it captures all the possible symmetries of the state space. This should be seen as an asymptotic result, since constructing and working with the full bisimilarity of C is not feasible. But Proposition o remains valuable as it applies all bisimulation, not just the maximal bisimulation of É (its bisimilarity).
23


Reviews:
[{"review_id": "zHsQpO_vq_", "reviewer": "Reviewer_B3kw", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "A step-wise neural CO algorithm is proposed, where the idea of bisimulation quotienting is used to define a state with the minimal but sufficient information. Authors mathematically formalize the solution-construction approach in CO problems and its MDP perspective (in Section 2). Then, the idea of bisimulation quotienting is introduced and how it is used to map TSP-MDP into path-TSP-MDP is discussed (in Section 3, with CVRP). With such formulation, a simple policy network that uses a Transformer (with slight modifications, e.g., removing PE) and is suitable for path-TSP-MDP (and its CVRP version) is proposed (Section 4), where the scalability of the model was empirically proven in a variety of experiments (Section 6). ", "summary_of_the_review": "The submission proposes an interesting symmetry perspective for constructive CO problems and shows impressive performance, which makes me vote for the acceptance of this work. ", "strength_and_weaknesses": "### Strength\n- Constructive approach in CO and its relation to MDP are rigorously defined. \n- Explanation on generalization based on bisimulation and bisimilarity is clearly stated. \n- Strong generalization performance is shown through multiple experiments across two different CO problem instances (TSP, CVRP).\n### Weaknesses\n- Problems are restricted into the Euclidean settings. The algorithm’s applicability to non-Euclidean, non-symmetric COs is unclear.\n- High computational complexity since pure Transformer is used. It was shown that using efficient Transformer techniques makes generalization performance poor.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "u0Z431vov9", "reviewer": "Reviewer_yAnE", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the problem of solving combinatorial optimization problems using reinforcement learning enhanced with bisimulation quotients, where the main idea is to reduce the search space by identifying states with identical paths in MDP. In particular, new models are designed for TSP and CVRP. The proposed methods are supplemented with experimental studies\n", "summary_of_the_review": "The paper presents an interesting idea but could do better in explaining its novelty by having more details. The overall contribution seems limited. \n", "strength_and_weaknesses": "Strength:\n\nThe overall idea is reasonable: capturing symmetries in the system is expected to reduce the required training efforts and thereby facilitate good generalization. Most of the sections are well-written (module the technical part), and the studied problem is well-motivated. The presented experimental results suggest that the proposed method is promising.\n\n\nWeaknesses:\n\n- W1: The presentation of this paper lacks mathematical rigor, which makes its technical contribution less clear. \n  - Is $T$ a set of steps or a set of sequences of steps? Is $T^*$ a closure of $T$? Some notations on pages 2 and 3 are inconsistent.\n  - It would be better to formally define the concepts of being finalized, the new space $\\hat{S}$.\n  - Since the process is deterministic, should there be only one expansion?\n  - I am a little confused by the context around Proposition 1, especially by the claim that MDP is equivalent to solving the CO problem. The proof seems to show that MDP can simulate general Turing machines subsuming CO algorithms, which is well-known.\n  - The mapping $\\Theta$ introduced in Section 3 is desired but computationally hard to obtain in general. In addition, its role in the proposed model (Sec 4) is not very clear.\n\n- W2: Another major concern is that the designed model, as the main contribution, was described in a very abstract manner, and it is not clear how the ideas in the previous sections can be realized. Therefore, the novelty of this paper is not clear. The concrete contribution of this paper is entirely in the first paragraph of Section 4, but there are almost no technical details. As such, it seems that the proposed method can be obtained from the existing methods with very slight modifications. \n\n- W3: The paper could support reproducibility by including the source code. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "NuEr8WY5Vk", "reviewer": "Reviewer_Sx6V", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper presents a framework for defining construction heuristic MDPs for combinatorial optimization problems and proposes a technique for exploiting symmetries in state representation in such MDPs based on a mapping to a different state representation. They design a transformer-based architecture for solving TSP and CVRP that utilizes such mapping and show that they significantly improve over the baseline in terms of generalization to larger problems.", "summary_of_the_review": "The paper seems to propose a nice enhancement to neural combinatorial optimization by exploiting symmetries in states. The experimental results show impressive improvement over baselines on problems of larger size compared to training set. The main weaknesses are: (1) it is not entirely clear how much the experimental results benefit from the theory presented in the paper; (2) the existing experimental results are limited to two routing problems and it is not clear that this technique would easily extend to non-routing combinatorial problems despite being presented as a general approach for combinatorial problems.", "strength_and_weaknesses": "Strengths:\n* Novel and simple approach to enhance neural combinatorial optimization problem by exploiting symmetry\n* Results on generalization to larger instances than the training set instances show impressive improvement over the baselines\n\n\nWeaknesses:\n* While the approach is presented as a generic and flexible framework for combinatorial optimization, it seems to require a domain-specific mapping (Phi). The paper only considers such mapping for two routing problems and it is not clear if such mappings would naturally exist for many other (particularly non-routing) combinatorial problems and whether they will prove useful in such problems.\n* The long theoretical discussion on general combinatorial optimization using MDP and bisimulation-quotienting seems somewhat disconnected from the actual neural approach. While it does seem to inspire such approach, the proposed neural approach could stand on its own as a new way of handling symmetries in routing problems. In particular, unlike the MDP framework built around rewards, the neural approach is trained using imitation.\n* The approach requires optimal solutions for training. Such optimal solutions are typically intractable to compute beyond certain problem size. This is an important difference from approaches like Kool et al. (2021) based on reinforcement learning that do not rely on ground-truth optimal solutions.\n\nMinor question: does \"AM bs1024\" indicate a beam search with beam width of 1024?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "3Sbz7JLRnze", "reviewer": "Reviewer_kF44", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "To improve the out-of-distribution generalization in solving combinatorial optimization (CO) problems, this paper proposes a transformed MDP to formulate constructive heuristics. Specifically, the transformation is based on bisimulation quotienting (BQ), which reduces the state space by leveraging the symmetries of the state space. Experiments on the Traveling Salesman Problems (TSP) and Capacitated Vehicle Routing Problems (CVRP) demonstrate that the proposed method achieves the state-of-the-art generalization performance.\n", "summary_of_the_review": "The idea of improving the generalization performance based on BQ is interesting. However, some claims are not well-supported, and some description of the method is unclear. ", "strength_and_weaknesses": "Strengths:\n* Introducing bisimulation quotienting to reduce the state space of CO problems is an interesting idea.\n* The proposed method significantly improves the generalization performance in solving the TSP and CVRP, especially on the problems with large-scale graphs.\n\nWeaknesses:\n* The authors claim that their formulation is generic for arbitrary CO problems. However, the formulation seems specific for the TSP and CVRP. Thus, it would be more convincing if the authors could explain how the proposed formulation applies to other CO problems, such as mixed-integer linear programs. \n* The details about introducing the bisimulation quotienting into their proposed transformer-based model are unclear. For example, please illustrate the proposed model architecture and hyperparameters. Moreover, how does the proposed method learn two special embedding vectors for the origin and destination nodes?\n* The ablation studies are insufficient. The authors may want to provide more experiments to show the effectiveness of the proposed BQ-based formulation. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject