Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt
Authors: Yining Ma
Zhiguang Cao
Yeow Meng Chee
Venue: NeurIPS 2023 poster (2023)
Keywords: learning to optimize
vehicle routing problem
combinatorial optimization
TL;DR: We present a novel and flexible Neural k-Opt (NeuOpt) solver for routing problems that enables autonomous exploration of both feasible and infeasible regions.

Abstract: In this paper, we present Neural k-Opt (NeuOpt), a novel learning-to-search (L2S) solver for routing problems. It learns to perform flexible k-opt exchanges based on a tailored action factorization method and a customized recurrent dual-stream decoder. As a pioneering work to circumvent the pure feasibility masking scheme and enable the autonomous exploration of both feasible and infeasible regions, we then propose the Guided Infeasible Region Exploration (GIRE) scheme, which supplements the NeuOpt policy network with feasibility-related features and leverages reward shaping to steer reinforcement learning more effectively. Additionally, we equip NeuOpt with Dynamic Data Augmentation (D2A) for more diverse searches during inference. Extensive experiments on the Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) demonstrate that our NeuOpt not only significantly outstrips existing (masking-based) L2S solvers, but also showcases superiority over the learning-to-construct (L2C) and learning-to-predict (L2P) solvers. Notably, we offer fresh perspectives on how neural solvers can handle VRP constraints. Our code is available: https://github.com/yining043/NeuOpt.

Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt
Yining Ma
Zhiguang Cao"
National University of Singapore yiningmadu. nus. nus. edu
Singapore Management University zgcao@smu. edu. sg
Yeow Meng Chee
National University of Singapore ymcheeθnus edu.sg
Abstract
In this paper, we present Neural k-Opt (NeuOpt), a novel learning-to-seane (L22) solver for routing problems. It learns to perform flexible k-opt exchanges based on a tailored action factorization method and a customized recurrent dual-stream decoder. As pioneering work circumvent the pure feasibility masking scheme and enable the autonomous exploration of both feasible and infeasible regions, we then propose the Guided Infeasible Region Exploration (GIRE) scheme, which sup- plements the NeuOpt policy network with feasibility- rellted features and leverages reward shaping to steer reinforcement learning more effectively. Additionally, we equip NeuOpt with Dynamic Data Augmentation (D2A) for more diverse searches during inference. Extensive experiments the Traveling Salesman Problem (TSP) and Capacitated Vehicle Routing Problem (CVRP) demonstrate that our NeuOpt not only significantly outstrips existing maasking-basell L2S solvers, but also show- cases superiority over the coemiinggtt-constree (L2C) and learning-to- ceriinngtt--rediic (L2P) solvers. Notably, we offer fresh perspectives on how neural solvers can handle VRP constraints. Our code is available: https: //g/t/gttt////// com/ hwtpyyinnnnnnnneuuu
Introduction
Vehicle Routing Problems (VRPs), prevalent in various real-world applications, present NP-hard combinatorial challenges that necessitate efficient search algorithms [1, 2]. In recent years, significant progress has been made in developing deep (reinforcement) learning-based solvers (e.g., [3-11]), which automates the tedious algorithm design with minimal human intervention in a data-driven fashion. Impressively, these neural solvers developed the past five years have closed the gap to or even surpassed some traditional hand-crafted solvers that have evolved for several decades [5, 12).
In general, neural methods for VRPs be categorized into learning- to-construct (L2C), learning-to to- search (L2S), and cearning-to-preee to-peddict (L2P) solvers, each offering unique advantages while suffering respective drawbacks. L.2C solvers (e.g., [4, 13)) are recognised for their fast solution construction but may struggle to escape local optima. L.P solvers excel at predicting crucial information (e.g., edge heatmaps [14, 15)). thereby simplifying the search especially for large-scale instances, but may lack the generality to efficiently handle VRP constraints beyond the Traveling Salesman Problem (TSP). L2S solvers (e.g.. [8. 9]) are designed to learn exploration in the search space directly; however, their search efficiency still limited and lags behind the state-of-the-arr L2C and L2P solvers. In this paper, we delve into the limitations of existing L.S solvers, and aim unleash their full potential.
Zhiguang Cao is the corresponding author.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

One potential issue of L2S solvers lies in their simplistic action space designs. Current L2S solvers that learn to control k-opt exchanges mostly leverage smaller values (2-opt [9, 16] or 3-opt [17]). partly because their models struggle to efficiently deal with larger k. To address this issue, we introduce Neural k- k-Opt (NeuOpt), flexible 1.25 solver capable of handling k-opt for any k 2 2. Specifically, it employs tailored action factorization method that simplifies and decomposes a complex k-opt exchange into a sequence of basis moves (S-move, I-move, and E-move) with the number of I-moves determining the & of specifically executed k-opt action'. Such design allows k- opt exchanges to be easily constructed step-by-step, which more importantly, provides the deep model with the flexibility to explicitly and automatically determine an appropriate k. This further enables varying k values to be combined across different search steps, striking a balance between coarse- grained (larger k) and fine- -eriierridd (smaller k) searches. Correspondingly. we design a Recurrent Dual-Stream (RDS) decoder to decode such action factorization, which consists of recurrent networks and two complementary decoding streams for contextual modeling and attention computation, thereby capturing the strong correlations and dependencies between removed and added edges.
Besides, existing L2S solvers confine the search space to feasible regions based feasibility masking. By contrast, we introduce a novel Guided Infeasible Region Exploration (GIRE) scheme that promotes the exploration of both feasible and infeasible regions. GIRE enriches the policy network with additional features that indicate constraint violations in the current solution and the exploration behaviour statistics in the search space. It also includes reward shaping to regulate extreme exploration behaviours and incentivize exploration at the boundaries of feasible and infeasible regions. Our GIRE offers four advantages: 1) it circumvents the non-trivial calculation of ground-truth action masks, particularly beneficial for constrained VRPs or broader action space as in NeuOpt, 2) it fosters searches at the more promising feasibility boundaries, similar to traditional solvers [18-21], 3) it bridges (possibly isolated) feasible regions, helping escape local optima and discover shortcuts to better solutions (See Figure 2), and 4) it forces explicit awareness of the VRP constraints, facilitating the deep model to understand the problem landscapes. In this paper, we apply GIRE to the Capacitated Vehicle Routing Problem (CVRP), though we note that it is generic to most VRP constraints.
Moreover, our NeuOpt leverages a Dynamic Data Augmentation (D2A) method during inference to enhance the search diversity and escape local optima. Our NeuOpt is trained via the reinforcement learning (RL) algorithm tailored in our previous work [12]. Extensive experiments on classic VRP variants (TSP and CVRP) validate our designs and demonstrate the superiority of NeuOpt and GIRE over existing approaches. Our contributions are four-fold: 1) we present NeuOpt, the first L.2S solver that is flexible to handle k-opt with any & 2 2 based
tailored formulation and customized RDS decoder, 2) we introduce GIRE, the first scheme that extends beyond feasibility masking, enabling exploration of both feasible and infeasible regions in the search space, thereby bringing multiple benefits and offering fresh perspectives on handling VRP constraints, 3) we propose a simple yet effective D2A inference method for L2S solvers, and 4) we unleash the potential of L2S solvers and allow it to surpass L2C, L2P solvers, as well as the strong LKH-3 solver [20] on CVRP.
2 Literature review
We categorize recently developed neural methods for solving vehicle routing problems (VRPs) into Seamning-to-constricc (L2C), learning-to-seue -e-surcch (L2S), and learning-to-predice (L2P) solvers.
L2C solvers. They learn construct solutions by iteratively adding nodes to the partial solution. The first modern L2C solver is Ptr-Net [22] based on Recurrent Neural Network (RNN) and supervised
learning (extended to RL in [23] and CVRP in [24]). The Graph Neural Networks (GNN) were then leveraged for graph embedding [25] and faster encoding [26]. Later, the Attention Model (AM)
was proposed by Kool et al. [3], inspiring many subsequent works (e.g., [4, 27-31)), where we highlight Policy Optimization with Multiple Optima (POMO) [4] which significantly improved AM with diverse rollouts and data augmentations. The L2C solvers can produce high-quality solutions within seconds using greedy rollouts; however, they are prone to get trapped in local optima, even when equipped with post-hoc methods (e.g., sampling [3], beam search [28], etc), or, advanced strategies (e.g.. invariant representation [13, 32], learning collaborative policies [33], etc). Recently, the Efficient Active Search (EAS) [5] addressed such issues by updating a small subset of pre-trained
Broadly, in k-opt, added edges may coincide with removed ones. Thus, 2-opt may be viewed as degenerated 8-opt. To avoid ambiguity, unless specified, we refer to k-opt as an exchange introducing k entirely new edges.
2

---

model parameters on each test instance, which could be further boosted if coupled with Simulation Guided Beam Search (SGBS) [34], achieving the current state-of-ther ofrtthe-rtt performance for L2C solvers.
L2S solvers. They learn to iteratively refine a solution to a new one, featuring a search process. Early attempts, e-g., NeuRewriter [35] and 1.21 [36], relied heavily traditional local search algorithms and long run time. The NLNS solver [8] improved upon them by controlling a ruin-and-repea that destroys parts of the solution using handcrafted operators and then fixes them using a learned deep model. Besides, the crossover exchanges between solutions were also learned in [37]. Recently, several L2S solvers focused on controlling the k-opt heuristic that more suitable for VRPs [20. 38). Wu et al. [39] made an early attempt to guide 2-opt, showing superior performance than the L2C solver AM [3]. Ma al. [9] improved Wu et al. [39] by replacing vanilla attention with Aspl-Aspect Collaborative Attention (DAC-Att) and a cyclic positional encoding method. The DAC-Att was then upgraded to Synthesis Attention (Synth-Att) [12] to reduce computational costs. Besides, Costa et al. [16] proposed an RNN-based policy to govern 2-opt, which was extended to 3-opt in [17] with higher efficiency. However, these neural k-opt solvers are limited by a small and fixed k. Besides, although L2S solvers strive to surpass L2C solvers by directly learning to search, they are still inferior to those state-of-the-art L2C solvers (e.g., POMO [4] and EAS [5]) even when given prolonged run time.
process
L2P solvers. They learn to guide the search by predicting critical information. Joshi et al. [14] proposed using GNN models to predict heatmaps that indicate probabilities of the presence of an edge in the optimal solution, which then uses beam search to solve TSP. It was leveraged for larger-scale heatmap merging, and Monte Carlo Tree Search. In the GLS solver [40], similar GNN was used to guide the traditional local search heuristics. More recently, the DIFUSCO solver [15] proposed to replace those GNN models with diffusion models [41]. Compared to L2C or L2S solvers, 1.2P solvers exhibit better scalability for large instances; however, they are mostly limited to supervised learning and TSP only, due to challenges in preparing training data and the ineffectiveness of heatmaps in handling VRP constraints. Though L2P solver DPDP [42] managed to solve CVRP with dynamic programming. it was outstripped by L2C solver EAS[5]. Recently, L2P solvers also explored predicting a latent continuous space for the underlying discrete solution space, where the latent space is then searched using differential evolution in [43] or gradient optimizer in [7]. Still, they can be either time-consuming or ineffective in tackling VRP constraints.
TSP instances in [6] based on
Feasibility satisfaction. Most neural solvers handle VRP constraints using the masking scheme that filters out invalid actions (e.g., [12, 44]). However, few works considered better ways of constraint handling. Although the works [45, 46] attempted to use mask prediction loss to enhance constraint awareness, they overlooked the benefits of the temporary constraint violation applied in many traditional solvers [18-21]. Lastly, we note that constraint handling in VRPs largely differs from safe RL tasks that focus on fully avoiding risky actions in uncertain environments [47, 48].
3 Preliminaries and notations
VRP notations. VRP aims to minimize the total travel cost (tour length) while serving a group of customers subject to certain constraints. It is defined on a complete directed graph G = (V, E where r; E are nodes (customers) and e(x; -Z,, E are possible edges (route) weighted by the Euclidean distance between x; and Zy. In the Traveling Salesman Problem (TSP), the solution is a Hamiltonian cycle that visits each node exactly once and returns to the starting one. In the Capacitated Vehicle Routing Problem (CVRP), a depot zo is added to V. and each customer node 2z(i 1) is assigned a demand &, A CVRP solution consists of multiple sub-tours, each representing a vehicle departing from the depot, serving subset of customers, and returning to the depot, where each z;:( > 1) is visited exactly once and the total demand of a sub-tour must not exceed the vehicle capacity A. For instance, { 22- - 1 - +o >23 3 is CVRP-3 solution with 8= [5, 5,9] and A 10.
Traditional k-opt heuristic. The k-opt heuristic iteratively refines a given solution by exchanging k existing edges with 1: (entirely) new ones. The Lin- Le-Kennighan (LK) algorithm [49] narrowed the search with several criteria, where we underscore the sequential exchange criterion. It requires: for each i = 1....,k k. the removed edge etth and added edge e,"h must share an endpoint, and so must e," and e This allows a simplified sequential search process, alternating between removing and adding edges. Moreover, the LK algorithm considers scheduling varying & values in a repeated ascending order, so as to escape local optima by varying search neighbourhoods. Inspired by them, our paper proposes powerful L2S solver that performs flexible k-opt exchanges with automatically chosen k
3

---

Andtorr mods
Lactstlactdd mode
o Exipoit
Move S Edge
AAttoatio s00r Mosked atterroo
Balocance
Added odge Removed
Xode
Current
mhrktmark
Atterbor
Dundtoo
wirt wcrtundory,
02 h4
bg
GRU
GRU
GRU
GRU
Decodorna
Decoters
Adian: (ora))
Docddet Action
Decoder Aeteeeeeettt
&
4
Reke Add
361.00
Romnee
Add
Add
Add
(etyntah (Ryyntty (ite)tta))
Figure 1: Illustration of using RDS decoder to determine 3-opt exchange on TSP-9 given K= steps (with the E-move chosen at the final decoding step). The upper portion depicts a visual representation of how the dual-stream attentions (move stream μu and edge stream X) are computed. The lower portion demonstrates how the inferred basis moves lead to the modification of the current solution. At step K, RDS computes dual-stream attention from representations of historical decisions Ii 4x to node embeddings hy, thereby deciding a basis move (x,) ) by selecting Tx- Ghost marks indicate the same location of a cyclic solution when viewed in a flat perspective as this figure.
based on action factorization method and the customized decoder. Recently, the LK algorithm has been implemented by Helsgaun [50] in the open-source LKH solver, with additional non-sequential exchanges and edge candidate set. It was then upgraded to LKH-2 2 [51]. leveraging more general k-opt exchanges, divide-and- and---r strategies, etc. The latest release, LKH-3 [20], further tackled constrained VRPs by penalizing constraint violations, making it a generic and powerful solver that serves as a benchmark for neural methods. Finally, we note that k-opt has been a foundation for various solvers, including the state-of-the-art Hybrid Genetic Search (HGS) solver [21] for CVRP.
Neural k-opt (NeuOpt)
Designing effective neural k-opt solver necessitates addressing challenges potentially overlooked in prior works. Firstly, the solver should be generic for any given k> using a unified formulation and architecture. Secondly, it should coherently parameterize the complex action space while accounting for the strong correlations and dependencies between removed and added edges. Finally, it should dynamically adjust & to balance coarse goaiie- (larger k) and fine-grained (smaller k) search steps.
In light of them, we introduce Neural k- K-Opt (NeuOpt) in this section. We first present our action factorization method for flexible k-opt exchanges, and then demonstrate our decoder to parameterize such actions, followed by the dynamic data augmentation method for inference. Note that this section focuses on TSP only, and we extend our NeuOpt to handle other VRP constraints in Section 5.
4.1 Formulations
We introduce new factorization method that constructs a k-opt exchange using a combination of three busis moves, namely the starting move, the intermediate move, and the ending move. Concretely, the sequential k-opt can be simplified as performing one S-move, several (possibly none) I-moves, and finally one E-move, where the choice of the h corresponds to determining the number of I-moves.
S-move. The starting move removes an edge """ + +2)). converting TSP solution (a Hamilto- nian cycle) into an open Hamiltonian path with two endpoints Ia and øa. It is executed only at the beginning action construction. We denote S-move as S(x,) since x6 can be uniquely determined if Ir is specified. We term the source node Za as anchor node to compute the node rank.
Definition (Node rank w.r.t. anchor node) Given instance G= (V,E) and a solution T, let No be the anchor node, as specified in an S-move. The node rank of x, (I,, E V) w.r.t. En. denoted by needed reach F. from Ta.
T[ra, or Pla, u.) defined as the minimal number of edges
T-move. The intermediate move adds a new edge, removes an existing edge, and fixes edge directions, transforming the open Hamiltonian path into new one. Let 24, Iz, be the endpoints of the Hamiltonian

---

path before the I-move (with a/a, i| (T), and let (z - -2,,) be the introduced new edge. To avoid conflicts between consecutive I-moves, we impose sequential conditions on ex:: (1) its source node T. must be the endpoint of the current Hamiltonian path with lower node rank, i.e., Ix = 2ú. and (2) the node rank of its target node Te. i.e., F[a, vl, must be higher than the node ranks of the two current endpoints 24; i.e., T(a, i] < [[a. j] < a(a, vj. The removal of edge coat(x, - zww) followed when zy is chosen, and directions of the edges between zj and z, are reversed to yield a valid Hamiltonian path. Since an I-move can be uniquely determined by Zo. we denote it as / (xx)).
The ending move adds a new edge connecting the two endpoints of the current Hamiltonian path, converting it into Hamiltonian cycle. i.e., a new TSP solution T'. is executed only at the end of action construction. Since it is uniquely determined without specifying any node, we denote as (Tman) Note that if we relax the condition (2) of I-move tol a. 5 <Taa, u/, an E-move can be treated as a general I-move that selects F2 = -., denoted as I' (xxx or F(x,).
E-move.
MDP formulations. The examples of using the above basis moves to factorize 1-opt (void action), 2-opt, 3-opt, and 4-opt are depicted in Appendix A. Next, we present the Markov Decision Process (MDP) formulation M = (S, A, A, R, Y < 1) for our NeuOpt. At step i, the state 8 = {G, Te, T/ describes the current instance G, the current solution Tr, and the best-so-fir far solution -. found before step I. Given a maximum number of allowed basis moves K(K 2 2), an action consists of K basis movey & (xx), i.e., a; (3xx)) k= 1, ,..... K}, where the first move ( ((1)) is an S-move, and the rest either an I-move or an E-move (in the form of general I-move). Note that 1) we permit the I-move as the last move, adding ensure the action length is always K, we include null actions if E-move early terminates the action. Our state transition rule T is deterministic and it updates 8, 8t-41 based on the above action factorization method. We use reward r' = f(r/")) - min [ 1), f(T(()) following [9, 12].
E-move during state transition if so, and 2) to
4.2 Recurrent Dual-Stream (RDS) decoder
Our NeuOpt adopts an encoder--eecoder-sty/e policy network. We use the encoder from our previous work [12] but upgrade the linear projection to an MLP for embedding generation (details are presented in Appendix B). Here, we introduce the proposed recurrent dual-stream (RDS) decoder to effectively parameterize the aforementioned k-opt action factorization (see Figure I for a concrete example).
GRUs for action factorization. An action a= by K steps, where each decoding step k specifies basis move type 4, and a node H. to instantiate the move. Such decoding can be further simplified to a node selection process, with move types inferred based on: (1) for K it is an S-move; (2) for K > 1, it is an I-move if I' ju] < I'aa, x] (assuming 24,, Ty are the Hamiltonian path endpoints before the æ-th move with L'(a, ix] <1" jxD, otherwise, if xxx = Jy it is an E-move that early stops the decoding. Formally, we use factorization:
k=l,.... K} is constructed sequentially
K
To [a (P( (2(22) ... {x(oK)() II Ps P5 P1 ....... 1x
(I)
where P is a categorical distribution over N nodes for node selection. Our decoder leverages the Gated Recurrent Units (GRUs) [52] to help parameterize the conditional probabilities P Given node embeddings h E RR-N from the encoders (h; is a d-dimensiona vector), the decoder first computes hidden representations q" to model the historical move decisions {#1.-... } (the conditions of P5) using Eq. (2), where qe (hidden state of GRU) is derived from q" based on an input o". For better contextual modeling, we consider two streams, μ and X, which differ from each other by
learning independent parameters and taking different inputs o at each k. The df = - initialized by the mean pooling of node embeddings (i.e., a graph embedding).
ΣM h4
0 = GRU (of of-11) o = GRU (o%, 9x 1
(2)
Dual-stream contextual modeling. We employ a move stream μ and an edge stream X during contextual modeling and subsequent attention computation. On the one hand, to provide a relatively overall view, the move stream considers modeling historical move decisions by taking the node embedding of the last selected node I which is representation of the past selected move 1x-1(xxx11) as its GRU input, i.e., 0f - = On the other hand, to offer a relatively detailed view, the edge stream X focuses on edge proposals in each step by taking the node embedding of v.,,, which is stipulated to be the source node of the edge to be introduced in step k, as its GRU input,
5

---

i.e., =h. We intend the two streams to complement each other, coherently capturing complex correlations and dependencies among historical decisions. For the initialization, we use learnable parameters 02 o, o ö. Based on the attention between qy. QA and node embeddings h, the node selection scores suggested by both streams can then be calculated:
Pv. Tanh ((. Wu + Kor + W (hW )) W
p
(3)
AR Tanh ( + xa) + (a W @ (hW )) W
where all matrices W IRdx are trainable parameters and we consider both summation and Hadamard products. Afterwards, the final categorical distribution P/ is induced by: Softmax(C where C== 6 and invalid choices that do not satisfy [(a, < <Taa, s] are masked as -oo (an E-move is enforced if all nodes masked, which happens when the highest-ranked node was chosen in the previous I-move). A node Tye is then sampled from Pg. after which its basis move type 4x can be inferred. The decoding process continues until it early terminates reaches the maximum limit K.
(x,)
4.3 Inference with the dynamic data augmentation (D2A)
Our NeuOpt is trained using the RL algorithm tailored in our previous work [12]. During inference, our previous work [12] employed data augmentation method that applies cilimal-souutioninnaaaa transformations (e.g.. flipping coordinates) on an instance, G. so as to generate set of instances (G1, 9 for the trained model to solve. However, it was performed only once at the beginning of the inference. In this paper, we propose Dynamic Data Augmentation (D2A), an enhancement that generates new augmented instances each time the solver fails to find better solution (i.c., getting trapped in local optima) within a consecutive maximum of TDA steps. This allows for more diverse searches. Further details regarding training and inference algorithms are provided in Appendix C.
5 Guided infeasible region exploration (GIRE)
As demonstrated in Figure 2, the feasible region is usually fragmented with isolated islands. Masking in neural solvers typically restricts the search feasible regions, which may lead to inefficient search trajectories or failure to find global optima. Our GIRE explores both feasible and infeasible regions, foster- ing shortcut discovery, more promising boundary searches, and the identification of possibly isolated regions. We now illustrate our GIRE by handling the capacity constraint in CVRP.
Faxilee (*)
@r (r
O (t)
Glubel Optims
Trojaddey (uur G1BB wheensi
Local Opdina
....
Trajadtey (rankingalam
Figure 2: A search space example.
Definition 2 (Search space of CVRP): We define the feasible search space F the set of solutions that satisfy both TSP and the (CVRP-specific) capacity constraint; the infeasible search space U as the set of solutions that satisfy the TSP constraint but not the capacity constraint; and the e-feasible search space e-F Cu as the set of solutions with a capacity violation percentage not exceeding e.
Feature supplement. GIRE suggests supplementing Violation Indicator (VI) features and Explo- ration Statistics (ES) features into the policy network to identify specific constraint violations and understand its ongoing exploration behaviour. The VI features flag the specific infeasible portions of the current solution. For CVRP, we use two binary variables indicating if the cumulative demands exceed the capacity before after visiting a partieular node, respectively, which treated as node features during the node embedding generation. Such an idea could work with most VRP constraints, e.g., indicating the nodes that violate their time windows (TW) for CVRP-TW. The ES features provide the network with ongoing exploration behaviour statistics to guide future exploration behaviour. We define 74 := {(Tu + +e44) H Hi as the collection of the most recent This steps of solution transition record (if they exist). The ES features J, consist of estimated feasibility transition probabilities derived from H,, including P(T F P(T E E FF), P(T E F, E F), P(, ETT)), P(F'EU) (FTEEF,, and P P(r'E E44), along with a binary indicator w.r.t the feasibility of the current solution 7;, In order to make the policy network decisions dependent on these ES features, we introduce two hypernetworks [53], namely, MLP, R and MLPX, which take ES features J, as inputs and generate the parameters of the last decoder layer, i.e., WO, WO of Eq. (3), respectively. We adopt the structure (9 x 8 x d), and share the first hidden layer between / and W to reduce computational costs.

---

Reward shaping, Moreover, GIRE employs reward shaping:
Entropy Entropy measure
1.0
GIRE f ta r bonus
(4)
to guide the reinforeement learning, where is the original reward, rt regulates extreme exploration behaviours; rhomus encourages exploration in the e-feasible regions; and a and are reward shaping weights (we use 0.05 for both). Here, the regulation r is determined by entropy measure H[PP of the estimated conditional transforming probabilities P((2((4)= ((T EU) and =) F):
0.0
0.00
0.50
0.75
1,00
Probability
Figure 3: Plot of [].
Er: +
Ti
(5)
H[P] Clip [1 - c1 loga P 0, .1 = 0.5, 02 = 2.5,
where expectation Elrr]. that suggests the magnitude of r is estimated during training; the entropy measure [P]), as shown in Figure 3, imposes larger penalties when P is either too high or too low (indicating extreme exploration behaviour). The bonus p.oouss utilizes similar reward function the regular reward ry; however, it only considers an infeasible but e-feasible solution as a potential new best-so-far solution. More illustrations and discussions on GIRE designs are detailed in Appendix D.
Experiments
We conduct experiments on TSP and CVRP, with sizes - 50, 100 following the conventions [9, 13, 37]. Training and test instances are uniformly generated following [3]. For NeuOpt, we use K =4: 4; the initial solutions sequentially constructed in random fashion for both training and inference. Results were collected using a machine equipped with NVIDIA 2080TI GPU cards and an Intel E5-2680 CPU at 2.40GHz. More hyper-parameter details, discussions, and additional results available in Appendix E. Our PyTorch code and pre-trained models are publicly available?.
6.1 Comparison studies
Setup. In Table 1, we benchmark our NeuOpt (TSP) and NeuOpt-GIRE (CVRP) against a variety
of neural solvers, namely. 1) L2P solvers: GCN+BS [14] (TSP only). Am-GCN+MCTS [6] (TSP
only), GNN+ GLS [40] (TSP only). CVAE-Opi-DE [43], DPDP [42] sftate-of-thhearte DIMES [7]
(TSP only), DIFUSCO [15] (TSP only, sfate-of-the-are ; 2) L2C solvers: AM+LCP [33], POMO [4],
Pointerformer [32] (TSP only). Sym-NCO [13], POMO+EAS [5], POMO+EAS+SGBS [34] (state-of-
ahe-art); and 3) L2S solvers: Costa et al. [16] (TSP only), Sui et al. [17] (TSP only). Wu et al. [39].
To ensure faimess, we test their publicly available pre-trained models on our hardware and test datasets. Those marked with are sourced from their original papers due to difficulties in reproducing, among which we find potential issues marked with #. More implementation details are listed in Appendix E. Following the conventions [5. 9. 34), we report the metrics of objective values and optimality gaps averaged on test dataset with 10k instances, where the total run time is measured under the premise of using one GPU for neural methods and one CPU for traditional ones. The gaps are computed w.r.t. the exact solver Concorde [54] for TSP and the state-of-ther oftt---rttt traditional solver HGS [21] for CVRP. We also include the LKH [20, 51] as baselines. However, we note that it is hard to be absolutely fair when comparing the run time between those CPU-based traditional solvers and GPU-based neural solvers. The baselines are grouped, where the last group comprises variations of our NeuOpt, differentiated by the number of augments (marked "D2A=') and the number of inference steps (marked as "T=').
NLNS [8] (CVRP only), NCE [37] (CVRP only), DACT [9] (state-of-the-are
TSP results. Compared to L2P solvers, NeuOpt (D2A=1, T=Ik) surpasses GCN+BS, CVAE-Opt- DE, and GNN+GLS in all problem sizes with shorter run time. With increased T. NeuOpt continues reducing the gaps, and outshines the state-of-the-au DIFUSCO solver with less time at T=10k steps. The NeuOpt (D2A=5, T=lk), with more augmentations, shows lower gaps than NeuOpt (D2A=1, T=5k) in the same solution search count, where it achieves the lowest gap of 0.00% at (D2A=5, T=5k) all sizes. Despite the longer time compared to DPDP and ACtGGCN+MTSS their high efficiency is limited to TSP, and our NeuOpt could be potentially boosted by leveraging heatmaps
'https://githan http:::://gituub.oo///iiiit hattge///gthbbbooo/////gggggg//g www/yliningg44///Muup
7

---

Table Performance comparison of NeuOpt with various baselines on TSP and CVRP benchmarks.
Method
Model
Post (Per-
N =220
N=50
N = 100
Type Im.)) Proc.
Obj.
Capl.
Timel
0kj-4
Gopl
Timel
0bj
Gapl
Timc.
Concorde [54)
Exact
3.827
2m
5.696
9m
7.765
43m
LKH-22 [51]
3.277
0.005%
3,006
0.00%
1.3h
7.765
0.005
5.7h
GCNABS [14]a
1,21S1.
BS+H
3827
0.00%
15m
5.008
0.04%
23m
7,869
1.35%
46m
Ar-GCN- 16]-0
L2P/SL
MCTS
(s3.830)
(=0.000)
=2m
(s5.691)
(s0.015%
=8m
(x7.764)
(=0.04%)
=15m
GNN+GLS [40] (pelocatee22opo)
L2P/SL
GLS
+0.00%
+2.8b
+0.00%
+2.8h
e0.58%
+2.8h
CVAE-Opt-DE [43]]
DE
+0.00%
+0.02%
+0.34%
DPDP [42] (100k)
L2PISL
DP
7.765
0.00KS
1.9h
DIMES [?] (T-10)1-+
L2P/RL.
AMIM
(=7.762)
(=D.011%
DIFUSCO [15) (T-50, S-16)
L2P/SL
2-opt
5.696
0.01%
7.766
0.02%
21.7h
AM+LCP" [33] (12200 45/)
L2CRL
3,828
0.01%
2.1h
5.699
0.05%
4.9h
7.811
0.60%%
10. 9h
Pointeroommer [32] (A=X T-200)
1.CRRI
3,827
0.00%
13m
5.007
0.025
1.1h
7,773
0.11%
5.6h
Sym-NCO [13] (A=8. T=200)
0,08%
5.6h
POMO [4] (A=S, T-200)
L2C/RL
3.827
0.00%
13m
5,696
0.00%
1.1h
7.770
0.07%
5.6h
POMO-EAS [5] (A=8. T-200)
L2C/RL AS
3.827
0.00%
24m
5.696
0.00%
2h
7,769
0.05%
10.
POMO-EAS:SCBS
(short)
L2CRL
AS-BS
7.767
0.04%
6.5h
POMO-EAS+SCDS [34] (long)
L2C/RL AS-BS
7.767
0.03%
1.ld
Costa et al. [16] (2-opt, T=2k)
L28/R1.
3,277
0.00%%
31m
5,703
0.12%
40m
7.824
0.77%
1.1h
al. [17] (3-ops, T-2kF
L28/RL
<3.84
+0.00%
=32m
=:5.0
=0.00%%
a.48m
=7.82
-0.74%
1.33
et (2-opt. T-5k)
L2S/RL
0.23%
1.3h
7,884
1.54%
2h
[9CT A-4, T-10k)
128/RL
3,877
0.00%
1.5h
5.096
0.00%
4.1h
7.772
0.10%
13.5h
NeuOpt((DAA-1) (D22A11, T-1k)
L28/RL
3,827
0.00%
2m
5.007
0.02%
6m
7.790
0,333
17m
Nc2Opt(DDAA1)))
L2S/RL
0.00%%
0.00%
32m
7.768
0.05%
1.4h
NeuOpt 1.2
L25/RL
3.827
0.00%
23m
5.696
0.00%
1.1h
7.766
0.02%
2.8h
NeuOpt (D2A=5, T=1k)
L25/RL
3.827
0.00%
12m
5.696
0.00%
32m
7.767
0.04%
1.4h
(D200p(D22-5....... T-33))
L25/RL
3,827
0.00%
35m
5.696
0.00%
1.6h
7.765
0.01%
4.2h
NeuOpt (D2A-55, T-5k)
L2S/RL
3.827
0.00%
0.00%
2.7h
7.765
0.00%
7h
HGS [21]
10.7h
10.366
1.24
15.563
2.5d
LKH-3 (20)
6.135
0.08%
17.9h
10.375
0.09%
2.80
15.647
0.54%
5.70
CVAE-Oxe-DEH45 [43]]
L2PUL
DE
-6.14
2.44
=10.40
.4.7d
=15.75
=11d
DPDP (1000k)
L2P/SL
DP
15.627
0.41%
1.28
AM+LCP [33] (12560, 19)
L2C/RL
+6.15
-0.33%
=23m
=10.52
=1.48%
+:2mm
=16.00
+2.81%
-2.
Sym=NCO [13) (A=8, T=200)
L2CRL
15,702
0.89%
7.2h
POMO (A=8, T-200)
L2C/RL
0.09%
11m
10.397
0.30%
1.4h
0.70%
7.2h
POMO-EAS (A=8, T=200)
L2C/RL
AS
6.132
0.04%
38m
10.379
0.13%
3.
15.610
0,30%
16h
POMO-EAS-SSIBS [34] (short)
L2CRL AS BS
15.587
0.15%
1d
CVRP
POMO-EAS4SSORS [34] (long)
L2CRL AS-B8
0.10%
4.1d
NLNS [8] (Ruin-Repuir, T=5k)
L2S/RI
6.175
0.73%
48m
10:506
1.35%
1.4h
15:915
2.26/5
2,4h
NCE [57] (CROSS exchange)
L2S/SL.
x6.13
=0..00%
-11h
:10.4]
=:0.42%
=2..3d
=15.88
=11.59%
=110.4
al. (2-opt. T=5k)
L2S/RL
1.72%
3.87%
Sh
DACT [9] (2-opt, A-6 T-10k)
128/RL
6,130
0.01%
10:383
0.16%
16h
15:736
1.11%
1.7d
NeuOpt-GIRE Gralp--GRRRR/a (D2A-11 T=lk)
L25/RL
6.132
0.03%
4m
10.430
0.61%
12m
15.865
1.94%
28m
NeuOpt-GIRE (D2A=11 T=5k)
L25/RL
6.130
0.00%
20m
10.382
0.16%
59m
15,698
0.87%
2.3h
NeuOpt-GRRE (D2A-1. T-10k)
L2S/RL
0.00%
0.08%
0.60%
4.6h
NeuOpt- GIRE (D2A=5, T=ok)
L25/RL
6.130
0.00%
2.1h
10.369
0.03%
5.9h
15.610
0,30%
13.8h
NeuOpt-GiRRE (D22A-5 T-20k)
L28/RL.
6.130
0.00%
6.8h
10.367
0.015
19.7h
15.586
0.15%
1.9d
NeuOpt-CilRR (122A=5, T=40k)
L28/RL
0.00/
0.01%
0.10%
3.8l
We found issues with their code, causing underestimation their reported gaps mughly 0.02% (TSP-50) and 0.04% (TSP-100). Thus reproduced gaps may vary from those their papers. For not reproducedd ones, we use ()) indicate the underestinatled values soureed directly from their pupers. The results with 's' are based on their original papers since their code is either i) not publicly aeailable (eg. A AMACIP for CVRP) ii) raises (incompatiblee) iiš) requires long computation time reproduce (e.g.. CVAE-Opt-DDB
errors that are difficult fix
hardware (c.g. AI--CCN-MCSS) Augmentation, D2A Dynamic Augmentation. BS Beam Search, H Heuristies, MCTS Monie Carlo Search, DE- Dificremial Evalution, DP Dynamic Programming, GLS Guided Local Search, AS - Active Search, AS+M+M AS+MCTS-MMau Metrrnnnnnn
Note: The abtveviations
similar to theirs. As for L2C solvers, NeuOpt (D2A=5, T=3k) beats all baselines on TSP-100 with less time, including the state-of-the-ar POMO+EAS+SGBS solver. When pitted against L2S solvers which ours also belongs to, NeuOpt is able to at least halve their gaps using much shorter run time, demonstrating a substantial improvement. Lastly, our NeuOpt (D2A=5, T=5k) is one of the neural solvers (including DPDP) that can solve TSP- 100 to near-optimal (i.e., 0.00%) in reasonable time.
CVRP results. Most L2P solvers fail to handle CVRP. The remaining ones, CVAE-Opt-DE and DPDP, are significantly outstripped by our solver (D2A=5, T=6k) with less run time. For L2C solvers, our NeuOpt-GIRE, (D2A=1, T=10k) could exceed the previous state-of-the-art POMO solver. Furthermore, with (D2A=5, T=6k) and (D2A=5, T=40k), our method surpasses POMO+EAS and POMO+EAS+SGBS (Long) with less run time, respectively, even though they equip with extra post- hoc per-instance processing boosters. We note that such post- proseprocessing strategies (e.g., per-instance active search) could potentially be integrated into ours for further performance gains. Compared to L2S solvers, due to the advances of our GIRE, even NeuOpt-GIRE: T==k) could reduce the gaps of those (masking-baseel Notably, we are the first L2S solver to surpass the strong LKH-3 solver on CVRP.
I.2S solvers by an order of magnitude in much less time on CV0P-100.
8

---

Table 2: Comparisons our proposed RDS decoder and GIRE scheme versus existing designs.
Methods
Encoderr Type
Decoder
Type
Fessibility Scheme
Sizetm)
0bj
TSP-100
Gapl
Timel
Size(m)
Obj.1
CVRP-20
Gapl
Time]
DACT (2-opt)
d=61 AF
DACT
masking
0.281
7,933
1.73%
131s
0.281
6.172
0.14%
58s
DACT-U (2-apt)
d- d-128.MLP M.P....---yybb.. Att
DACT
masking
0.633
7.822
0.32%
171s
0.633
6.171
0.13%
61s
DACT-U-CIRE
d= 12...L....ybbbbbb..
DACT
GIRE
0.633
7,822
0.32%
171s
0.633
6.168
0.08%
59s
NeuOpr (K 2)
ASy
RDS
masking
0.683
7.817
0.24%
122s
0.683
6.180
0.27%
60s
NcuOpt-GIRE (K 20
d= 1=128MLP Au
RDS
GIRE
0.683
7.817
0.24%
122s
0.685
6.167
0.05%
S3s
NeuOpt-GIRB (K 4))
de 28.228 PSyyll-AA
RDS
GIRE
0.683
7.798
0.00%
1336
0.685
6.163
0.00%
60s
Table 3: Effects of GRUs, move Table 4: Effects of dynamic data augmentation (D2A).
6,1725
stream Ja and edge stream X.
OnL Value
6.1
Methods
Size(M)
TSP-100
Obj.
Size(M)
CVRP-30
Obj-
Inference Type
TSP-100
Gapl.
CVRP-100
Gapl.
6.1675
6.1650
Wio-GRUx
0468
7,804
0.470
6.165
wio-D2A (T-5k)
0.09%
1.00%
wlosp
0.617
7,806
0.620
6.165
w-D2A (T-5k)
0.05%
0.87%
6.1625
wib-A
0.67
7,799
0.620
6,164
w/-122A (T=10k)
0.04%
0.71%
Rase
-VI
+ES
VI+ES
Ours
7.798
0.685
6.163
w-DZA (T=10k)
0.02%
Figure 4: Effects of GIRE designs.
Effectiveness analysis. To further reveal the effectiveness of our RDS decoder and GIRE, we conduct comparison with the offte-of-the-ar L2S solver, DACT [9]. We upgraded it to DACT-U for faimess, which uses identical embeddings and encoders as our NeuOpt. The evaluation criteria include the model size, the best objective value (averaged over four training runs with T=1k inference steps on Ik validation instances), the gaps w.r.t. the best solver, and the run time. As evidenced in Table 2, our GIRE scheme consistently boosts both NeuOpt and DACT-U on CVRP-20, reducing the mask computation time while marginally increasing model size, which reveals the generality of our GIRE. Moreover, when all are used for 2-opt, NeuOpt (K- = 22, for TSP) and NeuOpt-GIRE (K- 2, for CVRP) surpass DACT-U (for TSP) and DACT-U-GIRE (for CVRP), respectively, with less run time. This is further amplified by increasing K 4 for NeuOpt at the cost of slightly increased run time.
6.2 Ablation studies
Ablation RDS decoder. In Table 3, we remove the key components of our RDS decoder including
the GRUs, the move stream f4, and edge stream X, respectively, and report the model size and the best objective value averaged over four training runs. As depicted, all components largely contribute to effective contextual modeling for parameterizing the k-opt decoder on both TSP-100 and CVRP-20.
Ablation on D2A inference. In Table 4, we gather the gaps (similar to Table 1) with and without our D2A design when single data augmentation is leveraged during inference with T=5K and T=10K. The results confirm that our D2A consis- tently enhances the inference on both TSP-100 and CVRP- 100.
8.50
Obj. Valuue
Ours
8.25
8.00
Ablation on GIRE designs. We examine scenarios, consid- ering the inclusion or exclusion of Violation Indicator (VI), Exploration Statistics (ES), and Reward Shaping (RS), using eight combinations of them during the training of NeuOpt on CVRP-20. We draw the box plots of the best objective values achieved across eight training runs for each scenario in Figure 4.
7.75
20
40
60
80
100
Training Epoch
(a) Effects of S-move.
wib-E-mure Ours
7.88
Obl. Value
7,85
We can conclude that: 1) the supplement of VI consistently en- hances training outcomes, irrespective of the presence of RS; 2)
7.83
the supplement of ES may bring improvement only when RS is present; and 3) our complete GIRE design (VI+ES+RS) yields the lowest objective values and demonstrates superior stability.
7,80
K-2
K-3
K-4
K-5
K-6
Varying K
(b) Effects E-move.
Ablation on basis moves. In Figure 5 (a), we depict the training curves of NeuOpt on TSP-100 with and without the learnable S-move. When removing the learnable S-move and opting for a random selection of the anchor node Fa, a significant degradation in the final performance can be observed, underscoring the necessity of the learnable S-move design. Meanwhile, Figure 5 (b)
Figure 5: Effects of basis moves.

---

Table 5: Generalization (10 runs) on TSPLIB.
Table 6: Generalization (10 runs) on CVRPLIB.
AM -unix
POMO
AMDKD
DACT (sol
Ours (sk).10k)
AM -nix
POMO
AMDKD
DACT (sol.10k)
Ours (skl.10k)
-mi
(POMO)
Avg.l
Best]
Avg-4
Best,
-mix
(POMO)
Avg.L
Best]
Avg-1
Best,
19.59%
0.92%
1.88%
3.29%
1,5%
0.85%
0.50%
15.8%
8.05%
5.77%
5.21%
3.68%
4.80%
3,27%
Table 7: Results on N 200.
Table 8: Influence of K.
6.1675
Oll, Vilue
(Ap
Methods
Gap.l
TSP-200
Time.]
Gap-4
CVRP-200
Time..
Trinfa
T(tr
Gupl
6.1650
2
2m002s
20m
0,30%
LKH (20, 311
0.00%
2.3h
1.17%
21.08
3
2m07s
21m
0.15%
6.1625
Ours (D2A=5,T-Idk)
0.04%
4.7h
0.68%
9.6b
2m1
0.08%
0.01
0.05
Ours (D2A=5,T-20)
Ours (D2A=5,T=300)
0.02%
0011
14.1h
9.4h
0.08%
0.39%
19:26
1.23
6
2m16s
2m19s
25m
24m
0.00%
0.01%
Figure 6: Influence a and 8
presents the pointplots with confidence intervals that show the performance of our NeuOpt on TSP- 100 with and without E-move during decoding across varying preset K. When E-move is absent (dotted blue line), the model, downgraded to performing fixed K-opi only, exhibits diminished performance on larger K. Conversely, our NeuOpt (solid orange line) could further benefit from a larger K, due to its flexibility in determining and combining different lt across search steps.
6.3 Generalization and scalability studies
In Table 5 and Table 6, we further evaluate the generalization capability of our NeuOpt models on more complex instances from TSPLIB [55] and CVRPLIB [56], respectively. Our NeuOpt achieves lower gaps than DACT [9] and L2C solvers (AM [3] and POMO [4]), and even shows superiority over the AMDKD method [11] that is explicitly designed to boost the generalization of POMO through knowledge distillation. Beyond generalization, our NeuOpt also exhibits notable scalability. As shown in Table 7, when trained directly for size 200, NeuOpt finds close-to-optimal solutions and still surpasses the strong LKH-3 solver [20] on CVRP-200. Note that existing L.2S solvers, e.g., DACT [9] may struggle with training such scales. More details and discussions are available in Appendix E.
6.4 Hyper- parameter studies
Influence of preset K. In Table 8, we display the performance of NeuOpt on TSP-100, as well as the corresponding inference time (T=lk) and the training time (per epoch) for varying K values. The results highlight trade-offs between better performance and increased computational costs.
Influence of GIRE hyper-parameters. Figure depicts the influence of and 3 in Eq. (4) on CVRP-20, where we fix one while varying the other, investigating both extremely smaller (0.01) and larger (0.1) values. The results suggest that more effective reward shaping occurs when the weights are moderate. Please refer to Appendix D for discussions on more GIRE prper-parameters
Conclusions and limitations
In this paper, we introduce NeuOpt, a novel L2S solver for VRPs, that performs flexible k-opt exchanges with a tailored formulation and a designed RDS decoder. We also present GIRE, the first scheme transcend masking for constraint handling based on feature supplement and reward shaping, enabling autonomous exploration in both feasible and infeasible regions. Moreover, we devise a D2A augmentation method to boost inference diversity. Despite delivering state-of-the results, our work still has limitations. While NeuOpt exhibits better scalability than existing L2S solvers, it falls short against some L2P solvers (e.g., [6. 7]) for larger-scale TSPs. Possible solutions in future works include: 1) integrating search space via heatmaps as predicted in [6, 15], 3) adopting more scalable encoders [61, 62], and 4) refactoring our code with opttiiee CUDA libraries as did in [7, 15]. Besides enhancing
strategies as per [6. 57-6776, 2) reducing
scalability, future works can also focus on: 1) applying our GIRE to more VRP constraints and even beyond 1.2S solvers, 2) integrating our method with post-hoc per-instance processing boosters (e.g., EAS [5]) for better performance, and 3) enhancing the generalization capability of our NeuOpt on instances with different sizes/distributions (c.g., by leveraging the frameworks in [11, 63]).
10

---

Acknowledgments and Disclosure of Funding
This research was supported by the Singapore Ministry of Education (MOE) Academic Research Fund (AcRF) Tier grant.
References
Paolo Toth and Daniele Vigo. Vehicle routing: problems, methods, and applications. SIAM press, 2014.
[2] Cong Zhang. Yaoxin Wu, Yining Ma, Wen Song. Zhang Le, Zhiguang Cao, and Jie Zhang. A review on learning solve combinatorial optimisation problems in manufacturing. IET Collahorative Intelligent Manufacturing, 5(1)xe 2023.
[3] Wouter Kool, Herke van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations, 2018.
[4] Yeong-Dac Kwon, Jinho Choo, Byoungjip Kim, Iijoo Yoon, Youngjune Gwon, and Seungjai Min. POMO: Policy optimization with multiple optima for reinforcement learning. In Advances in Newral Information Processing Systems, volume 33, pages 21 1188-21198, 2020.
[5] André Hottung, Yeong- Dac Kwon, and Kevin Tierney, Efficient active search for combinatorial optimization problems. In International Conference on Learning Representations, 2022.
[6] Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan 7ha. Generalize small pre-trained model to arhitrarily large TSP instances. In AAAI Conference Artificial Intelligence, 2021.
[7] Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. DIMES: A differentiable meta solver for combinatorial optimization problems. In Advances Neural Information Processing Systems, volume 35, pages 25531- 25546, 2022.
[8] André Hottung and Kevin Tiemny. Neural large neighborhood search for routing problems. Artificial Intelligence, page 103786, 2022.
[9] Yining Ma, Jingwen Li, Zhiguang Cao, Wen Song. Le Zhang, Zhenghua Chen, and Jing Tang. Learning to iteratively solve routing problems with dual-aspect collaborative transformer. In Advances in Neural Information Processing Systems, volume 34, pages 11096-11 107, 2021.
[10] Qingfu Zhang Xi Lin, Zhiyuan Yang. Pareto set learning for neural multi-objectivee combinatorial opti- mization. In International Conference on Learning Representations, 2022.
[11] Jieyi Bi, Yining Ma, Jiahai Wang, Zhiguang Cao, Jinbiao Chen, Yuan Sun, and Yeow Meng Chee. Learning generalizable models for vehicle routing problems via knowledge distillation. In Advances in Neural Information Processing Systems, pages 22122-311222 31238, 2022.
[12] Yining Ma, Jingwen Li. Zhiguang Cao, Wen Song, Hongliang Guo, Yuejiao Gong, and Yeow Meng Chee. Efficient neural neighborhood search for pickup and delivery problems. In International Joint Conference on Artificial Intelligence, pages 4776-477 4784, 2022.
[13] Minsu Kim, Junyoung Park, and Jinkyno Park. Sym-nco: Leveraging symmetricity for neural combinatorial optimization. In Advances in Neural Information Processing Systems, volume 35, pages 1936-1949, 2022.
[14] Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arxiv preprint arxiv:1906.01222 ArXiV, 2019.
[15] Zhiqing Sun and Yiming Yang. Difuseo: Graph-based diffusion solvers for combinatorial optimization. arxiv preprint mxxi:2332.008224 ArXiV, 2023.
[16] Paulo da Costa, Jason Rhuggenaath, Yingqian Zhang, and Alp Eren Akçay. Learning 2-opt heuristies the traveling salesman problem via deep reinforcement learning. Asian Conference on Machine Learning, pages 465 480, 2020.
[17] Jingyan Sui, Shizhe Ding, Ruizhi Liu, Liming Xu, and Dongho Bu. Learning 3-opt heuristics for traveling salesman problem via deep reinforcement learning. In Asian Conference on Machine Learning, volume 157, pages 1301-1316, 2021.
[18] Zbigniew Michalewicz et al. Do not kill unfeasible individuals. In Proceedings of the Fourth Intelligent Information Systems Workshop, pages 110- (20,12,,110 1995.

---

[19] Fred Glover and Jin-Kao Hao. The case for strategic oscillation. Annals of Operations Research, 183: 163-173, 2011.
[20] Keld Helsgaun. LKH-3 (3.0.7), 2017. URL
3/.
[21] Thibaut Vidal. Hybrid genetic search for the evrp: Open-source implementation and swap" neighborhood. Computers & Operations Research, 140:105,43, 2022.
[22] Oriol Vinyals. Meire Fortunato, and Navdeep Jaidy. Pointer networks. In Advances in Neural Information Processing Systems, volume 28, pages 2692-2700, 2015.
[23] Irwan Bello, Hieu Pham, Quoe V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. In International Conference on Machine Learning (Workshop). 2017.
[24] Mohammadreza Nazari, Afshin Oroojlooy, Martin Takáč, and Lawrence V Snyder. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems, pages 9861-9877 2018.
[25] Hanjun Dai, Elias B Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances Neural Information Processing Systems, pages 6351-6361, 2017.
[26] 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 real-world graphs linear time. In International Conference on Machine Learning and Applications (ICMIA), pages 19-24, 2020.
[27] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Step-wise deep learning models solving routing problems. IEEE Transactions on Industrial Informatics, 17(7):4861 2020.
[28] Liang Xin, Wen Song, Zhiguang Cao, and Jie Zhang. Multi-decoder attention model with embedding glimpse for solving vehicle routing problems. In AAAI Conference on Artificial Intelligence, pages 12042-12049, 2021.
[29] Yunqiu Xu, Meng Fang. Ling Chen, Gangyan Xu, Yali Du, and Chengqi Zhang. Reinforcement learning with multiple relational attention for solving vehicle routing problems. IEEE Transactions on Cybernetics, 52(10):11105
11120, 2022.
[30] Jingwen Li, Liang Xin. Zhiguang Cao, Andrew Lim, Wen Song, and Jie Zhang. Heterogencous attentions for solving pickup and delivery problem via deep reinforcement learning. IEEE Transactions Intelligent Transportation Systems, 23(3):2306 2315, 2022.
[31] Jingwen Li, Yining Ma, Ruize Gao, Zhiguang Cao, Andrew Lim, Wen Song, and Jie Zhang. Deep rein- forcement learning for solving the heterogeneous capacitated vehicle routing problem. IEEE Transactions on Cybernetics, 52(12): (1(12):35722. 13585,, 2022.
[32] Yan Jin, Yuandong Ding, Xuanhao Pan, Kun He, Li Zhao, Tao Qin, Lei Song, and Jiang Bian. Pointerformer: Deep reinforced pulti-pointer transformer for the traveling salesman problem. In AAAI Conference on Artificial Intlligence, 2023.
[33] Minsu Kim, Jinkyoo Park, and Joungho kim. Learning collaborative policies to solve np-hard routing problems. In Advances in Neural Information Processing Systems, volume 34, pages 10418-10430, 2021.
[34] Jinho Choo, Yeong-Dae Kwon, Jihoon Kim, Jeongwoo Jae, André Hottung, Kevin Tiemney, and Youngjune Gwon. Simulation-guided beam search for neural combinatorial optimization. In Advances in Neural Information Processing Systems, volume 35, pages
2022.
[35] Xinyun Chen and Yuandong Tian, Learning to perform local rewriting for combinatorial optimization. In Advances in Neural Information Processing Systems, volume 32, pages 6281 16292, 2019.
[36] Hao Lu, Xingwen Zhang, and Shuang Yang. A learning-based iterative method for solving vehicle routing problems. In International Conference on Learning Representations, 2019.
[37] Minjun Kim, Junyoung Park, and Jinkyoo Park. Learning to CROSS exchange to solve min-max vehicle routing problems. In International Conference on Learning Representations, 2023.
[38] Grigorios D Konstantakopoulos, Sotiris P Gayialis, and Evripidis P Kechagias. Vehicle routing problem and related algorithms for logistics distribution: A literature review and classification. Operational Research, pages 2033 2062-2 2020.
12

---

[39] Yaoxin Wu, Wen Song. Zhiguang Cao, Jie Zhang, and Andrew Lim. Learning improvement heuristics for solving routing problems. IEEE Transactions on Neural Networks and Learning Systems, 537)):007-5569, 2021.
[40] Benjamin Hudson, Qingbiao Li, Matthew Malencia, and Amanda Prorok. Graph neural network guided lo- cal search for the traveling salesperson problem. In International Conference Learning Representations, volume 35, 2022.
[41] Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International Conference on Machine Learning, pages 2256-2265, 2015.
[42] Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep policy dynamic programming for vehicle routing problems. In International Conference on Integration of Constraint Programming. Artificial Intelligence, and Operations Research, pages 190-213, 2022.
[43] André Hottung, Bhanu Bhandari, and Kevin Tiemnyy Learning latent scarch space for routing problems using variational autoencoders. In International Conference Learning Representations, 2021.
[44] Jiuxia Zhao, Minjia Mao, Xi Zhao, and Jianhua Zou. A hybrid of deep reinforcement learning and local search for the vehicle routing problems. IEEE Transactions Intelligent Transportation Systems, 22(11): 7208-7218, 2021.
[45] Renchi Zhang, Runsheng Yu, and Wei Xia. Constraint- policy optimization to solve the vehicle routing problem with time windows. Information Technology and Control, 51(1):126-11) 138, 2022.
[46] Hang Zhao, Qijin She, Chenyang Zhu, Yin Yang, and Kai Xu. Online 3d bin packing with constrained deep reinforcement learning. In AAAI Conference on Artificial Intelligence, pages 741-749, 2021.
[47] Ashish K Jayant and Shalabh Bhatnagar. Model-based safe deep reinforcement learning via a constrained proximal policy optimization algorithm. Advances in Neural Information Processing Systems, 35:24432- 24445, 2022.
[48] Linrui Zhang, Li Shen, Long Yang, Shixiang Chen, Xueqian Wang, Bo Yuan, and Dacheng Tao. Penalized proximal policy optimization for safe reinforcement lcarning. In International Joint Conference on Artificial Intelligence, pages 3744-3750, 2022.
[49] Shen Lin and Brian W Kernighan. An effective heuristic algorithm for the traveling- salesman problem. Operations research, 21(2):498-516. 1973.
[50] Keld Helsgaun. An effective implementation the lin-kernighan traveling salesman heuristic. European journal of operational research, 126(1):106-11)) 130, 2000.
[51] Keld Helsgaun. LKH-2 (2.0.9), 2018. URL http:: ruc. hacc.c///keeldreeercc/iiit
[52] Kyunghyun Cho, Bart van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Sehwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder- for statistical machine translation. In Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1724-1722 1734, 2014.
[53] David Ha, Andrew M. Dai, and Quoe V. Le. Hypernetworks. In International Conference Learning Representariioss 2017.
[54] David L. Applegate, Robert E Bixby, Vašek Chvátal, and William J Cook. Concorde TSP Solver, 2020.
URL http:/ http::///wwww/ htttt/ttttthtttt//////t/tt//thhh uwaterloo.
[55] Gerhard Reinelt. TSPLIB-A traveling salesman problem library. ORSA journal on computing, 3(4): 376-384, 1991.
[56] Eduardo Uchoa, Diego Pecin, Artur Pessoa, Marcus Poggi, Thibaut Vidal, and Anand Subramanian. New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research, 257(3):845-88) 2017.
[57] Qingchun Hou, Jingwei Yang. Yiqiang Su. Xiaoqing Wang. and Yuming Deng. Generalize learned heuristies to solve large-scale vehicle routing problems in real-time. In International Conference on Learning Representations, 2023.
[58] Hanni Cheng, Haosi Zheng, Ya Cong, Weihao Jiang, and Shiliang Pu. Select and optimize: Learning to solve large-scale tsp instances. In International Conference on Artificial Intelligence and Statistics, pages 2219-1231 2023.
13

---

[59] Xuanhao Pan, Yan Jin, Yuandong Ding. Mingxiao Feng, Li Zhao, Lei Song, and Jiang Bian. H-TSP: Hieranchieally solving the large-scale travelling salesman problem. In AAAI Conference Artificial Intelligence, 2023.
[60] Sirui Li. Zhongxia Yan, and Cathy Wu. Learning delegate for large-scale vehicle routing. Advances in Neural Information Processing Systems, 34:26198 112111991121111.1 2021.
[61] Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for general, powerful, scalable graph transformer. Advances Neural Information Processing Systems, volume 35, pages 14501-14515, 2022.
[62] Sebastian Jaszezur, Aakanksha Chowdhery, Afroz Mohiuddin, LUKASZ KAISER. Wojeiech Gajewski. Henryk Michalewski, and Jonni Kanerva. Sparse is enough in scaling transformers. In Advances in Neural Information Processing Systems, volume 34, pages 9895-9907, 2021.
[63] Jianan Zhou, Yaoxin Wu, Wen Song. Zhiguang Cao, and Jie Zhang. Towards omni genera neural methods for vehicle routing problems. In International Conference on Machine Learning, 2023.
14

---

Learning to Search Feasible and Infeasible Regions of Routing Problems with Flexible Neural k-Opt (Appendix)
A Action factorization examples
Figure depicts examples of our factorization method using combinations of basis moves (S-move, I- move, and E-move) to represent different k-opt exchanges. Initiated from a TSP-9 instance (leftmost), we list examples from 1-opt 4-opt, where the number of I-move corresponds varying k values, leading to distinct new solutions (rightmost). This demonstrates the flexibility of our factorization.
(K(e2) ((tua))
2not (50s) E(taa)
Kigh =l((t)=ta) E(ban) (1(())))s))
S(rg]i (1 ((g)) (14)))))
(5(kg) ((ts))
5t0ah: en" 106): eltl(x, 106). eni(xy 16))
sopt (ee EDban))
Kich et and Kas): e"to un). Righ e"Ios sta) R0taa): el sh))
Sirg en (t)) K0a) erllo exy less (39((1))11)) e"")ie"" et
Figure 7: Examples of using the basis moves to factorize 1-opt (void action), 2-opt, 3-opt, and 4-opt.
B
NeuOpt encoder
Given state $; = {g, tı, rhof), where & is the current instance, тę is the current solution, and 7, is the best-so-fil far solution before step t, the encoding process first translates the raw features of state into node embeddings. These embeddings are subsequently refined through = 3 stacked encoders.
Fearure Embedding. Building upon the dual-aspect representation design from [12]. we embed state features denoted as 1/ 1/ 7. ((p])) {p] (p:]) into two separate sets of node embeddings: Node Feature Embeddings (NFEs) to encode (G))= = { and Positional Feature Embeddings (PFEs) to encode ()(T)) - }. The NFEs, denoted as {h Jx, a set of d-dimensional vectors, each of which embeds d, dimensioonl
raw features yp node x; at step To obtain d) for enhanced representation. The PFEs, denoted as {g. Ja,ev, are set d-dimensional vectors, each of which embeds positional features p of at step 1, derived from the position of in the current solution тt. Following [9], we employ the Cyclic Positional Encoding (CPE) to generate a series of cyclic embeddings in d-dimensional space. These CPE embeddings then used initialize g! correspondingly, so as to capture the topological structure of the nodes in the current solution 7:.
himit, we upgrade linear projection used in [12] into the MLP with structure of (d,,
Problem-specific raw node features sp.. For TSP, node features off of contains its two- dimensional coordinates (i.e., d, 2): For CVRP, sot contains six features (i.e., 66= including 1-2) its two-dimensional coordinates, 3) the demand of node z;, 4) the sum of demand of the corre- sponding sub-tour before node x; (inclusive), 5) the sum of demand of the corresponding sub-tour after (exclusive), and 6) an indicator function to signify whether node is customer node. When GIRE is applied, we enrich of with two Violation Indicator (VI) features, i.e., d, =8.
Note that the rad is leveraged in the reward function and the critic network, but not the policy network.

---

Stacked encoders. Following the encoders in [9, 12], we use Transformer-styled encoders with Synthesis Attention (Synth-Att) to refine the embeddings {h]r" V and (gi j.z V. where PFEs serve as auxiliary embeddings that bolster the representation learning of NFEs. After the encoding, unified set of embeddings (h,) 2,, obtained, which then inputted our recurrent dual-stream (RDS) decoder for k-opt action decoding (see Section 4).
C Training and inference algorithms
C.1 Training algorithm
Algorithm Reinforcement learning algorithms for NeuOpt
Input: policy network оe. critic network Vg. PPO objective clipping threshold 0, learning rate Ijo, Nl. learning rate decay rate ç, number of PPO inner loops Q2 training steps Train number of epochs E, number of batches per epoch B, curriculum learning (CL) scalar &
E do 2: for batch = to B do
1: for epoch
3: Randomly generate batch of training instances D { and their initial solutions {Te):
4: CL: Improve {T,} to { by runing the current policy Ta for T = spoch/f steps:
5:
Get initial state so based on {5/} for each instance in the current batch;
6:
t
< 0:
7:
while < T irain do
8:
Run policy To on each instance and get ((se,0g;r)) H4n-1 where de ~o (sp])));
9:
I e- + n, Wold + wo, Vold f- up:
10:
for j = to do
11:
for E 11,1.... n do
13:
Rw t- ry + + Ru
14:
Ap t- Ry - R (s():
end for
16:
Compute RL loss LPo using Eq. (6) and critic loss Crriic using Eq. (7);
0 0- 0 no V CPFO, Φ 77 V Liitiie
18:
end for end while
19:
20:
end for
21:
+ STl., No + S76
end for
As detailed in Algorithm 1, adapt the n-step proximal policy optimization (PPO) with curriculum learning (CL) strategy used [9, 12] to train our NeuOpt. For our GIRE scheme, we consider origin reg and uoonus to fit the respective reward shaping terms in Eq.(4), so learning separate critics U/
as to better estimate the state values. In light of this, when GIRE is applied, we update Algorithm by: 1) duplicating lines 11, 13-14 to compute i2 R. and fehomus as well as A A and Ábomus at the same time; 2) updating the line 16 to replace Eq. (6) and Eq. (7) into Eq. (8) and Eq. (9), respectively; and update line 17 accordingly where all the critics share the same learning rate na.
1
min To(ar(sv) Ae, Clip
Te(ayr (s)))sss))))))) 1- 1, 1 1+ Ac
C
PPO
(6)
D
n
Totd(ar(ss)
(ata(ar((s))
d'tt-n
max (pea(ee) Rec clip - Rs. 12) P))
CCitte
- J
D
D P'=t-n
L
GIRE
min
To(arlsw)
(Aorigia Apod
Aboous)
D
Tota(ar str)
D
(8)
ne (ar (sv)
(mpriiii + Appd + +Apows)) )).
Clip
(a (8x)) 1 0, 1+0

---

CGIRE
max
n
origin
(se)
Rif
Rorigin
2
+
U/ (sr)) -Ra
+ -ib
1/ (sv)
Rhomus
2
(9)
origin.llip
(ser)
Rig
Aorigin
2
(p(c)l((ss))
2
+ 0
bonus,clip
(sv.)
Alyoous
C.2 Inference algorithm
In our previous work [12], the data augmentation was incorporated during inference to boost the search diversity. The rationale is that a specific instance, G, can transformed different ones, yet still retain the identical optimal solution. These augmented instances can be solved differently by the trained model in parallel, thereby enhancing the diversity of the search for better performance. Specif- ically, each augmented instance is generated by consecutively executing four predetermined invariant augmentation transformations as listed Table where the execution order and configurations used for each transformation randomly determined on the fly following Algorithm 2.
Table Descriptions of the four invariant augmentation transformations (retrieved from [12]).
Transformations
Formulations
Configurations
flip-x-y 1-x 1-y
(x', (y,
perform or skip perform or skip
(x' y
(1 x,
(x', yy
(x.1-8)
perform or skip
x
x cos 0 yin 0
rotate
0 E {0, TT 1/,, n, 3m 2
x sin I + y cos 0
Algorithm 2 Augmentation (retrieved from [12])
Input: Instance
Output: Augmented instance g'
1: g' 9;
2: A + RandomSSuffle(llip--> (ffip---y. 1-x, I-y, rotate);;
3: for each augment method AA do
4: 3(j) < RandomContig())
5: g' + perform augment j on g' with config 3j));
6: end for
However, such augmentation is performed only once at the start of the inference, making the augmentation fixed across the search process. We thus propose Dynamic Data Augmentation (D2A). suggests generating new augmented instances with different augmentation configurations each time when the solver fails to find a better solution within consecutive maximum of T22 steps (i.e., we consider the search to be trapped in local optima). This allows the model to explicitly solve instances differently once it gets trapped in the local optima, thus promoting even more diverse search process. Note that the proposed D2A is generic to boost most L2S solvers, and even has the potential to boost L2C solvers when equipped with post-hoc per-instance processing boosters such EAS [5]. In Algorothm 3, we summarize the D2A procedures where we note that the loops in line and line can be run in parallel during practical implementations. For example, when use "D2A=5" per in Table 1, it means that for each instance G, there are 5 augmented instances (91, G2, G3, G4, Gs being solved simultaneously. Each of these instances has its counter 7stali and the best-so-far solution bat to track whether the search (for the particular instance G,) has fallen into local optima.
D Additional discussions on GIRE scheme
Separate critic networks. As per Appendix C, we use separate crities GIRE, We now introduce their detailed architectures. During the critic value estimation, first upgrade embeddings {

---

Algorithm 3 Dynamic Data Augmentation (D2A)
Instance 9, policy network To, inference step T, number of augments D2A, maximum number consecutive steps allowed before considering the search trapped in local optima T2za Output: Best solution found during solving all the augmented instances 9;
Input:
for i
D2A do
2: Get an augmented instance: Gi + Augmentation(();
3: Get random solution 7g,0 and set as the best-so-far solution for 9;: 7hat <- 75,05
4: Set counter: T: 0;
5: end for
6: for m..t=1...,TT
do
7:
for = .2A do
8:
Run one inference step to get new solution Tie for Gj using policy network mp; if new solution Tı is a new best-so-far solution for instance G; then
9:
10:
Update the best-so-far solution: bsf + T,
11:
Reset counter: T f- 0:
else Increment counter: T:tall Tuall + 1; end if
13:
15:
if T 2 TDA then
Get new augmented instance: 9, < Augmentation(9): Reset counter 7,ttal <- 0
17:
18:
end if
19:
end for
20:
end for
(from the encoders of TT) to {hx Ja, using a vanilla multi-head attention layer. The (h,} are then fed into mean-pooling layer [39], yielding compressed representations as follows,
J. = h Wooco + mean [fhttave)) irGiobel
(10)
where W E RRx are trainable matrices, and the mean and max are element- wise operators. All origin zeg and bonus then share these representations { as parts of their inputs. Specifically, critics o U
origin is computed via a four-layer MLP in Eq. (11) with structure (d + 1, d, 2> 1) which leverages &
f(rba) additional features; 2/ is computed via a four-layer MLP in Eq. (12) with structure (d+ 10, d, d 1) which leverages frrh") and ES features J. as additional features; and u is computed 2.
via four-layer MLP in Eq. (13) with structure (d 1, d, d 1) which leverages the best-so-far cost w.r.t. e-F regions f(r w(rbef-wntte) as additional features All MLPs use the ReLU activation function.
origin v
MLP (max((00)a..es)) mean| (6 h,, fT? (T.
(11)
MLP 02 (max
[ 2. wwa. ( ) (T. J..
(12)
bonus
MLP da (max(fú) (x.ev) mean| [ e..ev] [( ())
(13)
Illustrations of extreme search behaviour and our GIRE efficacy. Recall that our GIRE considers
reward-shaping terms to encourage search within more promising feasibility boundaries and regulate extreme search behaviours using an entropy measure of the estimated conditional transforming probabilities (2( = P(r' E E U)) and (. P(r' E F F). Figure 8 depicts the persistence of extreme search behaviour when RS is absent while validating the efficacy of our reward shaping (RS) in GIRE. We conduct training with and without RS, recording the convergence curves of the objective values (with mean and confidence intervals) in Figure 8(a), the detailed objective values per run in Figure 8(b). the estimated probability (((FF) Figure 8(c), and the estimated probability (L(()))) in Figure 8(d). As revealed in Figure 8(a), without RS, the runs show unstable convergence and poorer final objective values. This can be attributed to higher P (FF and lower (2 (4) as shown in Figure 8(c) and Figure 8(d), indicating biased search preference towards feasible regions
"Given that GIRE additional features, the MDP states should be augmented accordingly.

---

and inefficient exploration in infeasible regions. In the worst case, training may fail to converge to lower objective values due to extremely low P. (2(()) (below 0.1 shown Figure 8(d)), indicating extreme search behaviour and entrapment in local optima. Conversely, GIRE fosters moderate search behaviours and promotes exploration in infeasible regions (especially for the boundaries), leading to significantly improved training curves with reduced variance and lower objective values.
6.20
6.20
1.40
1.00
Obj. Valee
6.19
Ouze
Olk Valler
6.19
P fleas to fout.)
0.75
Pfffaa to liree))
0.75
6.18
6.18
0.50
0.50
0.25
0.25
50
75
100
100
0.00
100000
200000
300000
0.00
100000
200000
300000
Training Epoch
Truining Epach
Grodicut Step
Step
(a) Objective values.
(b) Objective values.
(c) (F(FFF)
(d) Pa(UR))
Figure 8: Training curves of our GIRE with and without RS on CVRP-20 (8 runs).
Influence of e. We employ a deterministic rule to decide i.c., e Ç N Wustomerr x (ö/2), A), where Ç is coefficient within [0, 1], A is the vehicle capacity, and represents the average customer demands. This formula implies that the total violation corresponds to scenarios where Ç-ratio of customers, each with the average demand, breaches the constraint. Empirically, we set 0.1. Figure illustrates the impact of varying Ç.
Value
6.1640
0.01
0.05
0.1
0.15
0.2
Figure 9: Impact of varying Ç.
Influence of and C2. Recall that in the entropy measure defined by Eq. (5), introduce two syper-parameters 61 and 02 to shape the entropy measure pattern H[]] where the measure H[P] is used to penalize extreme search behaviours, particularly when values of approach 0 or 1. Figure 10 illustrates how c1 expands the penalty range, while larger с constricts the penalty range. Similarly, when eı is fixed, a smaller or larger C2 will also control the shape the patterns. Empirically, we set the values of c₁ 0.5, C2 2.5 as only penalize extreme search behaviour if the feasibility transition probability is outside the [0.25, 0.75] range. In Figure 11, we investigate the influence of cı, on the training stability of our NeuOpt-GIRE approach CVRP-20. Results show that they may affect training stability (thus no need for extensive tuning in practical usage).
C1 and c2 influence the shape of P]. When C2 is fixed, smaller
Entropy measure
Entropy measure
Entropy measure
1.0
1.0
1.0
0.9
0.5
0.5
0.8
0.0
0.0
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
Probability
Probability
Probability
(a) c1
0.1, C2
(b) c1
= 0.5, 02 2.5
(c) c1
1.0, 02
Entropy mensure
1.0
Entropy mensure
1.0
Entropy measure
1.0
0.5
0.5
0.5
0.0
0.0
0.00
0.25 0.50 0.75
1.00
0.00
0.25
0.50 0.75 1.00 Probability
0.00
0.25 0.50 0.75 1.00
Probability
Probability
(d) C1 0.5, C 1.5
(c) 0.5, C2 2.5
(f) c1 0.5, 02 3.5
Figure 10: Effects of and C2 on H[ pattern: (a)-(c) fix c2 2.5 and vary c1: (d)-(f) fix 0.5
and vary C2. Compared the pattern (b) and (e) used in this paper, varying ei and C2 either constricts the penalty range, shown in (c) and (f), or expands the penalty range, shown in (a) and (d).
5

---

6.20
cl-d., c2-1.5 (esgunded)
Obj. Value
c1-9.5 c2-1.5 (original)
clmd.5, c2-18 (comstriceed
6.18
6.16
60
100
Training Epoch
Figure 11: Influence of constricted and expanded patterns of H[P] on the training stability.
Applying GIRE to other constraints. Our GIRE can be viewed an important early attempt that moves beyond the pure feasibility masking to autonomously explore both feasible and infeasible regions during the search. To adapt GIRE for a particular constraint, we suggest the following:
For Feature Supplement, simply binary indicator functions can be employed to discern specific constraint violations of each node in the solution, thereby forming the Violation Indicator (VI) features. For example, VI can indicate nodes (customers) in the solution that breach their time window the pickup/delivery precedence constraints. For the Exploration Statistics (ES) features, they can be retained as originally conceptualized since they are based on historical exploration records, rather than specific constraints.
For Reward Shaping, it can be retained as originally conceptualized. We suggest characterizing the e-feasible regions by a fraction of nodes that do not adhere to the constraints, i.c., ( 0.11.
E
Additional experimental results
E.1 Details of implementation
Hyper-parameter details. We use 128, Tiza = 10, This 25 for NeuOpt, and employ 4 attention heads in both the encoders and critics. The ReLU activation function is utilized for MLPs within the network. In line with the training algorithms in [9, 12]. retain their dyper-paramest ensure an equivalent training amount. Training involves E = 200 epochs and epoch, with batch sizes of 512 (TSP) and 600 (CVRP). For TSP, we use n n 4, Timan 200; and for CVRP, we use n 5, 5, T irainn 250. The PPO inner loops is Ω = 3 and the clip threshold is = 0.1. The Adam optimizer is employed with learning rates 1/0 8 10-5 for To. 7/-- as well as a decay rate ç 0.985. The reward discount factor y is set to 0.999 for both problems. Besides, we empirically set approach-specific parameters: the gradient norm of NeuOpt is clipped at 0.05 in all cases, and the curriculum learning scalar È is set as 1, 0.5, and 0.25 for sizes 20, 50, and 100, respectively. The training time varies depending on the specific problem and size, e.g., CVRP requires about 4 days for size 20 (1 GPU). 5 days for size 50 (2 GPUs), and 8 days for size 100 (4 GPUs), which are around half the time taken as reported in DACT [9] and POMO [4] on CVRP100.
to 20 batches per
10-5 for ué-
Setup details. We follow Kool et al. [3] to sample all training and test instance coordinates within the unit square (0,
(0, 1] uniformly. For CVRP, the demands of customers are uniformly sampled from the set {1, 2.... 9) and the vehicle capacity is set to 30, 40, and 50 for sizes 20, 50, and 100 respectively (we thus estimate 5 as 5/30, 5/40, 5/50 in our GIRE, respectively). To facilitate GPU parallelization given the varying lengths of CVRP solutions, we employ the dummy depots design in [9, 39] for length padding, where depots are duplicated during both training and inference. Same as DACT [9], we include 10, 20, and 20 dummy depots for CVRP sizes of 20, 50, and 100 respectively.
Baseline details. We provide details the compared neural baselines. For the ones with #, found certain issues in their code, which may lead to the underestimation of reported gaps by around 0.02% (TSP-50) and 0.04% (TSP-100). We observed that they used 'GEO' (Geographical distance) instead of 'EUC' (Fuclidean distance) as the type of edge weights while running the Concorde to determine the optimal solutions. This results in the optimal solutions (optimal in the 'GEO' setting) no longer being optimal in the "EUC" settings, while the objectives derived by neural solvers are based on Euclidean distances. This discrepancy might be the reason for the reported negative optimality gaps on TSP, which seems anomalous as Concorde is guaranteed to produce optimal solutions.
GCN+BS [14]#: classic 1.2P solver that predicts heatmaps for TSP based on GCN. We run its star version that considers both beam search (1,280 beams) and shortest tour heuristics.

---

Att-CNN+MCTS [6]0: an efficient L2P solver that generalizes heatmap- based L2P solvers to larger-scale TSP instances through divide-and and-cuquurr However, we encountered issues running their GPU-version code, and the CPU-version code appeared to be time-consuming, taking around 28h (10s/instance) for 10k TSP100. We thus opt to use their reported results directly.
GNN+GLS [40]: an insightful L2P solver that uses GNN to predict regrets, thereby directing the traditional local search (relocate and 2-opt) heuristics for TSP. Regrettably, the code is not optimized for batch inference and we encountered some issues loading our datasets when following their instructions. As such, opt use their reported results directly.
CVAE-Opt-DE [43]: generic L2P solver that learns to predict a latent search space for TSP and CVRP. We use their reported DE version results due to the long runtime to reproduce results.
DPDP [42]: ttate-of-the-ar 1.2P solver that combines heatmaps with dynamic programming efficiently solve TSP and CVRP. We run it for 100k iterations (TSP) and 1,000k iterations (CVRP).
DIMES [7] novel L2P solver that learns to predict a latent search space and exploits differen- tiable optimizers to find TSP solutions. Due to incompatible issues when installing the required Pytorch extension library packages, opt to directly use their reported results obtained by the settings of using REINFORCE, active search, Monte Carlo tree search, and meta-learning.
DIFUSCO [15]#: a state-of-the-art L2P solver, that learns a diffusion model to predict heatmaps for TSP. We run their used setting: T=50 diffusion steps. S=16 samplings, and 2-opt post- post-processing.
AM+LCP [33]: a two-stage L2C solver that iteratively constructs (sceder) and re-constructs (reviser) parts of the solutions based on the AM [3]. For TSP, run their optimized version with 1,280 samplings and two revisers- one revises a length 10 nodes for 25 iterations, and the other revises a length of 20 nodes for 20 iterations. However, their code for CVRP is not publicly available. Hence for CVRP, we opt to directly use their reported results.
Pointformer [32]: latest L2C solver that enhances POMO with a multi-pointe Transformer and feature augmentation for TSP instances. We run it with 200 samplings and x8 augmentations.
Sym-NCO [13]: an effective L2C solver that enhances POMO with auxiliary losses for TSP and CVRP, aiming at better symmetry handling. We run it with 200 samplings and x8 augmentations.
POMO [4]: renowned L2C solver that enhances the AM [3] with diverse rollouts and data augmentations for TSP and CVRP. We run it with 200 samplings and x8 augmentations.
POMO+EAS [5]: leading 1.2C solver that adjusts small subset of the pre-trained POMO model parameters on test instances for efficient active search. We run the EAS-lay version with x8 augmentations for T=200 iterations (both TSP and CVRP) which is the best setting for CVRP.
POMO-EAS+SGBS [34]: a state-of-the-arr L.2C solver that bolsters EAS by incorporating simulation-guin -uuided beam search, executing beam search and efficient active search phases alternately. We run 5 rounds (TSP) and rounds (CVRP) for the short version, and 20 rounds (TSP) and 200 rounds (CVRP) for the long version. The beam search width is set as per their suggested values.
Costa et al. [16]: a compelling L2S solver that employs RNN-based policy control the 2-opt for solving TSP. We run it for T=2k iterations.
Sui et al. [17]: recent L2S solver improves upon [16] by performing 3-opt, where the policy first removes three edges and then chooses re-connection type from all candidate options. Given that their code is not available, we opt directly use their reported results.
Wu et al. [39]: a classic I.2S solver that employs Transformer-hase hased policy to control the 2-opt for solving TSP. We run it for T=5k iterations (both TSP and CVRP).
DACT [9]: a state-of-the-art L2S solver that enhances Wu et al. [39] via the cyclic positional encoding and dual-aspect representations. Consistent with their original best settings, we run it for 10k iterations with x4 augmentations for TSP and x6 augmentations for CVRP.
NLNS [8]: strong L2S solver that learns to control ruin-and-repair operators. Following their default settings, we run their code on 10 CPUs in parallel, executing T=5k iterations.
NCE [37]: distinctive L2S solver that is designed to execute CROSSOVER exchanges between
two CVRP solutions. As their code is not available, we opt to use their reported results directly.
E.2
Generalization on real-world datasets
We further evaluate the generalization performance of our NeuOpt models, which were trained on TSP100 and CVRP100, by testing them on real-worle TSPLIB and CVRPLIB instances containing up to 200 nodes (customers). These real-world instances differ significantly from training ones
7

---

Table 10: Generalization results of our NeuOpt (10 runs) on TSPLIB real-world dataset.
AMDKD (POMO)
DACT (sal.
10k)
Ours (sal.
10k)
DACT (sol. = 40k)
Ours (sol.
25k)
Instances
AM-mix
POMO-mix
Avg.
Best
Avg.
Best
Avg.
Best
Avg.
Best
KroA100
4.02%
0.02%
0.02%
1.13%
0.41%
0.00%
0.00%
0.21%
0.00%
0.00%
0.00%
KroB100
4.73%
0.25%
0.41%
0.67%
0.26%
0.05%
0.00%
0.38%
0.26%
0.00%
0.00%
KroC100
7.60%
0.01%
0.02%
2.56%
0.39%
0.00%
0.00%
0.77%
0.00%
0.00%
0.00%
KroD100
8.45%
0.27%
0.09%
2.23%
0.45%
0.05%
0.00%
0.64%
0.45%
0.02%
0.00%
KroE100
3.61%
0.50%
0.53%
1.14%
0.46%
0.02%
0.00%
0.60%
0.28%
0.02%
0.00%
cil101
5.45%
1.90%
2.55%
2.23%
1.59%
0.02%
0.00%
1.75%
1.27%
0.00%
0.00%
105
17.29%
0.36%
0.36%
6.37%
2.69%
0.00%
0.00%
0.89%
0.00%
0.00%
0.00%
pr107
71.89%
0.78%
1.62%
4.33%
2.87%
1.33%
0.81%
4.07%
2.87%
0.70%
0.54%
pr124
5.16%
0.00%
0.43%
0.75%
0.65%
0.12%
0.00%
0.30%
0.00%
0.05%
0.00%
bicr127
133.13%
0.80%
0.65%
3.39%
2.01%
0.77%
0.51%
2.43%
1.71%
0.59%
0.32%
ch130
1.98%
0.60%
0.69%S
2.72%
0.41%
0.40%
0.29%
1.09%
0.41%
0.35%
0.29%
pr136
3,54%
1.76%
1.49%
5.65%
1.45%
1.06%
0.26%
4.58%
0.58%
0.80%
0.02%
pr144
13.82%
0.85%
0.72%
2.63%
2.07%
0.62%
0.17%
1.16%
0.44%
0.19%
0.03%
ch150
2.33%
0.70%
1.25%
1.77%
0.58%
0.36%
0.00%
1.23%
0.87%
0.26%
0.00%
KroA150
11.22%
0.75%
1.07%
4,21%
1.74%
0.30%
0.00%
5.15%
0.66%
0.11%
0.00%
KroB150
9.39%
0.78%
0.76%
3.22%
1.64%
0.95%
0.57%
2.45%
1.64%.
0.55%
0.15%
prl52
16.31%
1.35%
2.16%
3.10%
1.57%
0.79%
0.34%
2.23%
0.77%
0.26%
0.00%
rat195
39.35%
4.25%
4.68%
3.92%
2.02%
2.40%
1.42%
3.28%
2.02%
2.02%
1.25%
KroA200
16.77%
1.61%
1.83%
5.43%
3 3.05%%
2.18%
1.67%
3.01%
2.33%
1.59%
1. 1.39%
KroB200
15.75%
0.77%
2.36%
8.27%
5,46%
5.52%
3.88%
6.39%
5.23%
4.07%
2.93%
Avg. Gup
19,59%
0.92%
1.18%
3.29%
1.59%
0.85%
0.50%
2.13%
1.09%
0.58%
0.35%
with much larger sizes and different node (customer, depot) distributions. We compare our NeuOpt with the state-of-the-art 1.2S solver, DACT [9], reporting both the best and average gaps across 10 independent runs. We also compare with the results from a recent work [11] that focused on enhancing the generalization capabilities of existing I.2C solvers, where we include AM-mix, POMO- mix, and AMDKD (POMO) as baselines. According to Bi et al. [11], AM-mix and POMO-mix are enhanced AM and POMO models, respectively, which were trained on a combination of uniform, cluster, and mix of uniform and cluster instances to bolster their generalization performance. The AMDKD approach leverages adaptive cullt--distiibution knowledge distillation to glean various forms of knowledge from multiple teachers trained exemplar distributions, as to yield a lightweight yet highly adaptable student POMO model. Since our primary focus is on the generalization capability of the deep model itself, we do not consider post-hoc per-instance processing boosters (e.g., EAS (5)). The results for TSPLIB and CVRPLIB are presented in Table 10 and Table 11, respectively.
TSPLIB results. As depicted in Table 10, our NeuOpt model consistently yields lower average gaps than the state-of-the-art DACT solver when both are allowed to explore 10k solutions. Meanwhile, our NeuOpt exploring 25k solutions could even surpass the DACT exploring 40k solutions. When compared to L2C solvers, NeuOpt yields lower gaps than AM-mix and POMO-mix, and even the AMDKD (POMO) model that is explicitly designed to enhance tross-distribution generalization performance. These results indicate the desired generalization capabilities of our NeuOpt model.
CVRPLIB results. As depicted in Table 11, our NeuOpt could still deliver the lowest average gaps on CVRPLIB instances compared to other baselines. Despite the promising results, we acknowledge that there is still room for improvement in enhancing the generalization of L.2S solvers (including our NeuOpt), which akin to the efforts made by AMDKD advancing L2CC solvers. Meanwhile, as dis- cussed in Section 7, the integration of post-hoc per-instance processing boosters (c.g.. EAS [5]) could potentially further improve both the in-distribution and cross-distribution generalization performance of existing L2S solvers. We consider the above ideas as important directions for future research.
E.3 Results on TSP-200 and CVRP-200
We carry out experiments on larger scales, i.c., training our NeuOpt on TSP200 and CVRP200. For the size-specific syper-parammters, we use & = 0.25 for both problems; and use the CVRP problem settings: capacity A= 70 and 30 dummy depots. All other
remain unchanged. The performance of our NeuOpt models for TSP-200 and CVRP-200 are depicted in Table 12, where we compare our models with traditional heuristics (as per Table 1). The results indicate that our models consistently find close-to-optimal solutions, even outperforming the LKH3 solver on CVRP-200. We note that due to prohibited longer training times, existing 1.2S solvers (like DACT [9]) may not be efficient for training on size 200, which underscores the better scalability of our approach.
8

---

Table 11: Generalization results of our NeuOpt-GIRE (10 runs) on CVRPLIB real-world dataset.
AMDKD (POMO)
DACT (snl.
10k)
Ours (sol.
l0k)
DACT (sal.
rilk) Best
Ours (sal.
600)
Instances
AM-mix
POMO-mix
Avg.
Besl
Avg.
best
Avg.
Avg.
best
X-n101-k25
9,92%
10.58%
6.19%
3.11%
1.68%
3.40%
1.77%
1.32%
1.84%
0.51%
X-n106-k14
6.06%
2.71%
1.84%
2.77%
2.28%
1.66%
1.01%
2.09%
1.72%
1.41%
1.01%
X-n110-k13
4.66%
1.36%
2.26%
0.98%
0.00%%
1.11%
0.27%
X-n115-k10
14,83%
6.76%
5.27%
1.43%
0.08%
1.18%
0.03%
0.68%
0.02%
0.61%
0.00%
X-n120-66
20.71%
4.99%
3.49%
2.34%
0.89%
0.95%
X-n125-k30
24.00%
12.32%
5.46%
6.01%
4.76%
4.71%
3.15%
5.51%
4.76%
3.55%
2.58%
X-n129-k18
6,54%
2.27%
1.76%
5.28%
3.98%
2.84%
1.64%
3.91%
3.48%
2.03%
1.26%
X-n134-k13
16.43%
3.74%
3.79%
6.40%
3.77%
3.48%
2.42%
3.28%
2.32%
2.50%
1.73%
X-n139-k10
10.03%
3,41%
2.69%
3.05%
1.65%
3.85%
2.39%
1.13%
0.53%
2.28%
0.99%
X-n143-27
16.84%
5.01%
4.12%
5.15%
3.92%
2.05%
1.29%
3.37%
0.89%
1.27%
0.78%
X-n148-k46
42.24%
22.48%
8.16%
4.75%
3.61%
6.30%
4.70%
4.24%
2.60%
4.66%
2.96%
X-n153.422
16.50%
11.35%
11.17%
7.62%
4.63%
9.16%
6.89%.
4.26%
3.22%
6.71%
6.00%
X-n157-k13
17.86%
6.36%
3,40%
3.36%
2.70%
3.50%
2.71%
2.60%
2.09%
2.67%
2.33%
X-n162-k11
4.41%
5.75%
5.41%
2.68%
1.82%
3.02%
1.92%.
1.57%
1.10%
2.43%
1.82%
X-n167-k10
5,49%
4.94%
4.11%
5.75%
4.36%
5.55%
3.64%
4.83%
4.05%
4.34%
3.04%
X-n172-551
36.86%
9.29%
9.06%
5.42%
3.66%
8.85%
5.92%.
3.78%
3.37%
6.48%
5.43%
X-2
11.40%
13,25%
11.25%%
10.91%
7.74%
11.20%
8.00S%
9.13%
7.74%
7.81
5.86/%
X-n181-k23
6.83%
13.47%
4.64%
3.65%
3.05%
2.82%
2.19%
2.51%
1.89%
2.33%
2.07%
K11
7.04%
6.97%
9.06%
8.01%:
6.80%%
5.54%
3,45%
6.10%
5.01%
4.71%%
4.01%:
X-n190-88
23.79%
11.38%
3.50%
7.86%
6.36%
8.06%
6.18%
6.42%
5.81%
6.65%
5.76%
k51
30.76%
10,59%
15.96%
7.74%
6.60%%
9.11%
7.53%
6.25%
5.14%
7.35%
6.12%.
Avg. Gup
15.87%
8.05%
5.77%
5.21%
3.68%
4.80%
3.27%
|| 3.74%
2.85%
3.51%
2.62%
Table 12: Results of our NeuOpt approach on solving TSP-200 and CVRP-200 instances.
Model Type
TSP-200
CVRP-200
Methods
Obj.
Gap
Time
Obj.
Gap
Time
Concorde [54]
Exact
10.687
23m
HGS [21]
Heuristies
21.756
19.8h
LKH [20, 51]
Heuristics
10.687
0.00%
2,3h
22,010
1.17%
21.6h
Ours (DA-5, T=1k)
L2S/RL
10.732
0.42%
28m
22.214
2.11%
58m
Ours (DA=5, T=5k)
L2S/RL.
10.696
0.09%
2.4h
21.960
0.94%
4.8h
Ours (DA=5, T=10k)
L2S/RI.
10.692
0.04%
4.7h
21.904
0.68%
9.6h
Ours (DA=5. T=20k)
L25/RL
10.689
0.02%
9.4h
21.861
0.48%
19.2h
Ours (DA=5. T=30k)
L2S/RL.
10.688
0.01%
14.1h
21.842
0.39%
1.2d
Ours (DA=5, T=40k)
L2S/RL
10.688
0.01%
18.8h
21.830
0.34%
1.6d
E.4 Inference with multiple GPUs
Our implementation allows for accelerated inference using multiple GPUs. Recall that in Table 1, the recorded time is for solving a total of 10,000 instances on a single GPU. For practical applications, users can achieve significantly shorter runtimes using multiple GPUs, as illustrated in Table 13.
Table 13: Inference time of our NeuOpt for solving 10k instances using different numbers of GPUs.
TSP-100
CVRP-100
Methods
IGPU (11GB)
2GPU (22GB)
AGPU
IGPU (11GB)
2GPL (22GB)
4GPU (44GB)
NeuOpt (DA=1,T=Ik)
17m 1.4h
5m
14m
NeuOpt (DA=1,T=5k)
42m
23m
2.3h
1.2h
36m
NcuOpt (DA=1,T=10k)
2.8h
45m
4.6h
2.3h
1.2h
E.5 Visualization of exploration behaviour
Figure 12 presents the objective values (search trajectories) of the visited feasible or infeasible solutions within the first 50 search steps, when using a pre-trained NeuOpt-GIRE model solve five randomly generated CVRP-20 instances, respectively. The blue line depicts the objective values of each visited solution where we use green dots to mark feasible solutions and use red crosses to mark infeasible ones. The red and green dotted lines represent the best-so-far infeasible and feasible objective values, respectively. As observed from the figure, our learned model exhibits a propensity to explore infeasible regions at the beginning of the search, as to rapidly decrease the objective values. It then learns to correct the constraint violations on the found best-so-far infeasible solutions and begins exploring the feasible regions, leading to new best-so-fa far feasible solutions more

---

efficiently. Moreover, there is trend of alternating searches between feasible and infeasible regions. This behaviour aligns with our motivation Section 5, suggesting that exploring infeasible regions could foster shortcut discovery, promising boundary searches, and identification of possibly isolated feasible regions. This showcases the significance and effectiveness our GIRE method.
13
18.0
7.5
5.0
10 20
50
20
40
50
20
30
20
19
20
50
Figure 12: Search trajectories (50 steps) on 5 random CVRP-20 instances. The blue line shows the objective values of each visited solution (green dot feasible one; red cross infeasible one). The red and green dotted lines represent the best-so-far infeasible and feasible objective values, respectively.
In Figure 13, we further visualize the estimated distribution of the number of infeasible solutions within the last 5 visited solutions before finding that the probability of encountering at least one infeasible solution before finding a better best-so-far solution around 80%, showcasing the importance of exploring both feasible and infeasible regions by GIRE (compared to purely visiting feasible solutions in the masking scheme).
best-so-far feasible solution. Results suggest
FUMtlcasi S:5)
Piftfeesl. 3/5)
PVMileast 1:5)
PyAtioul 495)
P(Aifrast.
PVWiferd
T (0.0K,0.21)
T In (0.2k,0.4k)
0.07
0.12
0.19
0.21
0.22
0.19
(0.4k,0.61a)
1.05
0.20
0.24
0.21
0.20
T in (0.6k.0.814)
1.05
0.16
0.16
0.18
0.23
0.21
Lo0)
0.06
0.10
0.17
0.25
0.21
0.19
Figure 13: Estimated distribution of the number of infeasible solutions explored in 5 visited solutions before finding a new best-so-far feasible solution (as step size increases).
E.6
Used assets and licenses
We list the used assets in Table 14. All of them are spen-source for academic research use. Our code and pre-trained models have been made available on GitHub (https: (https://gitae) //github www.ccoc/cc//eeeeeee /iii//nnnn003///// NeuOpt) using the MIT License.
Table 14: List of used assets (pre-trained models, codes, and datasets).
Type
License
Asset
HGS [21], GCN+BS [14], DPDP [42], AM+LCP" [33], Pointerformer [32], Sym-NCO [13), POMO POMÓ-EAS [5],
MIT license
POMO=FAS+SGBB [34], DACT [9], DIFUSCO [15]
Code
BSD-3-Clause license
Concorde [54]
GPL-3300 license
NENS [8]
Available academic use
LKH-2 [51],
[20]
No license
Costa et al. [16], Wu [39]
TSPLIB (http://comopt.in www..iiiiiiiiieebrrgg..... dcSsottwarc/SSLLIB95))
Datasct
Available for academic use
CVRPLIB (http:://vppgaale))) wapp-gglgg.iii.i www.rri.briindex.ppoo.
10


Reviews:
[{"review_id": "hcGEOlYQbn", "reviewer": "Reviewer_NeSp", "summary": "The paper introduces Neural k-Opt (NeuOpt), a deep learning-based vehicle routing solver, designed to handle k-opt exchanges for any k≥2. Unlike existing Learning-to-Search (L2S) solvers, NeuOpt employs a tailored action factorization method, which allows complex k-opt exchanges to be broken down into simpler basis moves. This approach grants the model the flexibility to determine an appropriate k for each search step, enabling a balance between coarse-grained (larger k) and fine-grained (smaller k) searches.\n\nMoreover, the paper introduces Guided Infeasible Region Exploration (GIRE) scheme that promotes exploration of both feasible and infeasible regions in the search space. GIRE enriches the policy network with additional features to indicate constraint violations and exploration behavior statistics, aiding in escaping local optima, discovering shortcuts to better solutions, and enhancing the model's understanding of the problem landscapes.\n\nNeuOpt is trained using reinforcement learning (RL) and incorporates a dynamic data augmentation method during inference for improved efficiency. Extensive experiments on classic vehicle routing problem variants (TSP and CVRP) demonstrate the superiority of NeuOpt and GIRE over some existing approaches, including traditional hand-crafted solvers.", "questions": "- Figure 1 is very hard to process...\n\n- lines 122-123: I believe the definition of TSP is slightly inaccurate. The main objective of the TSP is to find the optimal Hamiltonian cycle that **minimizes** the total distance or cost required to visit all the nodes exactly once and return to the starting node.\n\n- Can authors provide more discussions on why choosing k dynamically should escape local minimas?\n\n", "limitations": "see Weaknesses", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "- Novel Approach: The paper introduces a novel approach called Neural k-Opt (NeuOpt) to handle k-opt exchanges for vehicle routing problems. This approach offers flexibility by allowing k to be any value ≥2, which can potentially lead to better solutions and more efficient search processes.\n\n- Guided Infeasible Region Exploration (GIRE): The introduction of GIRE is a significant contribution that promotes exploration of both feasible and infeasible regions in the search space. This unique scheme bridges feasible regions, helps escape local optima, and forces explicit awareness of the VRP constraints, potentially leading to improved performance in constrained VRPs.\n\n- Comprehensive Evaluation: The paper claims to have extensive experiments on classic VRP variants (TSP and CVRP) to validate the proposed NeuOpt and GIRE. A thorough evaluation of the model's performance on various VRP instances can demonstrate its effectiveness and potential advantages over existing methods.", "weaknesses": "- Scalability: While the paper claims that NeuOpt outperforms other methods, including hand-crafted solvers, there is no mention of its scalability to larger and more complex instances of vehicle routing problems. The effectiveness of NeuOpt on larger and real-world datasets should be explored.\n\n- Complexity of Action Factorization: Although the tailored action factorization method is introduced to handle k-opt exchanges flexibly, it may introduce increased complexity in the model's architecture and training process. The paper should discuss potential trade-offs and computational costs associated with the proposed factorization.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for the positive and valuable comments. We are delighted that the reviewer acknowledged that our contributions (NeuOpt and GIRE) are novel and significant, and our experiments are comprehensive and extensive. We hope that the following response will clear the remaining concerns.\n***\n**[Effectiveness of NeuOpt on larger and real-world instances]** Thanks for raising the concern. We would like to clarify that our NeuOpt (for TSP) and NeuOpt-GIRE (for CVRP) were evaluated on these more complex instances as detailed in the original Appendix. Please refer to the above global response for a summary of these results.\n***\n**[Are our action factorization complex?]** We understand the concern about complexity. As pointed out by the reviewer, our Action Factorization is designed to allow the deep model (our NeuOpt) to control k-opt exchanges flexibly (with any $k \\ge 2$). We would like to clarify that our Action Factorization does not introduce much complexity into the model architecture or the training process. In fact, the designs of our NeuOpt for achieving flexible k-opt are both lightweight and desirable, for the following three reasons:\n* **Regarding the computational complexity:** Firstly, our factorization formulation is already simpler (while ensuring flexibility) compared to the original k-opt definition. Moreover, in the proposed RDS decoder, we **have further simplified** the parametrization of the above action factorization to a *node selection process* (with the type of basis moves in the action factorization being automatically inferred, see lines 198-201). This means that the decoder **only needs to specify one node in each decoding step**, resulting in a computational complexity (time) that grows approximately linearly with the increase of K. We believe that such complexity is highly desirable for decoding k-opt decisions.\n* **Regarding the model architecture:** We note that the model size (number of parameters) **remains the same for varying K** since our RDS decoder is flexible to control any k-opt with a unified model architecture. In Table 2 and our analysis in lines 329-331, we compared our NeuOpt (K=2) with DACT (2-opt) where both of them are learning to control 2-opt but with different decoders. Compared to the existing DACT decoder, our RDS decoder achieved better performance (our gap 0.24% vs its gap 0.32%) with **reduced** time (our 119s vs its 171s) but a slightly increased model size (our 0.683m vs its 0.633m).\n* **Regarding the training complexity:** We reported the training time in lines 615-617 in the original Appendix. For training on CVRP, it requires only 4 days, 5 days, and 8 days for sizes 20, 50, and 100, which are highly desirable as they are about **half the time taken by POMO and DACT** (their training time is around 2 weeks on CVRP100).\n***\n**[Discuss trade-offs and computational costs]** We agree with the reviewer that there are trade-offs between better performance and increased computational costs. We would like to clarify that we did mention such trade-offs in the original submission:\n* In Table 2 and lines 329-331, we compared our NeuOpt (K=2) with NeuOpt (K=4), and mentioned that the performance is *\"further amplified by increasing K to 4 for NeuOpt at the cost of slightly increased run time\"*.\n* In Figure 5(a) and lines 354-357, we compared our NeuOpt with K=2, K=3, K=4, K=5, K=6, and mentioned that *\"however, there is a trade-off between larger K and longer decoding time.\"*\n\nFollowing the suggestion of the reviewer, we have further **supplemented this by gathering more data to illustrate the trade-offs more clearly**. In the table below, we exhibit the performance and the inference/training time for different K. The results did suggest the aforementioned trade-offs, and we used K=4 to balance the trade-offs in this paper. We will further refine our paper to make the discussion more clear.\n| | Inference Time (T=1k) | Training Time (per epoch) | Objective Values | Gaps to the Best |\n|:-:|:-:|:-:|:-:|:-:|\n| NeuOpt (K=2) | 2m02s| 20m| 7.817| 0.30%|\n| NeuOpt (K=3) | 2m07s| 21m| 7.806| 0.15%|\n| NeuOpt (K=4) | 2m13s| 22m| 7.798| 0.05%|\n| NeuOpt (K=5) | 2m19s| 24m| 7.795| 0.01%|\n| NeuOpt (K=6) | 2m26s| 25m| 7.794| 0.00%|\n***\n**[Refine Figure 1]** Thanks for the valuable feedback. We will enhance the readability of Figure 1 and add explanations. Please refer to the global response for detailed clarification.\n***\n**[Refine TSP definition]** Thanks for the valuable feedback. We will refine it according to your suggestion and thoroughly check all the other definitions.\n***\n**[Why dynamic $k$ help escape local minima?]** Thanks for the valuable question. We will refine our paper based on the discussions from two aspects as follows: \n* **Exploration of different neighborhoods:** The value of $k$ defines the neighbourhood of the current solution. For a given solution, different neighborhoods may have different local minima. For example, from the current solution $\\tau_0$, we may obtain a local minima solution $\\tau_1$ via a 2-opt move (only changing 2 edges of $\\tau_0$), while a 5-opt move on $\\tau_0$ might lead to another local minima solution $\\tau_2$. Hence, the capability to vary $k$ dynamically can equip the solver with flexibility and reduce the likelihood of confinement to particular local minima. \n* **Adaptive search strategies:** Different search stages may require different $k$ to foster an efficient search. However, a statically defined $k$ might either be too restrictive, leading to rapid convergence to local optima, or too unbound, resulting in excessive exploration without convergence. As mentioned in introduction (lines 41-42), dynamically scheduling $k$ could achieve a *\"balance between coarse-grained (larger $k$) and fine-grained (smaller $k$) searches\"*. In our NeuOpt, $k$ is autonomously determined and dynamically scheduled during the search."}, {"review_id": "IMOSma0Ecq", "reviewer": "Reviewer_8kc7", "summary": "In this paper, the authors propose Neural k-Opt (NeuOpt) that factorizes a generic k-opt exchange operation as a series of base operations. They also introduce Guided Infeasible Region Exploration (GIRE) scheme for Capacitated Vehicle Routing Problem (CVRP) where one augments a reward function for RL with signals about exploring infeasible solution spaces. On the model architecture side, the authors propose a recurrent dual-stream decoder that consumes both moves and edges. The authors provided a comprehensive comparison with baseline methods for problems of sizes up to 100 cities.\n", "questions": "1. In section 5 about the reward shaping (near line 266), how to compute $P_t(\\mathcal{U}|\\mathcal{U})$ exactly? \n\n2. In the entropy computation, why $P_t(\\mathcal{U}|\\mathcal{F})$ and $P_t(\\mathcal{F}|\\mathcal{U})$ are not included? It is possible to transition between feasible and infeasible solution spaces. \n\n3. The actual entropy calculation involves hyperparameters $c_1$ and $c_2$. Can the authors provide more context on how they were chosen and their impact on the stability of training?\n\n4. In Table 1, for different variants of NeuOpt, what does the DA number refer to? Is that the $T_{DA}$ mentioned in section 4.3?\n\n5. In Figure 5(a), the results for K = 5 and 6 w/o E-move are missing.\n", "limitations": "The authors could add discussions about the generalization ability of trained models as well as scaling to larger problem sizes.\n", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. I found the action factorization novel and general. A limitation of past k-Opt based learning-to-search methods is that they require a pre-determined value of k. The proposed factorization method can accommodate arbitrary k given an agent enough number of steps. \n\n2. GIRE seems a promising approach to incorporating information about near-feasible regions into explorations. As far as I know, this contribution is novel.\n\n3. The empirical comparisons with baseline methods are comprehensive. I appreciate the authors including an up-to-date list of baseline methods. There are some expected issues with reproductions but I definitely applaud the authors’ efforts here.\n\n4. The paper is relatively well-written. The authors did a good job of packing a dense set of information within the page limit.", "weaknesses": "1. The problem sizes considered are relatively small. Methods like DIFUSCO experimented with sizes up to 10000 cities. It is unclear how practically useful this method is with small problem sizes.\n\n2. Another common evaluation mode for these classes of problems is for the generalization ability of a trained model. That is, extrapolate the model performance on problems of larger sizes than those in the training set. This is not considered in this paper.\n\n3. In general, the empirical results are mixed. On TSP, NeuOpt is not better than DPDP and Att-GCN+MCTS. The comparison with DIFUSCO is obfuscated by a large time discrepancy from the original paper, possibly due to difficulty in reproducing their results. On CVRP, POMO+EAS+SGBS methods are comparable with NeuOpt.\n\n4. The main advantage of the factorized action representation is that one could potentially handle arbitrary k-Opt in a general way. However, in the experiments, the authors used a value of 4 for k which seemed limiting. In addition, in the ablation on values of k, larger k values worked better, so why did the authors not choose a larger value of k for the main evaluations?\n\n5. There are some places where the exposition could be improved. Please see my questions below.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for the positive and valuable comments. We are delighted that the reviewer found our approach novel, general, and promising. Thank you for recognizing our efforts to include extensive baselines. We hope that the following response, along with additional experimental results, will address the remaining concerns.\n***\n**[How practically useful our NeuOpt is?]** Thanks for the comment. \n* Regarding - *\"sizes considered are relatively small\"* - we would like to clarify that we did improve the scalability of the learning-to-search (L2S) solvers by direct training on size 200 (see global response). For even larger instances, we recommend integrating our NeuOpt with the SOTA **divide-and-conquer** frameworks. In such frameworks (e.g., L2D [2] and RBG [3], references in global response), a divider is usually learned to segment large-scale instances (e.g., TSP with 10,000 nodes) into sub-problems (e.g., fifty TSP-200 instances), where the sub-problems are solved by LKH3 or POMO (in parallel). **Given the new SOTA performance on sizes 100 and 200, our NeuOpt could serve as a more desirable conquer solver in these frameworks**.\n* Regarding - *\"methods like DIFUSCO experimented with sizes up to 10000 cities\"* - we acknowledge that L2P solvers excel at scalability, however, **methods like DIFUSCO are limited to supervised learning and TSP only** since their predicted heatmaps may not handle other constraints. Conversely, our NeuOpt and GIRE could be more adaptable for constrained VRPs via DRL. Moreover, we have shown in Table 1 that our NeuOpt (0.00%, 7h) exhibited much better performance than DIFUSCO (0.02%, 21.7h) on TSP100.\n* Regarding - *\"how practically useful this method is?\"* - the unique **research and practical values** of our approach are listed as follows:\n    * SOTA performance compared to up-to-date baselines\n    * the first L2S solver for flexible k-opt search\n    * the first constraint-handling scheme beyond masking\n    * better conquer solver for divide-and-conquer frameworks\n    * more generic and adaptable solvers (for constrained VRPs)\n***\n**[Generalization evaluation]** Yes, we have included such evaluations in the original Appendix. Kindly refer to the global response for more details.\n***\n**[Time discrepancy with DIFUSCO]** Thanks for the question. Their reported time is for 128 instances while ours is for 10,000 instances. Meanwhile, their hardware (V100 GPU, CPU 2.50GHz) is different from ours (2080TI GPU, CPU 2.40GHz).\n***\n**[Results are mixed]** We agree with the reviewer that different solvers have unique pros and cons, and we note that our NeuOpt does achieve SOTA performance on the whole. Specifically, \n* The good performance of **DPDP and Att-GCN+MCTS is limited to TSP, and our NeuOpt are more adaptable to constraints**. Our NeuOpt (0.30%, 13.8h) significantly outperforms DPDP (0.41%, 1.2d) on CVRP100 and Att-GCN+MCTS even fails to solve CVRP.\n* While achieving comparable gaps, **our NeuOpt-GIRE is around 7h faster than POMO+EAS+SGBS on CVRP100 and also significantly outperforms it on TSP100**. We note that POMO+EAS+SGBS has evolved through 4 stacked schemes, including model design by AM (ICLR’18), training algorithms by POMO (NeurIPS’20), active search by EAS (NeurIPS’21), and beam search by SGBS (ICLR’22). Thus, it is already promising that our NeuOpt, utilizing unified model parameters for all test instances without per-instance active search (model parameter update) or beam search boosters, outperforms POMO+EAS+SGBS. We believe the superiority of our NeuOpt could be further enhanced with similar per-instance boosters in the future.\n* Lastly, as one of the L2S solvers, **our NeuOpt is able to halve (on TSP) or even reduce by an order of magnitude (on CVRP) the gaps achieved by other L2S solvers with a much shorter run time**.\n***\n**[Why use K=4?]** Thanks for the question. We use K=4 to balance computational costs and better performance, aligning with traditional solvers like LKH that avoid $k\\geq5$ due to unbounded exploration. Yes, our factorization benefits from handling k-opt in a general way. Besides, it lets the model autonomously schedule dynamic k during the search. Kindly refer to our response **[Discuss trade-offs and computational costs]** and **[Why dynamic $k$ help escape local minima?]** to reviewer #NeSp for more discussions.\n***\n**[Compute $P(\\mathcal{U}|\\mathcal{U})$]** We adopt $P(\\tau'\\in\\mathcal{U}|\\tau\\in\\mathcal{U})=\\frac{P(\\tau'\\in\\mathcal{U},\\tau\\in\\mathcal{U})}{P(\\tau\\in\\mathcal{U})}$, where $P(\\tau'\\in\\mathcal{U},\\tau\\in\\mathcal{U})$ and $P(\\tau\\in\\mathcal{U})$ are estimated based on the historical solution records of the past $T_{EI}$ steps.\n***\n**[Why not include $P(\\mathcal{U}|\\mathcal{F})$ and $P(\\mathcal{F}|\\mathcal{U})$?]** We opt not to explicitly include them since the MLP is able to derive $P(\\mathcal{U}|\\mathcal{F}) = 1 - P(\\mathcal{F}|\\mathcal{F})$ and $P(\\mathcal{F}|\\mathcal{U}) = 1 - P(\\mathcal{U}|\\mathcal{U})$.\n***\n**[Effects of c1 & c2]** Thanks for the suggestion. They control the entropy measure patterns (shown in Figure 3). We set the values to only penalize extreme search behavior if the feasibility transition probability is outside [0.25, 0.75]. We follow the suggestion and add Figure A1 and Figure A2 in the attached PDF under global response. Results show that they may not affect training stability (thus no need for tuning in practical use).\n***\n**[DA and T_DA]** We apologize for the confusion. DA refers to the number of augmentations for an instance, and T_DA is the maximum number of steps allowed before considering the search trapped in a local optimum. If T_DA is reached, the augmentation is changed to a new one. We will include algorithm pseudocode for dynamic data augmentation in the revised Appendix.\n***\n**[Full results of w/o E-move]** Thanks for the comment. We have added the requested results to Figure A3 in the attached PDF under global response. The conclusion remains unchanged."}, {"review_id": "Gdh8XAVuIa", "reviewer": "Reviewer_vydT", "summary": "The paper aims to learn the k-opt operation, one of the famous local search methods, via neural networks. In particular, the authors model the k-opt operation as a sequential node selection process and use a recurrent dual-stream (RDS) decoder. Furthermore, a guided infeasible region exploration (GIRE) is suggested to encourage the policy to escape local optima.\nThe paper models the k-opt as a sequence of basic moves on open Hamiltonian paths (not cycles), which allows the neural network model easily learns the k-opt operation. Since the end of the sequence (i.e., E-move) is a kind of I-moves, k can be flexibly adjusted according to states. GIRE allows the model to explore infeasible regions, not only feasible regions; it encourages the model to escape local optima. In addition, the portion of infeasible solutions is dynamically adjusted.", "questions": "I have some questions about the details.\n\n1. Effectiveness of learning the S-move. I think that choosing the S-move also gives good performances.\n2. Why is LKH3 (known as better than LKH2) not employed as a baseline?\n3. Whether the encoding is necessary for every t?\n4. How is the problem augmented in detail? I’ve read through the appendix but couldn’t find it.\n\nMinor Comments:\n1. I think further explanation for ES features is required (maybe in the appendix)\n2. For better readability, additional cross-references for contents in the appendix are recommended.\n3. There is no explanation when the other papers are referenced (e.g., line 192, 257). I recommend adding further descriptions.", "limitations": "I think the dual-stream structure is restricted to consider additional context information.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is well-written in general, and the key ideas are clearly delivered. The extensive experiments with various baselines suggest that the proposed method can mitigate the inefficiency of L2S solvers.\n\nOne of the main benefits is that we can choose the proper K, the number of DA, and T according to the available computation budget. Also, the results show that NeuOpt gives promising performances with similar time with L2C algorithms.", "weaknesses": "There is no analysis of where the performances come from. the k-opt operations are well-working with fixed k. Comparisons between the original k-opt and NeuOpt are required.\n\nSome detailed but important information is missing or hard to be found (e.g., encoding scheme, dynamic augmentation, initial tour)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer for the positive and valuable comments. Thank you for acknowledging that NeuOpt improves the efficiency of L2S solvers, exhibits unique benefits for practical use, and achieves promising performance. We hope that the following response, along with additional experimental results, will address the remaining concerns.\n***\n**[Similar time with L2C solvers]** Thanks for the comment. However, we would like to clarify that **our NeuOpt is consistently faster than all compared L2C solvers** while achieving better or similar performance. Specifically,\n* On TSP100, our NeuOpt (0.02%, 2.8h) surpasses all L2C solvers **in both gap and speed**, including AM+LCP (0.60%, 10.9h), Pointerformer (0.11%, 5.6h), Sym-NCO (0.08%, 5.6h), POMO (0.07%, 5.6h), POMO+EAS (0.05%, 10.9h), and POMO+EAS+SGBS (0.03%, 1.1d).\n* On CVRP100, NeuOpt (0.59%, 4.6h) outperforms L2C solvers like Sym-NCO (0.89%, 7.2h) and POMO (0.70%, 7.2h) **in both gap and speed**. Compared to POMO+EAS, to achieve a gap of 0.30%, NeuOpt is around **2 hours faster**. Compared to POMO+EAS+SGBS, to achieve a gap of 0.10%, NeuOpt is around **7 hours faster**.\n***\n**[Where does the performance come from?]** Thanks for the question. Following your suggestion, we will make the analysis more clear. We attribute the performance of our approach to our 4 contributions, thoroughly verified through extensive experiments and ablation studies in the original paper:\n* **New action factorization:** It enables autonomous scheduling of dynamic $k$ during search (see lines 40-42), delivering advantages over fixed $k$ (see Figure 5a, lines 349-356).\n* **The RDS decoder:** It is flexible to control k-opt with any $k$ and more effectively captures the strong correlations between the removed and added edges (see line 45). Compared to the DACT decoder, our RDS decoder achieves much better performance with reduced run time (see Table 2 and lines 329-331). Further, designs within the RDS decoder, including the GRUs and dual streams, are all essential to performance (see Table 3 and lines 333-336).\n* **The GIRE scheme:** It is the first constraint handling scheme that promotes the exploration of both feasible and infeasible regions, bringing multiple benefits (see lines 52-57). It has been verified to be generic to boost both DACT and our NeuOpt for better constraint handling (see Table 2, lines 326-328). Besides, designs within GIRE, including the reward shaping and feature supplement, are both essential to performance (see Figure 4 and lines 337-343). We also provide visualizations and discussions about GIRE (see Appendix D and Figure 8).\n* **Dynamic data augmentation:** It enables NeuOpt to explicitly escape from the local optima (see Table 4 and lines 344-348). Table 1 also shows the effects of different augmentation settings on performance.\n***\n**[Comparison with other k-opt methods]** Following the suggestion, we have added another baseline called OriginOpt and gathered the results together with those reported in the original paper in the tables below. Note that various traditional and learning-based k-opt baselines are now comprehensively included, as detailed below:\n* **Traditional k-opt baselines:**\n    * **OriginOpt (static)** and **OriginOpt (dynamic)**, which randomly perform the k-opt (rather than using our NeuOpt) in a static and dynamic manner, respectively.\n    * **LKH**, which not only performs dynamic k-opt, but also integrates other complex heuristic designs for better performance (e.g., an $\\alpha$-measure-based edge candidate set, partitioning rules, tour merging strategies, the iterative partial transcription technique, the backbone-guided search, etc).\n* **Learning-based k-opt baselines:**\n    * Neural 2-opt: **DACT**, **Wu et al.**, and **Costa et al.**\n    * Neural 3-opt: **Sui et al.**\n\nThe results demonstrate that our NeuOpt significantly outperforms all learning-based k-opt baselines, as well as the original k-opt OriginOpt baseline. Notably, our NeuOpt is able to find lower gaps at a faster speed than the strong LKH3 solver (which employs complex heuristics beyond k-opt) on CVRP100.\n\n--\nTSP100|Gap|Time\n-|-|-\nLKH2|0.00%|5.7h\nOriginOpt (static)|210.00%|17m\nOriginOpt (dynamic)|202.40%|17m\nCosta et al.| 0.77%| 1.1h\nSui et al.| 0.74%| 1.3h\nWu et al.| 1.54%| 2h\nDACT| 0.10%| 13.5h\n**NeuOpt (DA=1,T=1k)**|0.33%|17m\n**NeuOpt (DA=5,T=3k)**|0.01%|4.2h\n\n--\n\nCVRP100|Gap|Time\n-|-|-\nLKH3 |0.54%|5.7d\nOriginOpt (static)|93.23%|2.3h\nOriginOpt (dynamic)|103.84%|2.3h\nWu et al.|3.87%|5h\nDACT|1.11%|1.7d\n**NeuOpt (DA=1,T=5k)**|0.85%|2.3h\n**NeuOpt (DA=5,T=6k)**|0.30%|13.8h\n***\n**[Effects of S-move]** Thanks for the insightful comment. The reviewer is correct that learning the S-move is crucial for good performance. Kindly refer to Figure A4 in the attached PDF under the global response for new results.\n***\n**[LKH2 or LKH3]** Kindly note that **we employed LKH3 for CVRP, while LKH2 was used for TSP**. This distinction was made because LKH2 is the latest version for TSP, whereas the updates in LKH3 are only made for constrained TSP (such as CVRP).\n***\n**[Encoding for every t?]** Yes, because the current solution and features change with each $t$. This is common across all existing L2S and L2C solvers.\n***\n**[Is dual-stream structure restricted?]** No. Let $s_1, s_2$ be the logits of the current dual streams, and $s_3, s_4, …$ represent additional ones. While our paper utilizes $s_1 + s_2$, more streams can be easily accounted for by MLP($s_1, s_2, s_3, s_4, …$) if needed.\n***\n**[Explain details & other minor comments]** Thanks for the suggestions. We will refine our paper accordingly. Specifically, encoding and augmentation details follow the exact methods used in [1]. We will include algorithm pseudocode for dynamic data augmentation, and we will clarify that the initial tours are randomly generated (same with all existing L2S solvers).\n```\nReferences: \n[1] Efficient Neural Neighborhood Search for Pickup and Delivery Problems (IJCAI’22)\n```"}, {"review_id": "gcL2EtgJHI", "reviewer": "Reviewer_2dzf", "summary": "The paper introduces a learning-to-search (L2S) solver called Neural k-Opt (NeuOpt) for routing problems. NeuOpt learns to perform flexible k-opt exchanges using a tailored action factorization method and a customized recurrent dual-stream decoder. The paper also proposes the Guided Infeasible Region Exploration (GIRE) scheme, which allows the autonomous exploration of both feasible and infeasible regions. The experiments on TSP and CVRP with up to 100 nodes show that NeuOpt could outperform other learning-based methods slightly. However, the solving speed could be very slow. It also cannot outperform HGS and LKH3 from OR fields. Overall, I think the topic and proposed method are interesting, however, the results are not significant.", "questions": "The feasibility of solutions is not discussed in the experiments.  To what extent does the Guided Infeasible Region Exploration method impact the feasibility?  The reviewer encourages the authors to evaluate the method on VRPTW or TSPTW to make a more solid benchmark.", "limitations": "The limitations have been discussed in the main body. In Section 7,  the first point \"it falls short against some L2P solvers (e.g., [5, 6]) for larger-scale TSPs\" is a good discussion about the limitation. However, the second and third points are actually the advantages of the paper, rather than the limitations.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "* The paper is mostly well-written, except that Figure 1 is too complex to help the reviewer to understand the basic ideas of the proposed method. \n* The literature reviews are quite impressive, which include necessary classic and SoTA methods.\n* The proposed NeuOpt and Guided infeasible region exploration seem reasonable.\n* The proposed MDP for k-opt is interesting", "weaknesses": "* The experiments on TSP and CVRP with up to 100 nodes show that NeuOpt could outperform other learning-based methods slightly.  However, the solving speed could be very slow. It also cannot outperform HGS and LKH3 from OR fields. Overall, I think the results are not significant.\n* Given the complexity of the method and the code is not provided, reproducibility could be a problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for acknowledging that our approach is reasonable, the MDP is interesting, and the paper is mostly well-written. We understand that the main concerns are the significance of the performance and the code availability. We hope our response below will clarify any misunderstandings and concerns about our work.\n***\n**[Significance of the Performance]** Regarding - *\"NeuOpt could outperform other learning-based methods slightly. However, the solving speed could be very slow. It also cannot outperform HGS and LKH3 from OR fields\"* - **these appear to be misunderstandings**, and we would like to clarify the following:\n* **Compared to learning-to-search (L2S) solvers: NeuOpt significantly surpasses them in both performance and speed** (NeuOpt also belongs to L2S solvers)\n    * On TSP100, our NeuOpt (0.33%, 17m) **halves the gaps** of Costa et al. (0.77%, 1.1h), Sui et al. (0.74%, 1.3h), and Wu et al. (1.54%, 2h) **with faster speed**. And NeuOpt (0.00%, 7h) **significantly surpasses** the SOTA solver DACT (0.10%, 13.5h).\n    * On CVRP100, our NeuOpt (0.85%, 2.3h) **reduces by an order of magnitude the gaps achieved by all L2S solvers with faster speed**, including NLNS (2.26%, 2.4h), NCE (1.59%, 10.4d), Wu et al. (3.87%, 5h), and DACT (1.11%, 1.7d).\n* **Compared to learning-to-construct (L2C) solvers: NeuOpt consistently achieves better/comparable performance with faster speed**\n    * On TSP100, our NeuOpt (0.02%, 2.8h) surpasses all L2C solvers **in both gap and speed**, including AM+LCP (0.60%, 10.9h), Pointerformer (0.11%, 5.6h), Sym-NCO (0.08%, 5.6h), POMO (0.07%, 5.6h), POMO+EAS (0.05%, 10.9h), and POMO+EAS+SGBS (0.03%, 1.1d).\n    * On CVRP100, NeuOpt (0.59%, 4.6h) surpasses L2C solvers like Sym-NCO (0.89%, 7.2h) and POMO (0.70%, 7.2h) **in both gap and speed**. Compared to POMO+EAS, to achieve gap 0.30%, NeuOpt is around **2 hours faster**. Compared to POMO+EAS+SGBS, to achieve gap 0.10%, NeuOpt is around **7 hours faster**.\n    * We note that POMO+EAS+SGBS has evolved through 4 stacked schemes, including model design by AM (ICLR’18), training algorithms by POMO (NeurIPS’20), active search by EAS (NeurIPS’21), and beam search by SGBS (ICLR’22). Thus, **it is already promising that our NeuOpt, utilizing unified model parameters for all test instances without per-instance active search (model parameter update) or beam search boosters, outperforms POMO+EAS+SGBS**. The superiority of our NeuOpt could be further enhanced with similar per-instance boosters in the future.\n* **Compared to learning-to-predict (L2P) solvers: NeuOpt shows greater adaptability to constrained VRPs and still exhibits better performance on the whole**\n    * On TSP100, our NeuOpt (0.33%, 17m) surpasses GCN+BS (1.35%, 46m), CVAE-Opt-DE (0.34%, 1.8d), and GNN+GLE (0.58%, 2.8h) in **both gap and speed**. Our NeuOpt (0.00%, 7h) surpasses the SOTA solver DIFUSCO (0.02%, 21.7h) with a **significantly faster speed**.\n    * While we acknowledge that NeuOpt does not outperform DPDP and Att-GCN+MCTS on TSP100, **their performance is limited to TSP only**. On CVRP100, our NeuOpt (0.30% gap, 13.8h) significantly surpasses DPDP (0.41% gap, 1.2d) and Att-GCN+MCTS even fails to solve CVRP.\n* **Compared to solvers from OR fields: our NeuOpt exhibits lower gaps than LKH3 with faster speed on both CVRP100 and CVRP200**\n    * On CVRP100, in Table 1 (main paper), **NeuOpt (0.30%, 13.8h) outperforms LKH3 (0.54%, 5.7day)**.\n    * On CVRP200, In Table 5 (appendix), **NeuOpt (0.68%, 9.6h) outperforms LKH3 (1.17%, 21.6h)**.\n    * We acknowledge that NeuOpt may not outperform the upgraded HGS solver recently released in 2022 (neither can all the other neural solvers given that neural solvers are still in early stages). Nevertheless, we narrow such gaps for this line of neural solvers. Moreover, by integrating per-instance search boosters like EAS, our neural solver has the potential to further amplify the performance.\n\n**Lastly, beyond mere performance competition, we present novel ideas and insights as recognized by other reviewers.** We believe that our contributions, including the k-opt factorization in MDP, the first L2S solver for flexible k-opt, the fresh constraint handling scheme GIRE, and the dynamic data augmentation are worth sharing with the learning-to-optimize community.\n***\n**[Code availability]** As promised in lines 278-279, **we will make our code, pre-trained models, and the used data publicly available on GitHub. Following the rebuttal guidelines, we have forwarded our code to Area Chair**. Meanwhile, we note that our approach is not complex. For training on CVRP, it requires only 4 days, 5 days, and 8 days for sizes 20, 50, and 100, which are highly desirable as they are around half the time taken by POMO and DACT (their training time is around 2 weeks on CVRP100).\n***\n**[Refine Figure 1]** Thanks for the valuable feedback. We will enhance the readability of Figure 1 and add explanations. Please refer to the global response for detailed clarification.\n***\n**[Feasibility of the solution in the experiments]** We apologize for the confusion. The eventual solutions in all experiments are **always feasible** (because our approach only retrieves the best feasible solution visited during search as the final output), even though we allow temporal exploration of infeasible regions. Kindly refer to Appendix E.3 and Figure 9 for visualizations of the learned search trajectories (showing a trend of alternating searches between feasible and infeasible regions).\n***\n**[Make benchmark more solid]** Thanks for the suggestion. We will study the extensions of NeuOpt-GIRE to more constraints in the future. However, we believe that the current benchmark is considered solid as recognized by other reviewers.\n***\n**[Discuss limitations]** We apologize for the confusion. The last two points are future works. We will refine our paper to ensure all limitations and suggestions from reviewers are mentioned and addressed properly."}]

Author rebuttal:
We thank all the reviewers for their valuable comments. We are pleased to see that the reviewers have recognized our NeuOpt approach (including the k-opt action factorization, the RDS decoder, the fresh constraint-handling scheme GIRE, and the dynamic data augmentation) as being **novel** (#NeSp and #8kc7), **general** (#8kc7), **of significant contribution** (#NeSp), **beneficial for use** (#vydT), and **reasonable** (#2dzf). We also appreciate the positive feedback, where all reviewers found our paper mostly **well-written** and our experiments with various baselines **extensive** and **comprehensive**. In this global response, we intend to address the common concerns.
***
**[Evaluation on more complex instances]** While Reviewers #NeSp and #8kc7 raised concerns regarding the evaluation of our approach on more complex (larger or real-world) instances, we would like to clarify that our NeuOpt (for TSP) and NeuOpt-GIRE (for CVRP) were indeed evaluated on these instances **in the original Appendix**. We will add summary tables and additional discussions to the revised main paper. Below we summarize the key results.
* **Results on larger instances:**
    * Firstly, we followed existing conventions to benchmark our approach against various baselines on TSP and CVRP instances with sizes 20, 50,100 in Table 1. Beyond these results that affirm the superior performance of our approach, we have also conducted experiments on larger TSP200 and CVRP200 instances as detailed in Appendix E.2 and Appendix Table 5. The results indicate that our approach consistently finds close-to-optimal solutions and still **outperforms the traditional LKH3 solver on CVRP200**. We note that due to prohibited longer training time, existing L2S solvers like DACT [1] may not be efficient for CVRP with size 200, highlighting the better scalability of our approach.
    * For solving even larger instances, we recommend integrating our NeuOpt with the SOTA **divide-and-conquer** frameworks (e.g., [2][3]) where they require efficient solvers for handling sub-problems with small size. Given the new SOTA performance on sizes 100 and 200, our NeuOpt could serve as a **more desirable conquer solver** to complement the learning-based divide solver in such frameworks. Besides, as outlined in Section 7, future work would focus on integrating our NeuOpt with predicted heatmaps by L2P solvers to reduce search space, employing more scalable encoders or efficient CUDA implementation to further improve the scalability.
    * Lastly, we also examined the **generalization of our model to larger sizes** (generalize models trained on size 100 to larger sizes), details of which are given in the next bullet point.
* **Results on real-world instances (generalization across size and distribution):** 
    * In Appendix E.4 (Table 6 and Table 7), we have evaluated the generalization of our NeuOpt models trained on TSP and CVRP instances with size 100 and uniform distribution to real-world instances (from TSPLIB and CVRPLIB) with larger sizes (e.g., size 200) and/or different distributions (e.g., clustered node distributions, corner depot, much different demand settings, etc). For ease of reference, we have summarized the results in Table A1 and Table A2 in the attached PDF. The results consistently showcases that our NeuOpt could yield the lowest average gap. 
    * Notably, the generalization of our NeuOpt is even more promising when compared to AMDKD method [4] which explicitly boosted the cross-distribution generalization performance of POMO based on knowledge distillation. This further suggests the promising potential of our NeuOpt if NeuOpt were to be augmented with a similar generalization boosting method in future work (e.g., applying AMDKD [4] or per-instance gradient update EAS [5] to our NeuOpt). 
```
References:
[1] Learning to Iteratively Solve Routing Problems with Dual-Aspect Collaborative Transformer (NeurIPS’21)
[2] Learning to Delegate for Large-Scale Vehicle Routing (NeurIPS’21)
[3] RBG: Hierarchically Solving Large-Scale Routing Problems in Logistic Systems via Reinforcement Learning (KDD’22)
[4] Learning Generalizable Models for Vehicle Routing Problems via Knowledge Distillation (NuerIPS’22)
[5] Efficient active search for combinatorial optimization problems (ICLR’22)
```
***
**[Clarification on Figure 1]** We thank the reviewers for providing this feedback and we apologize for the confusion due to the space limitation. We will add more explanations in the revised paper and further simplify this figure. For clarification, Figure 1 depicts an example on TSP-9 to illustrate how our decoder determines a 3-opt exchange with K=4 steps. Even though K=4, the 3-opt is selected instead of the 4-opt due to the E-move being chosen at the final decoding step. The upper portion of the figure provides a visual representation of how the dual-stream attentions are computed, where the top yellow part represents the move stream $\mu$, while the bottom blue part represents the edge stream $\lambda$. The lower portion of the figure demonstrates how the inferred basis moves contribute to the modification of the current solution. At each step, $\kappa$, our RDS decoder computes the dual-stream attention (depicted by both yellow and blue dotted arrows) from representations of historical decisions $q^\kappa_\mu$, $q^\kappa_\lambda$ to node embeddings $h_i$. Each $q$ undergoes processing by the corresponding GRUs that model the historical decisions. Following the attention, one node is selected (highlighted in green), thereby deciding a basis move $\Phi_\kappa(x_\kappa)$ to modify the solution. Ghost marks are used to indicate the same location of a cyclic solution when viewed from a flat perspective as in this figure.
***
**[Additional experiments]** Following the suggestions of Reviewer #NeSp, #8kc7, and #vydT, we have added new experiments (figures and tables) in the attached PDF. Details can be found in our specific response to each reviewer.

Meta-review: Reviewers agree that the paper is well-written, with clear and thorough experiments to demonstrate the effectiveness of proposed method (NeuOpt) that learns to search in combinatorial optimization problems. Therefore I vote for acceptance.
Decision: Accept (poster)