A Learning-Augmented Dynamic Programming Approach for Orienteering Problem with Time Windows
Authors: Guansheng Peng
Lining Xing
Fuyan Ma
Aldy Gunawan
Guopeng Song
Pieter Vansteenwegen
Venue: NeurIPS 2025 poster ()
Keywords: combinatorial optimization
graph convolutional network
dynamic programming
state-space relaxation
Primary area: optimization
TL;DR: Machine learning accelerates dynamic programming in combinatorial optimization via state-space relaxation imitation

Abstract: Recent years have witnessed a surge of interest in solving combinatorial optimization problems (COPs) using machine learning techniques. Motivated by this trend, we propose a learning-augmented exact approach for tackling an NP-hard COP, the Orienteering Problem with Time Windows, which aims to maximize the total score collected by visiting a subset of vertices in a graph within their time windows. Traditional exact algorithms rely heavily on domain expertise and meticulous design, making it hard to achieve further improvements. By leveraging deep learning models to learn effective relaxations of problem restrictions from data, our approach enables significant performance gains in an exact dynamic programming algorithm. We propose a novel graph convolutional network that predicts the directed edges defining the relaxation. The network is trained in a supervised manner, using optimal solutions as high-quality labels. Experimental results demonstrate that the proposed learning-augmented algorithm outperforms the state-of-the-art exact algorithm, achieving a 38% speedup on Solomon’s benchmark and more than a sevenfold improvement on the more challenging Cordeau’s benchmark.

A Learning-Augmented Dynamic Programming Approach for Orienteering Problem with Time Windows
Guansheng Peng Lining Xing Fuyan Ma Guopeng Song S*
Aldy Gunawan Pieter Vansteenwegen" 'School of Advanced Engincering. Great Bay University, China
Shenzzenn International Center For Industrial And Applied Mathematics, Shenzhen Research Institute of Big Data, China
Reseaacc Institute of Intelligent Control and Manufacturing System, Jiangsu University of Technology, China
Defense Innovation Institute, Chinese Academy of Military Science, China
CCollgee of Systems Engineering. National University of Defense Technology. China
"School of Computing and Information Systems, Singapore Management University, Singapore KU Leuven Institute for Mobility CIB, KU Leuven, Belgium pengguanshengâgbu. edu. cn, guopeng songonudt. edw. enu.cn
Abstract
Recent years have witnessed a surge of interest in solving combinatorial optimiza- tion problems (COPs) using machine learning techniques. Motivated by this trend, we propose a learning- aomning-auggented exact approach for tackling an NP-hard COP, the Orienteering Problem with Time Windows, which aims to maximize the total score collected by visiting a subset of vertices in graph within their time windows. Tra- ditional exact algorithms rely heavily domain expertise and metieulous design, making it hard to achieve further improvements. By leveraging deep learning mod- els to learn effective relaxations of problem restrictions from data, approach enables significant performance gains in an exact dynamic programming algorithm. We propose novel graph convolutional network that predicts the directed edges defining the relaxation. The network is trained in a supervised manner, using optimal solutions as high-quality labels. Experimental results demonstrate that the proposed learning-augmented algorithm outperforms the state-of-the offtthe-rttt exact algorithm, achieving 38% speedup on Solomon's benchmark and more than a sevenfold improvement on the more challenging Cordeau's 's benchmark.
Introduction
Combinatorial optimization problems (COPs) arise in a wide range of application domains, such as logistics, felecommunications, manufacturing, and finance. Solving these problems efficiently can result in significant cost reductions. Nevertheless, their NP-hard nature presents major computational challenges. To handle these challenges, traditional approaches, including exact and heuristic methods, have been developed over the past decades.
Recently, machine learning (ML) has emerged as a complementary approach, addressing the lim- itations traditional approaches through data-driven learning 4 A variety of studies adopt an end-to-end framework that directly outputs solutions. Among these, graph neural network models has been successfully applied to COPs defined over graphs, such as the Traveling Salesperson Problem
*Coreesondence
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

(TSP), Minimum Vertex Cover, Maximum Cut, and others |9,24 15], as they naturally operate on the graph structures inherent to these problems. Additionally, sequence-to- to-seuueeeeeeeeeee learning methods, such as Pointer Networks R Graph Attention Networks [19] and Transformers [6] offer an autore- gressive approach for solving COPs. Although the above studies have achieved some success, there are still limitations. First, these learning models are rarely applied to complex and higher-dimensional COPs which usually requires hard-won explicit expertise for higher performance. In many cases, the end-to-end learning approaches underperform traditional approaches []. Second, most existing studies focus on combining ML with heuristics, while integrations with exact algorithms remain largely unexplored. The predominant trend of this direction is to formulate COPs as mixed-integer -nttger programmings (MIPs) and enhance key components of branch-and wanechh-n--bee aaa--add--ouun bound (B&B) based algorithms for MIPs using ML techniques [3]] ML techniques are leveraged to guide primal heuristics [7], make high-quality branching decisions [13 27 separate cutting planes to strengthen the formulation
[10, and improve node selection strategies [1 22 within the B&B framework. The advantage of this direction is that the MI techniques accelerate the traditional exact al algorithms without compromising the exactness.
Our work focuses on a deep integration of ML with dynamic programming (DP), another exact solving paradigm for COPs. Unlike MIP-based approaches, DP solves COPs by explicitly defining state-space formulation and determining state transition recurrences based on the problem's 's specific structure. DP is widely used to efficiently solve COPs with clear problem structures, such as knapsack and routing problems. However, its main drawback is the risk of state space explosion, also known as the 'curse of dimensionality'. To address this limitation, we employ ML techniques to approximate a projection function that maps the original state space onto a lower-dimension space, thereby substantially reducing its dimensionality. To the best of our knowledge, such learning- based paradigm for COPs has not been explored in the existing literature. Numerical experiments demonstrate its superior performance compared with state-of-the-an (SOTA) exact algorithms.
To illustrate this paradigm, this paper focuses on a classic COP, the Orienteering Problem with Time Windows (OPTW). In the OPTW. a set of vertices is given, each associated with a score, service time and a time window. The objective is to determine a tour that maximizes the total collected score while respecting all time window constraints. This problem, also known the Selective TSP [23], has more complex resource constraints and decision variables than the classic TSP. To solve the problem efficiently, we propose a learnin--uumented exact approach, DP-NG-MI, which combines an advanced deep learning model with a DP method enhanced by so-called Ng-route Relaxation (DP-NG). This learning model, termed DiConvNet, accelerates the DP algorithm by approximating effective relaxations of the problem's 's elementarity restrictions. The elementarity restrictions ensure that each vertex is visited most once in tour. Relaxing the restrictions reduces the dimensionality of the searched state space but may lead to a non-elementary path. The main contributions of this paper are summarized as follows:
Compared to the well-studied TSP, the problem we address is a more intricate COP, involving more constraints and high-dimensional features. Whether advanced learning models can achieve comparable success on such complex problems remains an open question. Moreover, we claim that OPTW applications can particularly benefit from the use of MI. techniques. For example, the Tourist Trip Design Problem (TTDP) B3 a variant of the OPTW, plans personalized itinerary for each individual tourist in a city within time limits. In practice, planners the same city often encounter similar instances, with variations mainly in tourist preferences. Such consistency provides an opportunity for ML uncover regional patterns and enhance effective real-time decision-making.
Problem Perspective:
Methodological Innovation: Our method combines the ML techniques and transitional DP algo- rithm, preserving optimality while significantly enhancing performance through data-driven insights. By leveraging imitation learning, the model accurately approximates the state space relaxation, thereby accelerating the DP algorithm. To the best of our knowledge, this is the first work to propose such solution paradigm. Despite the state space relaxation method is problem-specifee the overall paradigm is anticipated to generalize across broad spectrum of COPs defined over graph structures.
Extensive experiments on benchmark instances show that the proposed maaming--ugmentee exact algorithm, DP-NG-ML, significantly outperforms the SOTA exact al- gorithm, the pulse algorithm [12]. Moreover, this algorithm demonstrates a considerable speedup compared to the version without the integrated learning model. The experiments also show that the learning model achieves high accuracy in predictions, outperforming the heuristic methods commonly used in the literature COPs.
Empirical Validation:
2

---

2
Related Work
The OPTW is an NP-hard problem and several heuristics have been proposed to obtain high-quality solutions, including a depth-first search tree algorithm [16]. a granular variable neighborhood search [21] an ant colony system algorithm (26) and an iterated local search algorithm [34]. Ricardo Gama and Hugo L. Fernandes [29] proposed the first work to tackle the OPTW using a ML approach, based on a reinforcement learning framework combined with Pointer Networks. These methods are empirically efficient but offer guarantec of exactness optimality gap.
Due to the complexity of the OPTW, only two exact approaches have been proposed: a bidirectional DP with Decremental State Space Relaxation (DSSR) (30 and SOTA pulse algorithm [12]. The former 30 solves a relaxed version of the OPTW via DP algorithm, allowing subset of vertices to be visited more than once. The latter [12), which is based on a branch and bound search scheme with efficient pruning strategies, significantly outperforms the former on the OPTW benchmark in terms of both solution quality and computational time. We adopt the same DP iterative framework as in (30] but replace the DSSR with a more advanced relaxation technique, ng-route relaxation [2]. This relaxation is guided by so-called ng-sets, which impose the elementarity restrictions over set of edges and are approximated by our proposed learning model. To the best of our knowledge, no existing work has attempted to estimate the state space relaxation in DP using ML.
3 Dynamic programming with state space relaxation for OPTW
3.1 Problem definition and basic DP formulation
The OPTW is defined on a directed graph G = EV, where V is the set of vertices and E is the set of directed edges representing accessibility between vertex pairs. The cardinalities of V and E are denoted as [V] and [E), respectively. For each vertex E V, we are given: a 2D coordinate (x), x?). positive score 8; collected upon visiting the vertex, a time window [w.. w(( specifying the feasible arrival time interval, and a non-negative service duration de representing the time required to serve the vertex. For each pair of vertices (i, j). the travel time f.j is equal to the Euclidean distance between them. The objective is to determine an optimal tour that starts and ends at the depot O, visits a subset of vertices in V, maximizes the collected scores, and satisfies all time window constraints. This tour must be elementary, meaning it contains no cycles or duplicate vertices. The maximum length of the route is limited to given time budget T Taax-
The OPTW can be formulated as a special case of the classic Resource constrained Elementary Shortest Path Problem [30], for which polynomial-ting algorithm is known. DP is considered an efficient exact approach for solving this problem. Let F(S,7 T, i) denote the maximum collected score of path starts from the depot and ends vertex i, visiting each vertex in set S exactly once, with an elapsed time of r. F(S,T,i) can be computed by solving the recurrence equation:
F(S,T,i) max (F(S (1), 7'))) + $5|T + t3 S wi w ST' S w)) (3.))
(I)
Wi V,S C V. v. < w..
Set S denotes the set of visited vertices and can be interpreted set of dummy resources, each with a unit capacity. This set is typically encoded as a binary vector of length |V.. By recording this set, the path can be extended to other unvisited vertices that cycles avoided and all the searched paths are elementary. It is evident that the size of the state-space graph grows exponentially with the number of vertices [V] To reduce the number of states explored, we adopt state space relaxation technique, namely the ng-route relaxation Baldacci et al. 2 to project the original state space (S, T, onto dower-dimensional space.
3.2 Ng-route relaxation
The ng- ng-route relaxation, introduced by Baldacci et al. (2), provides a good compromise between enforcing elementarity constraints and enabling efficient exploration of the state space. For each vertex i E V, we define an ng-set N, C V. which is selected subset of vertices associated with vertex (according to some criterion). Let = {0, f1,-.., } be a partial path starting from the depot to vertex ip. which is associated with the set of visited vertices S S(P) and elapsed time The
3

---

basic DP algorithm explores the state space by extending paths to all possible succeeding vertices using equation ( We define II(P) S (() as the "memory" of path P. During the past extension of path P. for any intermediate vertex (1 < & S p), only the visited vertices that belong to the ng-set of ig can be retained in memory of P. Therefore, the memory set (T(P) is defined as the intersection of the visited vertices and the ng-sets of all subsequently visited vertices, and is given by:
[TP) (ix S(P) \ (ip) i E U (1p)-
With this definition, path P cannot be extended to vertices which are included in its memory II(P). The predefined ng-sets determine the degree of state space relaxation. all ng-sets are empty, all elementarity constraints equivalent to the original onc. If vertex i does not belong to Ni,, is not recorded in the memory of path P and may be revisited by the next extension of P. To prevent such cycles, ig is added to Ni,- thereby tightening the relaxation.
relaxed; conversely, if N, V for every vertex E V. the algorithm is
By applying this relaxation, the original state (S(P), r. i) of path P is mapped onto lower- dimensional state (II(P), r,) where (I( represented as binary vector of length NN.]. Since [N.] < [V] for each vertex i, the size of the state-space graph is significantly reduced. Figure 1 illustrates the path extension using given netsets. The main drawback of the relaxation technique is that the search in the relaxed state space does not guarantee to find optimal solution. A practical compromise is to iteratively tighten the relaxation, i.c., enlarge the ng-sets, based on the optimal non-elementary path obtained in each iteration of DP, until an optimal elementary path is eventually found. This procedure will be detailed in the next subsection.
Step
Step
Step 3
N2
Pa
Ps
P2
Fg 00 1- 2) n(P)) = (1.2)
Pg= = (0- 100-1)2-3 n(P)) = (2.3)
P = (0- 1 2- 3- ((P)) (1.2
Figure I: Illustration of path extensions using ng sets. The blue circular area indicates the ng-set of the associated vertex. Path P2 is extended to vertex to produce new path P3. as 3 & (T(P)). The memory of path P3 forgets the visited vertex 1, as Ng, does not contain 1. Consequently, vertex 1 can be revisited by path Ps.
Note that this iterative framework may incur higher computational costs compared to the basic DP algorithm, as the dimensionality of the state space increases with each iteration. An inappropriate criterion for expanding the ng-sets may introduce "unnecessary" vertices, further inflating the search space. We demonstrate that this issue can be mitigated by leveraging MI. techniques predict the ng-sets based on hidden patterns extracted from data. Moreover, the data-driven approach serves as an effective heuristic to initialize the ng-sets, thereby reducing the number of required iterations. Essentially, our goal is train a neural network that approximates the projection function, mapping the original state space to a suitable lower-dimension space in a one-shot manner. In this case, the ng-set of vertex i can be viewed as set of directed edges originating from i.
3.3 DP with ng-route relaxation
(()))))))))) where is the last visited vertex and s( ((P) ) is the collected score. Extending label L(P) to vertex j indicates adding the end of P. thereby generating new label. This extension feasible only if the time window constraint at j is satisfied and j has not been visited by path P. i.e., j & II(P). To limit the exponential growth in the number of labels, dominance test is applied to identify and discard labels that cannot lead to an optimal solution. By exploring the state space defined by the current ng-sets, path with the highest scores considered the optimal path for that iteration. the obtained path is non-elementary, the vertices involved in a cycle is updated to include the duplicate vertex, thereby preventing the same cycle from occurring in the next iteration. This exact approach referred as the DP-NG algorithm, with detailed description given in Appendix A.I and an outline in Appendix
state of path P can be interpreted as label L(P)= (i,t(P), s(P) II(P)).

---

A.2. Figure illustrates example of the DP-NG algorithm applied to vertex instance. It can be expected that states with lower time consumption and higher collected scores are more likely to survive the dominance test. Consequently, pairs of vertices with high individual scores, close spatial proximity and highly overleaped time windows are more likely form cycles. This observation motivates the use of graph structural features for predicting the ng-sets.
Optimal path
Opt path: 0-6 6-5---33--
ppt 0-6-5-3-2-3-0
Opt path: 0-6-5-3-2-0
iteration
iteration
Iteratiin
Figure 2: Illustration of the DP-NG algorithm at different iterations. The blue directed arrows represent the edges the optimal path in the current iteration, while the red dotted arrows indicate the current ng- netsets. The target vertex of the red dotted arrow belongs to the ng-set of its source vertex. In the first iteration, the DP algorithm finds non-elementary optimal path (0-6-5-3-5-3-0), and subsequently adds the edges (5,3) and (3,5) to the ng-sets to avoid revisiting the cycle between vertices and 3 in future iterations. In the second iteration, returns another non-elementary optimal path (0-6-5-3-2-3--), and edge (2,3) is added to the ngtsets. The algorithm ultimately finds an elementary path (0-6-5-3-2-0), at which point terminates.
Despite its theoretical merits, the ng-route relaxation may result in longer computation times. In the worst case, as iterations increase, the ng- ngtsets may eventually include all vertices, effectively reducing the method to standard DP without relaxation. However, if the ng-sets can be accurately predicted, number of required iterations can significantly reduced. This insight drives the development of our learning approach.
4
Learning approach for state space relaxation
4.1
Framework
To The overall framework our proposed soaning-augmentee approach is illustrated in Figure 3 enhance prediction accuracy, first apply edge reduction procedure that tags edges unlikely be part of any ng-set (see Appendix B. for details). The vertex and edges features are fed into to the DiConvNet model which ultimately outputs probabilistic heatmap over the edges. This heatmap indicates the likelihood of each edge being included in the ng-sets. A subset of edges with the highest probabilities is then selected to initialize the ng-sets, and the DP-NG algorithm is executed compute the optimal path.
Predicting the ng-sets for graph can be formulated possible directed edges, with those in the ng-sets labeled as positive. We train the DiConvNet network in supervised manner, using labels generated by the proposed DP-NG algorithm.
binary classification problem over all
4.2 Edge reduction
To improve prediction accuracy, propose an edge reduction procedure that leverages problem- specific characteristics to exclude edges that cannot belong to ng-sets. Two types of edges are excluded: (1) the edges connected the depot or self-loops; (2) any edge ei satisfying the following condition:
mar(w) + dg + Liss wi} + d, + 44 w/.
The first type of edges is excluded by definition, while the second type corresponds situation where cycle (j i j) is infeasible due to the time window constraints.
5

---

Input layers
DiConvNet layers
MLP
Original graph
DiConvNet model
Optinal path
Prediction
Edge reduction
Vertex festures Edge features
DP-NG
Reduced graph
Heatmap
Figure 3: Framework of the DP-NG-ML algorithm.
4.3
DiConyNet model
The DiConvNet model is based on the Graph Convolutional Network (GCN) architecture, ConvNet, originally proposed by Bresson and Laurent [5] ConvNet designed to directly approximate solutions to the TSP and has demonstrated strong performance [5]. However, preliminary experi- ments indicate that this model performs poorly for our problem, primarily because it is tailored for undirected graphs. To accommodate the asymmetry inherent in directed graphs and problems with time windows, we develop directed variant of this model, referred as DiConvNet.
The DiConvNet model comprises three main components: input layers, DiConvNet layers, and a Multi-Layer Perceptron (MLP) classifier. The input layers project the initial vertex and edge features into h--imennional embeddings, which are refined by DiConvNet layers. The MLP classifier then estimates the probability of each edge being included in the ng-sets. Details of the MLP classifier and the loss function are provided in Appendix B.1.
Input Layer The input features for each vertex include its 2D coordinates x; = (x) ..?), score 8,, service time d,, and time window w, (w. w³). These features are then embedded to h-diiennsinal vectors:
a, = 6 (a::|s:||ddlluus b1,
where 0 R4x6 and -||- is the concatenation operator. We consider the Euclidean distance t.j and the edge tags Cıj 1, as the input features for each edge Gij E E. Tags I and 0 indicate whether an edge is included or not in the corresponding reduced graph, while tags and represent edges connected to the depot and self-loops, respectively. Each of the two edge features is
h independently embedded into a 2 -ddimensional vector, and the resulting vectors are concatenated to form the final edge embedding, as expressed below:
Bij = O2t1s + by |8gcij
(5)
where 02 E x1 0g E X24
DiConvNet layer We define source embedding Pt and target embedding di for each vertex i, and an edge embedding hij for edge Cij. The source embedding p; is updated by iteratively aggregating the target embeddings of its out-neighbors (denoted Noue while the target embedding qa is updated by aggregating the source embeddings of its in-neighbors (denoted as (f). This directional propagation mechanism enables the model effectively capture the asymmetric structural patterns in directed graphs. Consequently, the edge embeddings, derived from the source and target embeddings, asymmetric. Both the source and target embeddings of each vertex are initialized with a;, while the initial embedding of each edge eij is set to Bij. The embeddings are updated at each iteration as:
a(1))))
p +1 = r/ ReLLU(BN(()pp
+ Σ JENome(()
vts 2 0gd)) with Ths = EyeNoui0 (1ly)))++ +E
(6)

---

o(h),)) Σ the o (bp))) with t/ys = EyEN.. o (hl,)))))))))
dt1 of ReI.U +
+e
JEN (6)
1++ h = M4 ReLU(BN Oarl + riodi)),
(8)
where 04, 04,05,0 06, 07, Os E B is the sigmoid function, e is small constant, C represents the Hadamard product, ReLU is the rectified linear unit, and BN stands for batch normalization. T/ acts as edge gate to govern the propagation of information from edge embeddings to vertex embeddings during each layer. Unlike the approach of Joshi et al. [13], our model aggregates messages from all incoming edges each vertex. This broader aggregation scheme enables the network to capture local structural information more comprehensively. Figure Aegure-Jillutaattee iillustrates how the DiConvNet layer updates the vertex embeddings and asymmetric edge embeddings. During each iteration, the source, target and edge embeddings are updated in sequence.
r
A
P
Mi
A/p
P
PL
q
Figure 4: The proposed DiConvNet layer for updating source, target and edge embeddings for each vertex i and edge 6iy in the graph. Blue and orange circles represent source and target embeddings, respectively, with dotted arrows indicating their propagated messages. Red dotted arrows represent messages propagated by edge embeddings.
5
Experiments
5.1 Experimental setup
Datasets. There two main classes of OPTW benchmark instances in the literature: Solomon's instances (32) and Cordeau's instances 7 8) both of which have known optimal solutions. In Solomon's 's instances, distances between locations Cordeau's 's instances, they are rounded to two decimal places. We randomly generate separate sets of training and validation instances for each class, following the methodologies outlined in the corresponding literature. Finally, the benchmark instances are used to evaluate the proposed DP-NG and DP-NG-ML algorithms. Detailed parameter settings are provided in Appendix C.
rounded
decimal place, whereas in
Solomon's 's instances. This dataset contains 29 instances with 100 vertices, organized into three categories: r-instances, where vertices are randomly located; c-instances, where vertices are clustered; and the re-instances, which combine random and clustered vertices. Within each category, the instances share identical vertex coordinates, service times, and scores, differing only in the time window settings. Hence, we generate 10,000 training instances and 1 1,000 validation instances per category, using the same vertex information except for the time windows. However, since Solomon (32 does not provide the parameters of generating time windows, we empirically determine them and generalize the trained model to Solomon's benchmark instances.
Cordeau's 's instances. This testbed comprises 10 instances, with the number of vertices ranging from 48 to 288, Compared to Solomon's 's instances, these instances are considered more challenging due their wider time windows [30]. Moreover, Cordeau's benchmark instances vary substantially in size, making it difficult to generalize across different instance scales. We generate 100,000 training instances and 1. 1.000 validation instances, each containing 50 vertices, and randomly select only 10,000 instances for each training epoch.
Training. In each training epoch, the 10,000 training instances are partitioned into 312 mini-batches, each comprising 32 instances. The model is trained using the Adam optimizer [88 with single-graph mini-batches, a learning rate of 10-1 and a decay factor of 1.01. The maximum training epochs is set to 1,500.
7

---

Evaluation. Since the performance of the DP-NG-ML algorithm is highly sensitive to both false positives and false negatives, we evaluate the learning model using the following metries:
Error Rate: the overall percentage of misclassified samples.
FNR: the proportion of positive samples incorrectly classified as negative.
FPR: the proportion of negative samples incorrectly classified as positive.
To evaluate performance on OPTW benchmark instances, we compare the proposed DP-NG and DP-NG-ML algorithms with the SOTA exact algorithm, the pulse algorithm [12]. Leveraging the publicly available implementation of the pulse algorithmf] provided by Duque et al. [12]. all algorithms are executed on the same computational platform to ensure fair comparison. To assess the effectiveness of the proposed DiConvNet model, we compare against the original ConvNet configured with identical architecture and training settings. The details of the ConvNet model are provided in Appendix B.2.
Network settings. For Solomon's instances, the DiConvNet model is configured with 10 DiConvNet layers, each containing 64 hidden units. For Cordeau's instances, the model uses 15 layers with 256 hidden units per layer. These configurations are chosen to enhance model performance while preventing memory overflow during training. The MLP classifier is configured with three layers across all cases.
5.2 Results
The learning models trained on an NVIDIA Tesla V100-SXM2 GPU with 32 GB of memory. The DP-NG and DP-NG-ML algorithms, along with the pulse algorithm [[] for comparison, are executed on a desktop equipped with a 2.5 GHz Intel Core i5-13490F processor and 16 GB of RAM. All computational times are reported in seconds, denoted as "time(s)".
Performance of predictive models. Table compares the performance of different predictive methods on Solomon's 's and Cordeau's benchmark instances. The best results are highlighted in bold. "Nearest" represents widely adopted heuristic that constructs the ng-set of each vertex by selecting its ñ closest neighbors [2], while the "MaxScores" heuristic, proposed in [28]. incorporates spatial proximity, vertex scores and time window constraints in more comprehensive manner. This comparison highlights that the formation of ng-sets involves intricate dependencies and structural patterns within the graph features. Such knowledge can be precisely learned through data-driven approaches.
Furthermore, the proposed DiConvNet achieves lower Error Rate and FPR than the original ConvNet model, although the ConvNet yields a lower FNR on the Solomon benchmark instances. Note that a slight increase in the FPR can lead to substantial expansion in the size of the ng-sets, because of the large proportion of negative samples (edges) in the graph. The reduction in FPR can be attributed to the model's ability capture asymmetric edge representations. For Cordeau's benchmark, although trained on random instances with only 50 vertices, the model still exhibits strong predictive capability, Nevertheless, to achieve further improvements, predicted probabilities, provided the probability exceeds 0.5. These selected edges serve as the initial ng-sets, leading improved performance of the DP-NG algorithm, shown in Tables 2 and 3 The best configuration of DiConyNet for Cordeau's benchmark is shown in the last row of Table with detailed parameter tuning results presented in Appendix D.
only select the top ñ. |V| edges with the highest
The evaluation of the predictive models relies on labels derived from the current DP-NG algorithm. While further improvements to the label quality are possible through more sophisticated ng- update strategies in the DP-NG algorithm, such enhancements may come with increased computational cost. For practical efficiency, maintain the current implementation.
Performance on OPTW benchmark. Tables and 3 report the performance of our proposed algorithms compared to the SOTA pulse algorithm [2] using Solomon's 's and Cordeau's benchmark instances. For Cordeau's 's benchmark, we set = 3, while for Solomon's 's benchmark, we do not impose any limit on the size of the predicted ng-sets. All instances solved to optimality by the exact algorithms, with the column Val" reporting the corresponding optimal values. The sizes of the predicted and final ng- sets are listed in the columns "pre-ng-size nize and "ng-size" respectively.
pestps://gitan haam//opaauuiianessDDPPPPPP Pul.eeeittttt
8

---

Table 1: Comparison of different predictive methods on on Solomon's 's and Cordeau's benchmark instances.
Solomon's 's Benchmark
Cordeau's Benchmark
Predictive Method
Error Rate(S))
FNR(%)
FPR(%)
Error Rate(%)
FNR(%)
FPR(%)
Nearest (û 2)
25.75
73.73
23.98
6,88
70.36
4.92
MaxScores (ñ =
24.44
51.42
23.29
5.89
53,99
4.4
Nearest (Ā 3)
29.17
66.66
27.72
9,10
61.50
7.59
MaxScores (ñ 3)
27.56
41.11
26.87
7.9
41.72
6.96
Nearest (û 4)
31.72
56.81
30.64
11.25
52.29
10.22
MaxScores
30.24
35.42
29.86
10.11
32.67
9.62
ConvNet DiConvNet DiConvNet(i = 3)
5.46
9.97
5.33
10.60
2.74
10.72
3.41
11.21
3.27
8.21
2.64
8.25
3.25
12.09
3.06
4.49
6.40
4.40
The Column "iter." denotes the number of iterations required compute the elementary optimal solution. The Column "olumnnPpulaa "Rpulse" reports the speedups of the DP-NG-ML algorithm compared to the pulse algorithm, while the column "Rmi" indicates the speedup of DP-NG-ML over the original DP-NG algorithm. Speedups greater than one are highlighted in bold. The last row presents the average results, where the average speedups are computed as the ratio of the computational time of the pulse algorithm to that of the DP-NG-MI algorithm.
Table 2 shows that, in 21 out of 29 instances, the learning- augmented DP-NG algorithm outperforms the pulse algorithm, despite achieving only a modest overall speedup of 1.26. The DP-NG algorithm becomes twice as fast when integrated with the learning model. Additionally, the number of iterations required to compute the elementary optimal solution is reduced from an average of 24.4 to 2.9.
Table 3 shows that the DP-NG-MI algorithm consistently outperforms the pulse algorithm on the more challenging Cordeau benchmark set, achieving an average speedup of 7.33. The performance advantage is even more pronounced than that observed on the Solomon benchmark instances. Nearly all instances require only a single run of the DP algorithm to obtain the optimal solution. It is worth noting that the model for Cordeau's 's instances is trained on 50-vertex random instances and evaluated on benchmark instances with 48 to 288 vertices. These results also demonstrate the effectiveness of the proposed method in generalizing to larger-scale and more complex instances. More detailed generalization performance results for different training distributions and instance sizes are presented in Appendix E. Furthermore, we observed that although the solving efficiency has improved substantially, the final size of the ng-sets has nearly tripled. This indicates that the presented algorithm still has significant room for improvement. One promising direction is to explore more advanced and better-suited learning models.
6 Conclusion
In this paper, we propose novel learning-augmented exact approach, DP-NG-ML, for solving classic combinatorial optimization problem, the Orienteering Problem with Time Windows (OPTW), which arises naturally in wide range of transportation and logistic applications. This approach combines an advanced deep learning model with dynamic programming (DP) algorithm enhanced by the ng-route relaxation technique. The relaxation technique relaxes the problem's 'ss elementarity restrictions, thereby effectively reducing the search space of the DP algorithm. its efficiency within data-driven paradigm, We develop a novel Graph Convolutional Network, DiConvNet, to construct the so-called ng-sets that define this relaxation. The network is trained in a supervised manner, using optimal solutions as high-quality labels. Extensive experiments on OPTW benchmark instances demonstrate that the proposed the SOTA exact algorithm. Moreover, DiConvNet shows superior performance compared to widely used heuristics for constructing the sets.
further improve
exact approach outperforms
Future work will explore incorporating reinforcement learning and other advanced learning models into our framework to enhance its generalization to solve large-scale problem instances with diverse data distributions. In addition, the proposed serming-augmmener approach can be extended to address other related combinatorial optimization problems and potentially be integrated into column generation frameworks for solving multi-route variants.

---

Table 2: Comparison of our proposed algorithm against the state-of-the-art pulse algorithm on Solomon's 's benchmark instances.
palse
DP-NG
DP-NG-MI
Instance
OptVal
time(s)
ng-siie
iter.
time(s)
pre-ng-
ng size
iter.
time(s)
Ryuis
Run
c101
320
0.016
0
0.041
0.034
0.47
1.21
e102
360
0.125
0.19
14
0.219
0.97
0.97
0.072
1.73
3,04
4.031
3.33
c104
420
1.801
1.96
54
1,865
2.74
2.97
8
2.227
0.81
2.18
c105
340
0.016
0
0,002
0.006
2.88
0.40
c106
0.02
0.008
0.24
0:24
0.003
4,75
c107
370
0.016
0
0.006
0.26
0.26
0.004
3.90
1.41
c108
370
0.032
0.07
0.036
1,09
1.12
0.038
0.85
0.95
c109
380
0.062
0.3
14
0.134
1.21
1.43
0.142
0.44
0.94
r101
198
0.001
0
0.001
0.022
0.05
0.05
r102
r103
293
10.511
2.28
44
12,945
3.94
3.53
1.566
6.35
7.81
r104
303
26.371
2.92
56
53. 129
4.39
4.01
37,254
0.71
1.43
1105
247
0.001
0.005
0.58
0.16
0.025
0.04
0.19
r106
293
3.841
2.177
44
4, 142
3,78
3.12
1.894
2.03
2.19
1107
11.993
1108
308
27.892
2.81
51
45.220
3.9
16.732
1.67
2.70
1109
277
0.032
0.43
17
0.166
1.6
1.29
0.039
0.83
4.29
r110
r11]
297
5.078
2,08
45
6,048
4.38
3.46
L6400
3.10
3.69
r112
298
3.887
1,93
45
5.582
4,36
4.04
2.222
1.75
2.51
re101
219
0.015
0.03
0.005
0.33
0.33
0.035
0.43
0.14
re102
266
0.078
0.41
1I
1.2
1,22
1.22
0.040
1.9.3
2.53
re104
301
1.159
0.86
16
0.635
2.43
2.43
0.262
4.42
2.42
re105
244
0.031
0.33
13
0.062
0.89
0.89
0.010
3.16
6.27
252
0.42
21
0.117
1,25
1.25
0.015
2.01
rc107
277
0.173
0.93
31
0.497
2.07
2.08
2
0.112
1.54
4.43
2.38
2.38
0.099
Mcan
3.372
1.02
24.4
5.449
2.11
1.91
2.9
2.448
1.38
2.23
Table 3: Comparison of our proposed algorithm against the state-of-the-art pulse algorithm on Cordeau benchmark instances.
pulse
DP-NG
DP-NG-ML
Instance
time(s)
ng-size
iter.
pre-ng-size
ng-size
Ryuiss
Resi
pr11
308
0.047
1.60
11
0.206
1.9
0.067
0.70
3.06
pr02
404
0.376
1.02
21
0.981
3
3
0.197
1.91
4.98
pr03
prl4
489
1.285
0.93
25
4.866
3
0.441
2.91
11.03
pros
195
18.857
1.08
28
13:925
3
3.402
5.54
4,09
pr06
pr07
298
0.078
0.97
15
0.138
1.89
1.89
0.020
3.82
6.74
pnt88
463
0.517
0.89
15
1.007
3
3
0.180
2,87
5.60
pr09
4.09
pr10
594
23.802
0.96
33
15.680
1.627
14.63
9.64
Mean
11.107
1.06
23.9
6.850
2.78
2.79
1.3
1.516
7.33
4.52
Acknowledgments
This work is supported by Guangdong Basic and Applied Basic Research Foundation (Grant No. 2023A1515 10228, 2024A15151401 Hetao Shenzhen- Kong Science and Technology Innovation Cooperation Zone Project (No. Ww..HZQSSS-KCA CWTNSSKCCYBB-220000 of China (Grant No. 2023 1009300) Science and Technology Innovation Team of Shaanxi Province 2023-CX-TD-077 the Key Research and Development Program of Shaanxi (2024GH- ZDXM-48), and the National Natural Science Foundation of China (Grant 72571280, 72101264, 72431011, 72421002).
National Key R&D Program
References
[1] M. C. Angelini and F. Ricci-Tersengue Modern graph neural networks do worse than classical greedy algorithms solving combinatorial optimization problems like maximum independent set. Nature Machine Intelligence, 5(1):29-31, 2022.
[2] R. Baldacci, A. Mingozzi, and R. Roberti. New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem. Operations Research, 1269-1226911288 2011.
10

---

[3] I. Bello, H. Pham, Q. V. Le, M. Norouzi, and S. Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv:1611.09944 2016.
[4] Y. Bengio, A. Lodi, and A. Prouvost. Machine learning for combinatorial optimization: A methodological tour d'horizon. European Journal of Operational Research, 290(2):405-43) 421, 2021.
[5] X. Bresson and T. Laurent. Residual Gated Graph ConvNets. arXiv preprint arXiv:1711.0755. 2018.
[6] X. Bresson and T. Laurent. The Transformer Network for the Traveling Salesman Problem. arXiv preprint arXiv:2103.03012, 2021.
[7] J.-F. Cordeau, M. Gendreau, and G. Laporte. A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks, 30(2):005-119, 1997.
[8] J.-F. Cordeau, G. Laporte. and A. Mercier. A unified tabu search heuristic for vehicle routing problems with time windows. Journal of the Operational Research Society, 52(8):928-936. 2001.
[9] H. Dai, E. B. Khalil, Y. Zhang, B. Dilkina, and L. Song. Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems, 2017.
[10] A. Deza and E. B. Khalil. Machine learning for cutting planes in integer programming: A survey, In Proceedings of the Thirty-Second International Joinı Conference on Artificial Intelligence, pages 2592-6000. International Joint Conferences on Artificial Intelligence Organization, 2023.
[11] J.-Y. Ding, C. Zhang, L. Shen, S. Li, B. Wang, Y. Xu, and L. Song. Accelerating Primal Solution Findings for Mixed Integer Programs Based on Solution Prediction. Proceedings of the AAAI Conference Artificial Intelligence, 1452)::452-1459 2020.
[12] D. Duque, L. Lozano, and A. L. Medaglia. Solving the Orienteering Problem with Time Windows via the Pulse Framework. Computers & Operations Research, 54:168-178 2015.
[13] M. Gasse, D. Chételat, N. Ferroni, L. Charlin, and A. Lodi. Exact Combinatorial Optimization with Graph Convolutional Neural Networks. In Advances Neural Information Processing Systems, 2019.
[14] H. Hc, H. Daumé, and J. Eisner. Learning to search in branch and bound algorithms. In Advances in Neural Information Processing Systems, volume 27, 2014.
[15] C. K. Joshi, T. Laurent, and X. Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint MX06:1906.01220 2019.
[16] M. G. Kantor and M. B. Rosenwein. The Orienteering Problem with Time Windows. The Journal of the Operational Research Society, 43(6):629-635, 1992.
[17] E. B. Khalil, C. Morris, and A. Lodi. MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers. Proceedings of the AAAI Conference on Artificial Intelligence, 36(9): 10219-10227, June 2022.
[18] D. P. Kingma and Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 2017.
[19] W. Kool, H. Hoof, and M. Welling. Attention, Learn to Solve Routing Problems! arXiv preprint 1803:v1100..8444 2019.
[20] R. Kuroiwa and J. C. Beck. Solving Domain- Indepenenn Dynamic Programming Problems with Anytime Heuristic Search. Proceedings of the International Conference on Automated Planning and Scheduling, 33(1):245-253, 2023.
[21] N. Labadie, R. Mansini, J. Melechovsky, and R. Wolfler Calvo. The team orienteering problem with time windows: An Ip-based granular variable neighborhood search. European Journal of Operational Research, 220(1):15-27, 2012.

---

[22] A. G. Labassi, D. Chételat, and A. Lodi. Learning to Compare Nodes in Branch and Bound with Graph Neural Networks, In Advances Neural Information Processing Systems, 2022.
[23] G. Laporte and S. Martello. The selective travelling salesman problem. Discrete Applied Mathemalics, 26(2):193-207, 1990.
[24] Z. Li, Q. Chen, and V. Koltun. Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search. In Advances in Neural Information Processing Systems, 2018.
[25] R. Martinelli, D. Pecin, and M. Poggi. Efficient elementary and restricted non-elementary route
pricing. European Journal of Operational Research, 239(1):102-111, 2014.
[26] R. Montemanni and L. M. Gambardella. An ant colony system for the team orienteering problem with time windows. Foumdations of Computing and Decision Science, 34(4):287-306, 2009.
[27] V. Nair, S. Bartunov, F. Gimeno. I. Glehn, P. Lichocki, I. Lobov, B. O'Donoghue, N. Sonnerat, Wang, R. Addanki, T. Hapuarachchi, T. Keck, Keeling, Kohli, I. Ktena, Y. Li. O. Vinyals, and Y. Zwols. Solving Mixed Integer Programs Using Neural Networks. arXiv preprint arXiv:2012.13349 2021.
C. Tjandraatmadja,
[28] G. Peng, J. Wang, G. Song, A. Gunawan, L. Xing, and Vansteenwegen. Branch-and and-price for agile earth observation satellite scheduling. European Journal of Operational Research, 2025.
[29] Ricardo Gama and Hugo L. Fernandes. A reinforcement learning approach to the orienteering problem with time windows. Computers & Operations Research, 133:105357, 2021.
[30] G. Righini and M. Salani. Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming. Computers Operations Research, 36(4): 191-11233,,, 2009.
[31] L. Scavuzzo, K. Aardal, A. Lodi, and N. Yorke-Smith. Machine learning augmented branch and bound for mixed integer linear programming. Mathematical Programming, 2024.
[32] M. M. Solomon. Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints. Operations Research, 35(2):254-265, 1987.
[33] P. Vansteenwegen and D. Van Oudheusden. The Mobile Tourist Guide: An OR Opportunity. OR Insight, 20(3):21-21 2007.
[34] Vansteenwegen, W. Souffriau, G. Vanden Berghe, and D. Van Oudheusden. Iterated local search for the team orienteering problem with time windows. Computers & Operations Research, 36(12):3281-3290, 2009.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In the abstract and introduction, have provided detailed and accurate description of the scope the research, related works in OPTW, limitations of current research on traditional and learning- based approaches, and the contributions of this paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We have discussed the limitations of our DiConvNet in Section 5 and in the Conclusion and Future Work. Our framework relies on optimal solutions as labels, which restricts the availability of high-quality training data for large-scale instances. Furthermore, the optimization results suggest that there is still considerable room for improvement the augmented al algorithm.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model vell-specificattin, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
13

---

3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We have provided the full set of assumptions and complete, correct proof in Sections and 4, as well as Appendices A and B.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: All information required to reproduce the main experimental results is provided, covering the exact DP-NG algorithm, the network architecture, and the dataset generation procedure.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
14

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: If the paper is accepted, the data and code will be considered for public release.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ //nips.co... ctailss.cc/publcc/uuuu..o http://gggiidee/ddSSuubbbiiii
wtt.subbiissioooooooooooooo for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All training and testing details are specified in Section 5.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
Justification: We did not perform statistical hypothesis testing because both the proposed and baseline algorithms are exact methods, where each step of the algorithm yields deterministic results. There is no randomness in the solution process itself (as would be the case in heuristic stochastic methods). The only source of variability lies in minor fluctuations in runtime measurements due to system-level factors. To reduce this noise, we report the
15

---

average over multiple independent runs. This ensures the reliability of our performance metrics.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
Question:
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: We have provided sufficient information on the computer resources in Section 5.2.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- cration due to laws or regulations their jurisdiction).
10. Broader impacts
16

---

Question:
Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We have discussed the potential impacts of the work performed in the Section 1, Introduction. The OPTW studied arises in a wide range of transportation and logistics applications. The proposed learning-aug auggmntee approach is expected generalize across broad spectrum of combinatorial optimization problems defined over graph structures, such the Vehicle Routing Problem, the delivery man problem and others.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Answer:[NA)
Justification:
The paper poses no such risks
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
17

---

Justification:
They are properly credited and respected in this paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperssiippssiiii thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out to the asset's s creators.
13. New assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
18

---

Answer: [N]]
The paper does not involve crowdsourcing nor research with human subjects Guidelines:
Justification:
The answer NA means that the paper does involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: The core methodologies in this study do not depend on LLMs, which are used solely for grammar correction.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non stannaaddard components.
Please refer to our LLM policy for what should or should not be described.
19

---

A DP-NG algorithm Details
A.1 DP with ng-route relaxation
In the DP algorithm, label associated with vertex represents a path starting depot and ending vertex i. The DP algorithm repeatedly extends each label to generate new labels all the resources constraints are satisfied. To limit the exponential increase of the number of labels, dominance test is applied between the new label and other existing labels and the dominated one will be pruned. This algorithm can be further improved by extending labels bi-directionally and matching the labels in both directions to form complete paths [30]. Since the forward and backward extensions are symmetrical each other, we only explain the forward labels for simplicity.
Let L(P) = (1, T(P), ((P))[((P) be the forward label associated with its last visited vertex i, arrival time r(P), score s(P) and memory set II).). Label L(P) can be extended to vertex if 2p+1 & (P) and r(P) + d, + tij I wg. After the extension, a new label ((P') can be obtained from the label L(P) by the following operations:
L(P") (i, (ax(r() + d: + lig, w)). + 5j, IILL N,
The ng-route relaxation is incorporated into the DP algorithm by permitting the generation of non- elementary labels. Specifically, label (P) can be extended to a previously visited vertex, provided that this vertex is not included in its memory set IT(P).
Once a new label is generated, dominance test is performed between the new label and existing labels associated with the same vertex. Any dominated label is pruned and will no longer be extended. Given two labels L1 and L2 associated with the same vertex, L1 dominates L2 when the following conditions hold and at least one of them is strict:
T(L)) < ((2)), s(Li) 2 s(L2): I(L.)) C (((2).
(10)
These conditions indicate that any further extension from label L2 can also be achieved by label L1, while Ln still maintains higher collected score than L2. Evidently, the size of the ng-sets increases, each label must memorize more visited vertices, resulting in higher-dimension state space that must be explored.
The extension of forward and backward labels is terminated at the midpoint of the planning horizon [0, ]mae]. and the two are matched together to form complete paths that start and end at the depot. The matching procedure between forward label L(Pr) ((P)) s(P)), I{())) and backward label L(Ps) = (j, T (Pt), s(P)), (Is))) is feasible only if the following conditions are satisfied:
7 T(P)) + d. 44 T(P) dj:
(11)
((P)) =
After the matching procedure, the complete path with the highest collected scores is considered the optimal solution at the current iteration. If the solution is non-elementary. the ng-sets are accordingly enlarged and the DP algorithm is rerum; otherwise, the optimal solution for the primal problem is obtained.
A.2 Outline of DP-NG algorithm
The pseudocode of the DP-NG algorithm with core procedures is provided in Algorithm I denotes the set of ng- ng-sets, and R represents the set of all labels, i.e., the union of the label sets R; for all vertices i. For each vertex i, N₁ is initially empty. In each iteration, once non- non-elementary optimal path is computed, the ne-sets are updated to forbid the cycles that occur in the path. Unlike standard DP algorithms (30 25 our method retains non-dominated labels after each iteration, thereby enabling their reuse the subsequent iteration to effectively prune unpromising labels during the dominance test.
N
20

---

Algorithm 1: The Dynamic Programming with Ng-route Relaxation algorithm
Define N = N; <- 0, E V; //Initialize ng-sets empty sets
Procedure DP-MG
Input: pre-defined ng-sets N, input graph G
Output: elementary optimal path p
R = (R) U R. + 0, R t D. ViEV; isElem t- false; k t- 0:
while not isElem do
R f dynamiiPPogrammingg
G);
Pe + seleetOpimallath Rx);
if Pat PF) then
P <- Pk:
isElem true;
else
N f NSeateN Pt);;
R + updateLabell(RR N);
k k 11;
return P
Procedure
(R,iinngnnR.. G):
Define R = R/ U R = R. vi e V:R² = U, vi V:
T 0: //Initialliie unchecked vertices set with depot
while Φ! - do
i pop($);
AR/ forwarddExtension((R.
R + ArwarrdDominaaceeAARR R/);
AR + buckwwardExxenssion(((}))
R backwardDoominanceeAAAll R
return matchinggrroveduucRR// RR);
Procedure updateNGSets (N, P):
forall cycle = (v..... v) E C(P) do
forall E S(C) {o) do N U(1)
return N
B DP-NG-ML algorithm Details
B.1 Other components of DiConyNet model
MIPP classifier The edge embedding huy of the last DiConvNet layer used to compute the probability that the directed edge Eij belongs to the ng-sets of the graph. The output of the MLP classifier is then passed through softmax output layer normalize the probabilities. For each edge esj, the probability of being assigned label is expressed as:
fry 8) MLP (M!
(12)
where Imar represents the maximum number DiConyNet layer.
Loss function. As the problem size increases, the classification task becomes increasingly imbal- anced toward the negative class. To address this issue, we introduce appropriate class weights to balance the contributions of positive and negative samples in the loss function. Accordingly, we minimize the weighted binary cross-entropy loss for a mini-batch of training sample (G* 1¹) where 1 E {0, 13 [l represent the binary labels of graph G/k The loss function is calculated by:
m
0)) m
logg
0) w (1 log (G,(G*;)))
(13)
21

---

where 1y is the label of eij in I", (iy is the corresponding probability, and m denotes the batch size. For each instance k, we compute balanced class weights as w 2-no
[el and w 2-n:
where |E| is the total number of edges in the graph, and roo denote the number of negative and positive samples, respectively.
B.2 ConvNet model
The only difference between the ConvNet and DiConvNer models lies in the graph convolutional layers. The rest of the architecture remains identical.
ConvNet layers. Let v and by denote the vertex and edge feature vectors at layer respectively, associated with vertex i and edge Eij. We define the vertex feature and edge feature at the next layer as follows:
o(hig) The 2 (bg3))) with nks EyEN o )
1. ut ReRLLUBBN(',,
E
(14)
.. (8)
h2 = M' + (eL + OGU! + 12
(15)
where 04, 0g, 0g. 87 0s E RR is the sigmoid function, is small constant, @ represents the Hadamard product, ReLU is the rectified linear unit, and BN stands for batch normalization. The initial inputs the ConvNet are defined as vf a; for each vertex and h2J = Big for each edge. This network architecture is based on the Residual Gated Graph ConvNet proposed by Bresson and Laurent [5), with an extension incorporate edge embeddings. T/ acts as edge gate govern the propagation of information from edge embeddings to vertex embeddings during each convolutional layer. Evidently, the ConvNet model produces symmetric embeddings for all edges.
B.3 Outline of DP-NG-ML, algorithm
The pseudocode of the proposed DP-NG-ML algorithm is presented in Algorithm [ The process begins with edge reduction procedure that tags edges and produces reduced graph. The vertex and edge initial features are then processed by the trained DiConvNet model to predict the ng-sets. Finally, the DP-NG algorithm is executed to compute the optimal solution.
Algorithm 2:
The learning-augmentte DP-NG-ML algorithm Procedure DP-NG-MI ():
Input: trained DiConvNet model [(; 0), input graph G
Output: elementary optimal path P"
Greduced eddgeReduction((G))
Ñ forwardPass (f (Greducedd 0));
P DP-NNG(N G);
return P
C Datasets settings
We summarize below the parameter settings used for generating training instances in our experiments.
Solomon's 's instances. For each instance, 50%, 75% or 100% of vertices are randomly selected to receive time windows, while the time windows of remaining vertices are assigned fixed windows [w] + tus, wi too - d.). For each vertex i, the midpoint of the time window is sampled uniformly at random from the interval (w) + fus, wi too d.). The half- width of each time window is drawn from a normal distribution with mean j and standard deviation 8, where μ and are randomly selected integers from [5, 50) and [0, 10), respectively, for each instance.
Cordeau's instances. To generate clustered instances, we first randomly generate several centers in the [-50, 50]2 square according to a continuous uniform distribution. For instances with sizes 20, 30, and 50, the number of centers is set to 2, 3, and 4, respectively. One of the centers is
22

---

randomly selected as the depot. The vertex coordinates are randomly generated with a continuous uniform distribution within 1-100, 100] and both the score and service time are random integers within the range [1, 25). For each newly generated vertex, the distance Le to the closest center is less than c0.05te, the vertex is accepted; otherwise,
discarded. This process is repeated until the specified number of vertices has been generated. For the time window of each vertex, its opening time is random integer between [60, 480], and its length a random integer between (90, 180).
calculated,
D Parameter tuning
For each instance, the learning model produces probabilistic heatmap over the edges, indicating the likelihood of each edge being included in the ng-sets. When evaluated on large-size instances, significant number of misclassified edges may diminish the performance gains brought by the learning model. To preserve the improvement on benchmark instances, we only select the top n [V] edges with the highest predicted probabilities, provided the probability exceeds 0.5. Parameter tuning experiments for are conducted to identify the best configuration, as summarized Tables 4 and The best-performing ñ values are highlighted in bold. We observed that larger tend identify more positive samples, thereby significantly reducing the number of iterations. However, this also leads to higher number of misclassified positives, resulting in larger ng-sets. For simpler instances like Solomon's s, tuning ñ has limited impact on performance. However, for larger and more complex instances such as Cordeau's, selecting an appropriate is crucial for achieving good performance.
Table 4: Performance of our proposed approach with different ñ on Solomon's benchmark instances.
Solomon
DiConvNet
DP-NG-ML
ñ
Error Rate(%)
FNR (%)
FPR(% (%)
ng-size
iter.
time(s)
0.5
2.78
45.94
1.21
1.05
16.3
4.47
I
2.84
31.25
1.77
1.19
11.6
3.63
1.5
2,83
22.62
2.12
1.33
8.1
3,34
2
2.90
17.27
2.44
1.48
5.6
3,05
2.5
3,06
13.78
2.77
1.64
4.0
2.62
3
3,25
12.09
3.06
1.78
3.2
2.45
3.5
3.36
11.43
3.21
1.87
3.0
2.50
4
3.41
11.21
3.27
1.91
2.9
2.41
4.5
3.41
11.21
3,27
1.91
2.9
2.41
5
3.41
11.21
3.27
1.91
2.9
2.41
Table Performance of our proposed approach with different on Cordeau's benchmark instances.
Cordeau
DiConyNet
DP-NG-ML
Error Rate %)
FNR %6)
FPR(%)
ng-size
iter.
time(s)
0.5
2.10
58.18
0.17
1.06
14.0
4.47
1.77
33.38
0.72
1.23
8.2
3.30
1.5
2.20
18,86
1.69
1.58
4.3
2.44
2
3.07
12.03
2.82
2.01
2.5
1.87
2.5
3.75
8.43
3.59
2.39
1.7
1.59
3
4.49
6.40
4.40
2.79
1.3
1.49
3.5
5.18
5.27
5.13
3.16
1.3
1.84
4
5.71
4.43
5.69
3.48
1.90
4.5
6.17
4.08
6.16
3.76
1.2
2.19
5
6.53
3.85
6.53
4.01
1.2
2.75
23

---

E
More experimental results
E.1
Test on more difficult instances
The SOTA pulse algorithm was evaluated by Duque et al. [12] only on the standard Solomon and Cordeau benchmark instances, which have been tested in Tables 2 and 3 To further assess the performance of our algorithm on harder instances, we generated 20 Cordeau-style new instances with 100 vertices and time windows twice as wide. To ensure robust performance, the model was retrained using 10,000 labeled instances with 50 vertices and wide time windows. The computational times (in seconds) are reported in 6
The results show that the learning-basse method accelerates the DP-NG algorithm by a factor of 1.61 on average, while still outperforming the state-of-the-art pulse algorithm. This limited improvement mainly stems from prediction accuracy. Increasing both the number and size of training instances could further enhance the results.
Table 6: Comparison of our proposed algorithm against the state-of th-the-rrt pulse algorithm on Cordeau-style instances with wide time windows.
SOTA-pulse
DP-NG
DP-NG-M ML
Instance
Opt
time(s)
ng-size
Iter.
timets)
ng-size
Iter.
time(s)
Rpulse
Ras!
100.1 0
511
71.77
5.56
67
367
367.28
6.99
12
281.19
0.26
1.31
100 1
485
19.29
5.79
161.33
6.51
113.25
0.17
1.42
100 2
498
18.51
3.55
38
35.85
5.92
2
26.15
0.71
1.37
100
13.66
2.76
8.39
100 4
503
265.44
4.84
53
93.12
6.85
12
112.46
2.36
0.83
100
100 6
516
8.17
2.7
25
11.78
5.6
6.86
1.19
1.72
100_7
7.18
3.72
27.26
5.05
32.86
0.22
0.83
100 8
495
24.29
4.91
58
148.31
6.25
33.03
0.74
4.49
100_3 9
4.75
2.95
13:47
4,52
4.85
0.98
2.78
100_
577
1022.04
7,35
83
1452.04
8.49
1276.55
0.80
1.14
II
4.14
92.12
86.07
0.12
1.07
100_12
486
7.60
5,02
51
40.95
6,63
45.22
0.17
0.91
100 13
482
46.58
4.12
49
66.83
5.2
7
38.31
1.22
1.74
100
583
1031,12
4.14
97.24
7.45
129.05
7.99
0.75
100_15
493
89
4.2
192.83
6.21
235.07
0.38
0.82
100
462
6.90
3.3
10.92
4,79
6.14
1.12
1.78
100 17
505
175 96
5.81
66
695.98
6.41
450.45
0.39
1.55
100
488
2293.26 26
6.54
56
363.42
6.82
6
149.93
15.30
2.42
100 19
463
31.56
4.15
56
38.37
5.01
20.67
1.53
1.86
273.96
159.69
E.2 Comparison with DiDPPy solver
We tested a generic DP solver, DiDPPy (20), on the OPTW using Cordeau instances. For fair comparison, we added forced transitions that treat unvisited vertices as visited if they are infeasible due to time window constraints at the current state. In this case, more unpromising states will be pruned. Unfortunately, instances with more than 90 vertices ran out of memory using DiDPPy. We select the first 90 vertices (excluding the depot) from each instance to create instances. The computational time in seconds are shown Table 7 The number of vertices indicated by the suffix in the name. The results show that the DP-NG algorithm 100 times faster than the DiDPPy using the CABS solver. With the learning method integrated, the speedup reaches up to 800 times.
F Generalization performance
Figure provides the results of the proposed DP-NG-ML algorithm with various training dataset distributions of Cordeau's 's instances and instance sizes. The clustered training datasets are denoted as "Train-CIVI where [V] is the instance size. Instances with uniform distributions are labeled as "R" The parameter î is set to in all experiments. Overall, on smaller instances, the proposed method performs better when trained on smaller-sized instances. However, for generalization to larger in- stances, training the model on larger-sized instances tends to yield better performance. This is because larger instances offer greater potential for performance improvement through learning-augmenti approach, and models trained on larger data more capable of identifying a greater number of
24

---

Table 7: Comparison of our proposed algorithm against the generic dynamic programming solver DiDPPy.
Instance
OptVal
DiDPPy
DP-NG
Speedupl
DP-NG-ML
Speedup2
pr01_43
308
3.094
0.233
13.29
0.079
38,93
pr02_90
392
148.266
0.882
168.03
0.139
1065.18
pr03_90 _
331
51.841
0.782
66.29
0.231
224.82
pr04 90
356
33.328
0.674
49.43
0.169
197.45
pr05 90
443
193.404
1,386
139.54
0.551
350.70
pr06 90
329
29.954
0.527
56.85
0.046
656.43
pr07_72
298
12.956
0.187
69.14
0.016
810.99
pr08_ 90
374
19.59
0.397
49.30
0.034
568.74
pr09_90
320
100.259
0,346
289.93
0.057
1757.46
pr10_90 90
399
169.158
0.862
196.35
0.069
2465.47
Mean
76.185
0.628
109.81
0.139
813.62
positive samples. Moreover, even when the coordinate distribution of the training instances differs from that the test instances, the method still demonstrates significant performance improvements.
Generalization Performance
Train-C20 1.420
3.960
4.450
3,420
2.840
Train-C30 2.030
3.220
6.320
5,770
5.040
Train9200
1.280
4.520
3,520
2:840
Train-33
1.570
1.920
3.920
4.300
3.800
Triin2500
1.470
7,780
4.600
c2o
C30
C80
C100
Datasets
Figure Evaluation of DP-NG-MI. algorithm performance on Cordeau's instances with varying sizes and training distributions. The vertical axis represents training instances with clustered and uniform distributions of sizes 20, 30, and 50. The horizontal axis shows test instances with different sizes under clustered distribution. The heatmap illustrates the speedups achieved under various configurations relative to the standard DP-NG algorithm.
G
Visualizing Model Predictions
Figures|6 the visualizations of ground truth and predicted ng-sets for Cordeau's benchmark "pr01" with 48 vertices. The comparative visualizations demonstrate that the proposed learning models effectively capture the structural patterns of sets,,,, successfully identifying a large proportion of positive samples from a very large sample pool. The edge set in the ground-truth labels exhibits certain structural properties, such as short distances between nodes and proximity to the depot node. These properties, to some extent, help the neural network better identify and predict. The comparison between Figures (b) and (c) shows that the DiConvNet model can more effectively capture the asymmetry of edges than the ConvNet model.
25

---

(a)
(b)
(c)
Figure 6: Visualizations of (a) the ground truth ng-sets, and the ng-sets predicted by (b) ConvNet and (c) DiConvNet. Red arrows represent positive samples, while blue arrows indicate false positives. In (a), the tour shown with green arrows denotes the optimal path. Circle sizes are scaled proportionally the vertex scores.
26


Reviews:
[{"review_id": "O28VQgGd3s", "reviewer": "Reviewer_Nr8A", "summary": "This paper considers Orienteering Problem with Time Windows (OPTW), a more practical and harder variant of the traveling salesman problem. The paper considers the \"ng-route relaxation method\", which is a dynamic programming algorithm that solves the problem exactly. The idea is that optimal solutions are found, that maybe contain cycles. Gradually, the restrictions are increased to ensure that a feasible solution is eventually found. The original method is to simply add existing cycles of the current optimal solution to the \"ng-sets\" of each vertex to eliminate these in the next round. The authors propose a deep-learning method, based on Graph Convolutional Networks (GCN) to try to speed up this algorithm by predicting which edgess should belong to the ng-sets. A modification of the original GCN model to directed graphs is proposed.", "questions": "The context of the literature provided in the paper is very minimal. If the authors could greatly expand this discussion, so that the novelty of the proposed method could be accurately assessed, it could impact my rating. See more discussion under Weaknesses.", "limitations": "yes", "rating": 2, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 1, "originality": 1, "strengths_and_weaknesses": "+ Speeding up exact algorithms using ML is a good role for ML within combinatorial optimization, as the authors argue, as the optimality guarantee of the original, exact algorithm still holds. However, this is far from the first work to propose this idea. \n+ The proposed method appears to work well in practice, as evidenced by the empirical results.\n\nWeaknesses:\n- There are quite a few works on using deep learning, including RL and GNNs, to accelerate the solution of linear programs. Given the connection between dynamic programming and LPs, I wonder how relevant this literature could be to this paper. For example, here's a survey for ML-augmented approaches to branch-and-bound [1]. Very little related work, concerning ML to speed up exact optimization, is discussed by the authors. \n\n[1] Scavuzzo, L., Aardal, K., Lodi, A. et al. Machine learning augmented branch and bound for mixed integer linear programming. Math. Program. (2024). https://doi.org/10.1007/s10107-024-02130-y\n\n- There are many works adapting the original GCNs to directed graphs. So it's unclear what the novelty here is. I'm hardly an expert in this area, but the architecture proposed in this paper doesn't seem very novel. Moreover, none of this related work is discussed, and it is presented a major contribution to adapt the GCN to directed graphs.\n\nFor example: \n\n[2] Korban and Li. DDGCN: A Dynamic Directed Graph Convolutional Network for Action Recognition.\n[3] Rossi et al. Edge Directionality Improves Learning on Heterophilic Graphs.", "was_revised": true, "final_justification": "I have read the authors' rebuttal and the other reviews. \nIn response:\n- A comprehensive literature survey of ML for combinatorial optimization problems is not required. However, it remains important to place the proposed methods in context and clearly explain the novelty. For example, in the contributions paragraph, there is this sentence (line 71):  \"This innovative paradigm is anticipated to generalize across a broad spectrum of COPs defined over graph structures, such as the Vehicle Routing Problem (VRP) [ 2], the delivery man problem [ 25 ], and others.\" But the related work section discusses the OPTW problem only. Relevant work on related problems should be discussed.\n\n- The way the paper was written, I was under the impression the Section 4.2 was a significant component of the novelty of the proposed method (Indeed, it appears to be the only technological innovation introduced). The main argument for novelty is the generalization of DiConvNet to directed graphs. My point was that there are many directed GNN architectures that already exist that may perform well. In the rebuttal, the authors indicate that Section 4.2 is not a major part of their contribution. \n\n- Finally, after reading the other reviewer comments, I agree that problem instances that can be solved exactly in seconds are probably too small to demonstrate the effectiveness of the proposed method.", "rebuttal": "Thank you for your valuable comments and suggestions. Owing to the strict page limit, we did not include a comprehensive review of the literature on solving combinatorial optimization problems (COPs) with machine learning (ML). We will expand this part in the revised version.\n\n**1. Positioning of this work in related literature.**\n\nThe use of ML to solve COPs has emerged as a highly promising research direction, attracting considerable attention in recent years. Most existing approaches employ ML models as heuristics to directly solve the problems by constructing satisfactory solutions via learned predictions. However, these methods are often detached from the underlying mathematical models, lacking theoretical guarantees on solution quality.\n\nResearch on integrating ML with exact methods for COPs remains relatively limited, largely due to the complexity of designing such algorithms and the black-box nature of learning models. The predominant research trend is to formulate COPs as mixed-integer programming models (MIP models) and enhance key components of traditional exact approaches for MIP models using ML techniques. The majority of research efforts concentrate on enhancing branch-and-bound (B\\&B) based algorithms, which serve as the foundational theoretical tool in modern MILP solvers [1]. In this line of research, ML techniques are leveraged to guide primal heuristics, make high-quality branching decisions, separate cutting planes to strengthen the formulation, and improve node selection strategies within B\\&B frameworks. These enhancements are problem-agnostic and can be directly integrated into generic MIP solvers.\n\nOur work focuses on a deep integration of ML techniques with dynamic programming (DP), another exact solving paradigm for COPs. Unlike MIP-based approaches, DP solves COPs by explicitly defining a state-space formulation and determining state transition recurrences based on the problem’s specific structure. DP is widely used to efficiently solve COPs with clear problem structures, such as knapsack and routing problems. However, its main drawback is the risk of state space explosion, also known as the `curse of dimensionality'. To address this weakness, Christofides et al. [2] presented a state space relaxation technique which projects the search space explored by DP onto a lower-dimensional space to accelerate the DP. The main drawback of such relaxation is that the search in the lower dimensional state space does not guarantee to find an optimal solution. A practical compromise is to iteratively tighten the relaxation based on the computed infeasible solution, until an optimal solution is eventually found [3, 4] However, this iterative framework may lead to higher computational costs, as the DP algorithm needs to be executed multiple times, and the final relaxation is only identified once the computed solution is feasible.\n\nTo overcome this limitation, we utilize ML techniques to predict the final relaxation, so that the DP algorithm can achieve optimality in low-dimensional state space with limited iterations and computation time. In essence, the learning model approximates a projection function that maps the original state space to an appropriate lower-dimension space. To the best of our knowledge, this learning-based paradigm for COPs has not been explored in the existing literature.\n\nThis work takes the OPTW as an example to demonstrate such paradigm. The DP algorithm for solving this problem operates in a high-dimensional state space $(S, \\tau, i)$, where $S$ represents the set of visited vertices, $\\tau$ denotes the elapsed time, and $i$ is the associated vertex. The size of the state-space graph is heavily influenced by $S$ as it is typically encoded as a binary vector of length $|V|$. Therefore, we employ the ng-route relaxation technique [5] to relax the state space onto a lower-dimensional space $(\\Pi(P), \\tau, i)$ where $\\Pi(P)$ can be encoded as a binary vector of length $|N_i| (|N_i|\\leq |V|)$. The detailed procedure is explained in Section 3 and Appendix A. The proposed learning model approximates the ng-set $N_i$ for each vertex $i$, enabling the DP algorithm to operate in a customized state space and efficiently find the optimal solution.\n\n**2. The learning model.**\n\nThis work does not aim to introduce a sophisticated GCN model designed for general-purpose learning on directed graphs. Instead, we adopt a learning model that is sufficient for the prediction tasks required by our framework. Specifically, we select the Residual Gated GCN, a simple, scalable, and well-studied architecture. It has demonstrated competitive performance on the Traveling Salesman Problem (TSP) [6], which shares structural similarities with the OPTW. We adapt this model to a directed version to suit our prediction tasks, and the resulting performance remains competitive when compared to the state-of-the-art exact algorithm.\n\nIn preliminary experiments, we also evaluated more advanced architectures, such as Transformer-based models implemented with the PyTorch Geometric library. However, they exhibited poor performance in our setting, likely due to the need for further adaptations.  While we acknowledge that there may exist more suitable and well-developed learning models for our task, a comprehensive exploration of such models is beyond the scope of this work.\n\n**3. Conclusion.**\n\nIn summary, we present a novel paradigm that integrates DP with modern ML techniques for solving COPs. The numerical results demonstrate the effectiveness and superiority of the proposed learning-based enhancements. This learning approach can be generalized to other COPs by using DP with problem-specific state space relaxation. We believe that this work will serve as a valuable starting point to advance the deep integration between operations research and artificial intelligence.\n\n**Reference**\n\n[1] L. Scavuzzo, K. Aardal, A. Lodi, and N. Yorke-Smith. Machine learning augmented branch and bound for mixed integer linear programming. Mathematical Programming, 2024.\n\n[2] N. Christofides, A. Mingozzi, and P. Toth. State-space relaxation procedures for the computation of bounds to routing problems. Networks, 11(2):145–164, 1981.\n\n[3] N. Boland, J. Dethridge, and I. Dumitrescu. Accelerated label setting algorithms for the elementary resource constrained shortest path problem. Operations Research Letters, 34(1):58–68, 2006.\n\n[4] G. Righini and M. Salani. Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming. Computers & Operations Research, 36(4):1191–1203, 2009.\n\n[5] R. Baldacci, A. Mingozzi, and R. Roberti. New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem. Operations Research, 59(5):1269–1283, 2011.\n\n[6]  C. K. Joshi, T. Laurent, and X. Bresson. An efficient graph convolutional network technique for the travelling salesman problem, 2019."}, {"review_id": "pUI7XiK0He", "reviewer": "Reviewer_Ax3s", "summary": "This paper introduces a learning-augmented exact algorithm, DP-NG-ML, to solve the NP-hard Orienteering Problem with Time Windows (OPTW), aiming to maximize collected scores by visiting vertices within specified timeframes. Unlike traditional exact algorithms, this approach leverages a deep learning model called DiConvNet, a specialized graph convolutional network, to learn effective relaxations of problem restrictions from data. To enhance prediction accuracy, an initial edge reduction procedure is applied to tag and remove edges unlikely to be part of any \"ng-set\" before the data is fed into the DiConvNet model. DiConvNet predicts directed edges that define these relaxations, enabling significant performance gains in an exact dynamic programming algorithm. Experimental results show that this learning-augmented algorithm surpasses state-of-the-art exact algorithms, achieving a 38% speedup on Solomon's benchmark and a more than sevenfold improvement on Cordeau's benchmark, demonstrating its effectiveness in combining machine learning with operations research to preserve optimality while enhancing performance.", "questions": "- What is the specific methodology for edge reduction? Is this process machine learning-based, and if so, what approach is used? Additionally, is the same edge reduction technique applied consistently across all baseline methods to ensure fair comparison?\n\n- Has any sample complexity analysis been conducted to determine the minimum number of training instances required for effective model performance? Understanding the data requirements would provide valuable insights into the practical applicability of the approach.", "limitations": "- Add different and challenging problem classes to the analysis to make the contribution more significant. For example, consider incorporating problems such as vehicle routing with time windows, job shop scheduling, graph coloring, or maximum satisfiability problems.", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n\n1. The manuscript is well-written with excellent clarity and logical organization. \n\n2. The proposed methodology demonstrates strong potential for broader applicability beyond the specific problem class presented. This suggests the approach may have significant impact across multiple application areas, which is valuable for the broader research community. For example, there are many variants of TSPTW where this can be applied. \n\nWeaknesses\n\n1. Evaluation focuses on only one problem class, which is insufficient to establish the generalizability of the methodology, which seems to be the main contribution of the paper. The authors should test on additional problem domains such as vehicle routing, scheduling, or other combinatorial optimization problems.\n\n2. If exact methods solve instances in <11 seconds on average, the problems may be too trivial to demonstrate meaningful performance advantages. Similar to TSPTW where makespan/travel time objectives have different difficulty levels (I don't recall which one was more difficult), the authors should modify the objective function or constraints to create more challenging instances.\n\n3. The comparison should probably add a DiDPPy baseline [1], which has achieved state-of-the-art results on some DP problems. It has an easy to use Python package (https://didppy.readthedocs.io/en/stable/). \n\nReferences\n[1] Kuroiwa, Ryo, and J. Christopher Beck. \"Domain-independent dynamic programming: Generic state space search for combinatorial optimization.\" Proceedings of the International Conference on Automated Planning and Scheduling. Vol. 33. 2023.", "was_revised": true, "final_justification": "I have updated my score based on the newly added experimental results. First, the comparison to DIDPPy provides a nice baseline to one of the easy-to-use generic DP solver. Second, the comparison on larger/harder instances underscores the usefulness of such an approach. I would highly encourage adding these two results to the main text. Furthermore, I would advise the authors to add sample complexity results to the appendix. I would have preferred if the evaluation was done of two or more problem classes, nevertheless, I feel that the current contribution is impactful enough to be accepted at the conference.", "rebuttal": "We sincerely appreciate your thorough review and constructive feedback on our manuscript. Below, we address the identified weaknesses and respond to your questions.\n\n**1. Generalization to other problems.**\n\nIn general, most heuristics are more easily generalized to other optimization problems, as they do not rely on exact mathematical formulations. In contrast, efficient exact algorithms are often tailored to problem-specific characteristics, making them difficult to generalize to problems with different structures. Striking a balance between the efficiency of finding optimal solutions and the generalizability remains a significant challenge. Commercial solvers like Gurobi use generic branch-and-cut to solve various MIPs, but often overlook problem structures, making them less competitive than SOTA algorithms.\n\nThis work aims to develop an efficient exact algorithm for the OPTW that surpasses a highly competitive SOTA exact method, rather than a generic yet suboptimal solver. The core of this approach is the relaxation of elementarity constraints, which is problem-specific and hard to generalize across COPs. The OPTW can be reformulated as the Resource Constrained Elementary Shortest Path Problem (RCESPP) [1], where the objective is to find an elementary path minimizing the total collected weights on vertices or edges. We compare the TSPTW with the RCESPP to further illustrate this point.\n\nWe formulate the RCESPP with DP recursion. Let $F(S, \\tau, i)$ denote the minimum cost of a path that starts from the depot and ends at vertex $i$, visiting each vertex in set $S$ exactly once, with an elapsed time $\\tau$. $F(S, t, i)$ can be computed by solving the recurrence equation:\n\n\\begin{equation}F(S, \\tau, i) = \\min_{(j,i)\\in E}\\\\{F_i(S\\setminus \\\\{i\\\\}, \\tau^{\\prime}, j) + c_{ji} | \\tau+t_{ji}\\leq w_i^2, w_j^1 \\leq \\tau^{\\prime}\\leq w_j^2\\\\}, \\forall i\\in V, S\\subseteq V,   w_i^1 \\leq \\tau \\leq w_i^2.  \\quad \\(1\\)\\end{equation}\n\nThe set $S$ denotes the visited vertices, encoded as a binary vector of length $|V|$. $c_{ji}$ denotes the weight associated with the edge $e_{ji}$. The relaxation on elementarity restrictions reduces the state $(S, \\tau, i)$ to a lower-dimensional state $(\\Pi(P), \\tau, i)$, where $\\Pi(P)$ encoded as a binary vector of length $|N_i|\\ll|V|$. The TSPTW shares the same state space $(S, \\tau, i)$. However, their dominance rules are different: if state $(S, \\tau, i)$ dominates another state $(S^\\prime, \\tau\\prime, i)$, the TSPTW requires $S=S^{\\prime}$, whereas the RCESPP is $S\\subseteq S^{\\prime}$. This is because RCESPP does not require visiting all vertices. Moreover, the edge weights in RCESPP are not restricted to distances and can even take negative values. Relaxing the elementarity restrictions in the TSPTW results only in self-loops at the depot or back-and-forth trips, which are neither feasible nor help tighten the relaxation. Therefore, our approach is not applicable to the TSPTW or the VRPTW.\n\nNevertheless, based on a similar formulation, our algorithm can be readily extended to the generic Orienteering Problem [2] and the Capacitated Orienteering Problem (COP) [3]. However, the relaxation of elementarity constraints may be less effective for capacity constraints. When an unvisited vertex is not reachable due to time window constraint, the DP algorithm treats it as if it were already visited, which relaxes the dominance condition $S\\subseteq S^{\\prime}$ [4]. Moreover, tight time windows prevent the DP algorithm from generating too many loops along the path, thereby requiring small size of ng-sets. \n\nIn conclusion, although the relaxation of elementarity restrictions is inherently problem-dependent, this work successfully demonstrates a novel paradigm that leverages learning-based prediction to alleviate the curse of dimensionality in dynamic programming. We believe that future researchers may develop alternative forms of state-space relaxation tailored to their specific problems and explore their integration with learning-based methods.\n\n**2. Test on difficult instances.** \n\nThe SOTA pulse algorithm [5] is highly competitive for solving the OPTW or RCESPP, achieving more than a 70-fold speedup over the previous SOTA approach on Cordeau’s benchmark instances. Both the proposed DP-NG and its learning-enhanced variant, DP-NG-ML, exhibit clear performance improvements over the pulse algorithm. To evaluate performance on harder instances, we generated 20 Cordeau's instances with 100 vertices and time windows twice as wide. The computational times in seconds are shown below. However, DP-NG-ML does not performs well using the model trained on instances with regular time window instances. We are generating new 50-vertex instances with wide windows to retrain the model. As labeling is time-consuming, especially for hard instances, we will release the results of DP-NG-ML once they are ready. \n\n| Instance| OptVal | SOTA-pulse | DP-NG   \\|| Instance| OptVal | SOTA-pulse | DP-NG    |\n|---------|--------|------------|---------|---------|--------|------------|----------|\n| 100_0   | 511    | 71.7  | 367.2    | 100_10  | 577    | 1022.0  | 1452.0  |\n| 100_1   | 485    | 19.2   | 161.3 | 100_11  | 538    | 10.3    | 92.1    |\n| 100_2   | 498    | 18.5  | 35.8    | 100_12  | 486    | 7.6     | 40.9    |\n| 100_3   | 482    | 13.6   | 13.5  | 100_13  | 482    | 46.5    | 66.8    |\n| 100_4   | 503    | 265.4  | 93.1   | 100_14  | 583    | 1031.1   | 97.2    |\n| 100_5   | 535    | 330.8  | 256.8  | 100_15  | 493    | 89.8    | 192.8   |\n| 100_6   | 516    | 8.1  | 11.7   | 100_16  | 462    | 6.9      | 10.9    |\n| 100_7   | 435    | 7.1   | 27.2   | 100_17  | 505    | 175.9    | 695.9   |\n| 100_8   | 495    | 24.2  | 148.3  | 100_18  | 488    | 2293.2   | 363.4   |\n| 100_9   | 460    | 4.7  | 13.4   | 100_19  | 463    | 31.5     | 38.3    |\n| Mean    |        |         |         |         |        | 273.9     | 208.9   |\n\n**3. Comparison with DiDPPy**\n\nWe tested the DiDPPy solver on the OPTW using Cordeau instances. For a fair comparison, we added forced transitions that treat unvisited vertices as visited if they are infeasible due to time window constraints at the current state. In this case, more unpromising states will be pruned. Unfortunately, instances with more than 90 vertices ran out of memory. We select the first 90 vertices (excluding the depot) from each instance to create new instances. The computational time in seconds are shown below. The number of vertices is indicated in the name. The DP-NG is 100 times faster than the DiDPPy using the CABS solver. With the learning method integrated, the speedup reaches up to 800 times.\n\n| Instance | OptVal | DiDPPy  | DP-NG  | Speedup1 | DP-NG-ML | Speedup2 |\n|----------|--------|---------|--------|----------|----------|----------|\n| pr01_48  | 308    | 3.094   | 0.233  | 13.29    | 0.079    | 38.93    |\n| pr02_90  | 392    | 148.266 | 0.882  | 168.03   | 0.139    | 1065.18  |\n| pr03_90  | 331    | 51.841  | 0.782  | 66.29    | 0.231    | 224.82   |\n| pr04_90  | 356    | 33.328  | 0.674  | 49.43    | 0.169    | 197.45   |\n| pr05_90  | 443    | 193.404 | 1.386  | 139.54   | 0.551    | 350.70   |\n| pr06_90  | 329    | 29.954  | 0.527  | 56.85    | 0.046    | 656.43   |\n| pr07_72  | 298    | 12.956  | 0.187  | 69.14    | 0.016    | 810.99   |\n| pr08_90  | 374    | 19.59   | 0.397  | 49.30    | 0.034    | 568.74   |\n| pr09_90  | 320    | 100.259 | 0.346  | 289.93   | 0.057    | 1757.46  |\n| pr10_90  | 399    | 169.158 | 0.862  | 196.35   | 0.069    | 2465.47  |\n| Mean     |        | 76.185  | 0.628  | 109.81   | 0.139    | 813.62   |\n\n**4. The edge reduction procedure**\n\nThe explanation of this procedure was placed in Appendix B.1. We will move it to the main text in the next revision.\n_\"To improve prediction accuracy, we propose an edge reduction procedure that leverages problem-specific characteristics to exclude edges that cannot belong to ng-sets. Two types of edges are excluded: (1) the edges connected to the depot or self-loops; (2) any edge $e\\_{ij}$ satisfying the following condition:_\n\\begin{equation}\n\\max \\\\{w_j^1 + d_j + t_{ji}, w_i^1\\\\} + d_i + t_{ij} > w_j^2.   \\quad \\(2\\) \n\\end{equation}\n_The first type of edges is excluded by definition, while the second type corresponds to a situation where cycle $(j-i-j)$ is infeasible due to the time window constraints.\"_\n\nThis is a preprocessing procedure that does not involve learning. Since the other methods do not include ng-set prediction, this step is not required for them.\n\n**5. Sample complexity analysis**\n\nWe appreciate the reviewer’s insightful comment. While we have not performed a formal sample complexity analysis, our empirical experience suggests that around 10,000 training instances typically yield satisfactory predictive accuracy, with more data further improving performance. We will conduct additional experiments and include the results in the appendix of the revised version.\n\n**Reference**\n\n[1] G. Righini and M. Salani. Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming. Computers & Operations Research, 36(4):1191–1203, 2009.\n\n[2] M. Fischetti, J. J. S. Gonz´alez, and P. Toth. Solving the orienteering problem through branch-and-cut. INFORMS Journal on Computing, 10(2):133–148, 1998.\n\n[3] A. Bock and L. Sanit`a. The capacitated orienteering problem. Discrete Applied Mathematics, 195:31–42, 2015.\n\n[4] D. Feillet, P. Dejax, M. Gendreau, and C. Gueguen. An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems. Networks, 44(3):216–229, Oct. 2004.\n\n[5] D. Duque, L. Lozano, and A. L. Medaglia. Solving the Orienteering Problem with Time Windows via the Pulse Framework. Computers & Operations Research, 54:168–176, 2015."}, {"review_id": "ChjnAynZlM", "reviewer": "Reviewer_AJaq", "summary": "The paper studies the problem of solving NP-hard combinatorial optimization problem using machine-learned algorithms. Specifically, it considers the Orienteering Problem with Time Windows, which is essentially a variant of prize-collecting TSP equipped with time windows. The authors chose this problem to demonstrate the power of their approach compared to previously studied learning-augmented algorithms for combinatorial optimization problems with less dimensions, such as plain TSP. Problems with that many constraints and dimension have not been studied much before using such techniques.\nThe main contributions can be summarized as follows:\n\n- The authors present a first approach to integrate a graph neural network with an exact dynamic programming solver for combinatorial optimization problems, accelerating exact optimization without sacrificing optimality.\n\n- They demonstrate substantial speedups (up to 7x on challenging benchmarks) over the state-of-the-art pulse algorithm on standard OPTW instances, which highlights both efficiency gains and practical applicability of their approach.", "questions": "Have you considered different learning techniques that do not rely on supervised learning?", "limitations": "As far as I can see, the authors have addressed major limitations.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "### Strengths\n\n- The authors combine learning with an exact DP method, which has several benefits. I think this is relatively rare and an important contribution to ML for combinatorial optimization.\n\n- The authors tackle quite complex combinatorial optimization problems\n\n- The empirical results look impressive, with quite strong speedups over previous work and on competitive benchmarks.\n\n- The methodology seems to be generalizable and extendable to other combinatorial optmization problems.\n\n### Weaknesses\n\n- The method is based on supervised learning, and thus, requires labels of optimal solutions for instances. This is a significant limitation, as larger instances cannot be included in the learning process.", "was_revised": true, "final_justification": "The authors cleared out some of my concerns regarding the applicability of their result. Since I am not an expert, some doubts still remain. Hence, I would like to keep my overall positive impression. However, I feel not confident enough to strongly support the papers acceptance.", "rebuttal": "Thanks for your valuable comments and suggestions. We understand the limitations of supervised learning; however, due to the problem-specific characteristics, it remains a suitable and effective choice in our context. \n\n**1. Brief review of the proposed method.**\n\nTo better explain the reasons, we rewrite the dynamic programming formulation of the OPTW as follows.\n\n_Let $F(S, \\tau, i)$ denote the maximum collected score of the path a path starts from the depot and ends at vertex $i$, visiting each vertex in set $S$ exactly once, with an elapsed time of $\\tau$. $F(S, \\tau, i)$ can be computed by solving the recurrence equation_\n\\begin{equation}F(S, \\tau, i) = \\max_{(j,i)\\in E}\\\\{F_i(S\\setminus \\\\{i\\\\}, \\tau^{\\prime}, j) + s_j | \\tau+t_{ji}\\leq w_i^2, w_j^1 \\leq \\tau^{\\prime}\\leq w_j^2\\\\}, \\forall i\\in V, S\\subseteq V,   w_i^1 \\leq \\tau \\leq w_i^2.  \\quad \\(1\\)\\end{equation}\n_Set $S$ denotes the set of visited vertices and can be interpreted as a set of dummy resources, each with a unit capacity. This set is typically encoded as a binary vector of length $|V|$. Clearly, the size of the state-space graph is heavily influenced by this vector which enforces the elementarity restrictions over all the vertices in $V$._\n   \n_For each vertex $i \\in V$, we define an ng-set $N_i \\subseteq V$,  which is a selected subset of vertices associated with vertex $i$ (according to some criterion). Let $P=\\\\{0,i_1,...,i_p\\\\}$ be a partial path starting from the depot to vertex $i_p$, which is associated with the set of visited vertices $\\mathcal{S}(P)$ and an elapsed time $\\tau$. We define $\\Pi(P) \\subseteq \\mathcal{S}(P)$ as the ``memory'' of path $P$. During the past extension of path $P$, for any intermediate vertex $i_k$, only the visited vertices that belong to the ng-set of $i_k$ can be retained in memory. Therefore, the memory set $\\Pi(P)$ is defined as the intersection of the visited vertices and the ng-sets of all subsequently visited vertices, and is given by:_\n\\begin{equation}\n\t\\Pi(P)=\\\\{i_k\\in \\mathcal{S}(P)\\setminus \\\\{i_{p}\\\\}:i_k\\in \\cap_{q=k+1}^{p} N_{i_q}\\\\}\\cup \\\\{i_{p}\\\\}.   \\quad \\(2\\) \n\\end{equation}\n_In this way, the original state $(\\mathcal{S}(P), \\tau, i)$ of path $P$ is projected onto a lower-dimensional state $(\\Pi(P), \\tau, i)$, where $\\Pi(P)$ can be encoded as a binary vector of length $|N_i|$. Since $|N_i|\\leq |V|$ for each vertex $i$, the size of the state-space graph is significantly reduced. The main drawback of such relaxation technique is that some original state corresponding to an infeasible solution may be projected onto a state corresponding to a feasible solution in the lower-dimensional space. As a result, the search in the relaxed state space does not guarantee to find optimal solution. A practical compromise is to iteratively tighten the relaxation, i.e., enlarge the ng-sets, based on the optimal non-elementary path obtained in each iteration of DP, until an optimal elementary path is eventually found._\n\nThe central idea of this work is to train a neural network that approximates the projection function, mapping the original state space to a suitable lower-dimensional space. This enables dynamic programming to operate in a reduced state space while preserving optimality. \n\n**2. Difficulties of implementing unsupervised learning.**\n\nWe have attempted to implement such an approximation using unsupervised learning framework such as reinforcement learning. However, the main challenge lies in evaluating the quality of states and actions.\n\nExisting research on solving combinatorial optimization problems (COPs) using machine learning primarily focuses on constructing solutions incrementally or directly searching for solutions based on probabilistic heatmaps. It is straightforward to evaluate the quality of any states (incumbent solution) or actions (an local movement) based on the given objective function. However, in our case, the goal is not to approximate a feasible solution to the OPTW. Instead, we aim to predict the smallest possible ng-set for each vertex such that a single run of the DP-NG algorithm can compute the optimal elementary path under the given ng-sets. Consequently, there are two challenges to implement an unsupervised learning:\n\n**First**, the delayed reward of predicting any edges in ng-sets, i.e. the size of final ng-sets, are only revealed once the optimal solution of DP-NG algorithm is elementary. This procedure often requires many steps of prediction, as well as many iterations of the DP-NG. No immediate reward signals are available when selecting a directed edge. Moreover, each run of the DP-NG to confirm the status of ng-sets is essentially equivalent to solving an NP-hard problem, despite the reduced dimensionality of the state space. According to the work of Boland et al. [1], the worst-case complexity of the basic DP algorithm without relaxation is $\\mathcal{O}(|E| (T_{max} + 1)2^{|V|})$. Similarly, the worst-case complexity of te DP-NG algorithm can be approximated as $\\mathcal{O}(|E| (T_{max} + 1)2^{|\\bar{N}|})$, where $|\\bar{N}|$ denotes an averaged size of the ng-sets across all vertices. \n\n**Second**, the final ng-sets are obtained by iteratively tighten the relaxation based on the computed optimal non-elementary paths. Specifically, when a non-elementary path is computed, for each loop that appears in the path, the duplicate vertex is inserted into the ng-sets of the vertices involved in that loop. In this way, the same loops are prevented in the next iteration of the DP-NG algorithm, based on the extension method described in Section 3.2. The inclusion of other candidate directed edges into the ng-sets does not affect the optimal non-elementary path. If an auto-regressive learning approach is adopted, many of the trials may be incorrect, and no direct feedback signals are available. Moreover, it requires running the DP-NG algorithm at each step to evaluate whether the optimal path has changed and to determine whether the prediction process should terminate. More importantly, the cost of trial-and-error is prohibitively high, as the computational complexity of the DP-NG algorithm grows exponentially with the size of the ng-sets.\n\n**3. Efforts in supervised learning.**\n\nFor the above reasons, collecting a large amount of exploratory data with reward signals is extremely time-consuming. Compared to unsupervised learning, supervised learning typically requires a smaller amount of (high-quality) training data. Moreover, initializing the ng-sets to reduce the number of DP-NG iterations is inherently a one-shot process, which naturally aligns with the supervised learning paradigm.\n\nTo efficiently obtain a large number of labeled samples, we enhanced the DP-NG algorithm by reusing non-dominated labels from the previous iterations. To ensure optimality, a minor modification to the original DP-NG algorithm is necessary, although we omit the formal proof in this paper. The source code of the improved DP-NG algorithm will be made publicly available after submission. The computational time (in seconds) on Cordeau benchmark instances are provide as follows:\n\n| Instance | SOTA pulse | original DP-NG | imporved DP-NG |\n|----------|------------|----------------|----------------|\n| pr01     | 0.047      | 0.237          | 0.206          |\n| pr02     | 0.376      | 1.059          | 0.981          |\n| pr03     | 0.706      | 3.424          | 1.815          |\n| pr04     | 1.285      | 7.122          | 4.866          |\n| pr05     | 18.857     | 29.005         | 13.925         |\n| pr06     | 31.883     | 30.129         | 14.262         |\n| pr07     | 0.078      | 0.203          | 0.138          |\n| pr08     | 0.517      | 1.833          | 1.007          |\n| pr09     | 33.514     | 26.698         | 15.620         |\n| pr10     | 23.802     | 30.446         | 15.680         |\n| Mean     | 11.107     | 13.016         | 6.850          |\n\nThe improved DP-NG algorithm runs twice as fast as the original version and even outperforms the state-of-the-art Pulse algorithm on these instances.\n\n**4. Positioning of this Work**\n\nThe main contribution of this work is to improve an exact algorithm with machine learning technique for an NP-hard COP. We successfully demonstrates a novel paradigm that approximates the state space relaxation to enable dynamic programming to operate in a lower-dimensional state space. This method shows great potential for generalization to a broad class of network optimization problems, as many of these problems can be formulated using dynamic programming recursions.\n\n**Reference**\n\n[1] N. Boland, J. Dethridge, and I. Dumitrescu. Accelerated label setting algorithms for the elementary resource constrained shortest path problem. Operations Research Letters, 34(1):58–68, 2006."}, {"review_id": "AksgXoqF1r", "reviewer": "Reviewer_7zHH", "summary": "The paper presents a learning-augmented exact algorithm for the Orienteering Problem with Time Windows (OPTW) which is a combinatorial optimization problem (COP). The authors first reduce the number of likely edges in the ng-set from all the possible edges, then use a Graph Convolutional Network (GCN) to estimate the probability that each remaining edge is in the ng-set. The edges with the highest probabilities are then selected to initialize the ng-set and the DP-NG algorithm is used to compute the exact optimal solution. The authors test their algorithm empirically and show that it produces better ng-set initializations than a ConvNet and some heuristics. On OPTW benchmarks their algorithm produces significant speed-ups when compared to the current SOTA pulse algorithm.", "questions": "- Sections 3.2 and 3.3 should be rewritten to better explain the proposed algorithm (see weaknesses). This would greatly help readers which are less familiar with the underlying concepts understand the proposed algorithm without needing to refer to external ressources.\n- The edge reduction part should be briefly described in the text. When that part is introduced at the beginning of Section 4.1, the authors reference the appendix without further explanations but later in the main text they mention concepts presented in the appendix.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "### Strengths\n- The presented algorithm is innovative and performs strongly on benchmarks.\n- The paper is generally well written except for sections 3.1 and 3.2 (see weaknesses).\n- The figures significantly help understanding the proposed method.\n\n### Weaknesses\n- While I think the paper is generally well written, Section 3.2 is somewhat confusing. I was only able to properly grasp the explained concepts using outside ressources. I think that section should be re-written and that Appendix A.1 should be incorporated into the main text since the math there helps understand things. More generally the interaction between the DP algorithm and the ng-route relaxation should be better explained; when talking about \"extending a path P\" the authors give the impression that the path is built vertex by vertex with the ng-set updated after every new addition. However in Figure 2 it is clearly shown that at every iteration of the DP-NG algorithm a full \"optimal path\" is proposed and the ng-set is then updated. Perhaps a part of this confusion is a result of my relative unfamiliarity with the exact concepts of interest, but the text and explanations should still be improved and made clearer so that the proposed solution is easier to understand. The figures help in this regard so perhaps a better alignment between the text and the figures would be useful.", "was_revised": true, "final_justification": "After reading the other reviews and the authors’ rebuttal, I’ve decided to keep my score at 5 (Accept). Although the authors addressed my main concerns, I’m not comfortable raising to a 6 given the additional issues noted by other reviewers and my lingering uncertainty about how this work fits into the existing literature and state of the art.", "rebuttal": "We sincerely appreciate your thorough review and valuable comments. We have re-evaluated the text in Section 3 and will revise it accordingly. In addition, a brief introduction to the ``edge reduction'' will be included in Section 4. We summarize the modifications in the following four parts and review our contributions:\n\n**1. Dynamic programming formulation**\n\nWe will revise the last paragraph of Section 3.1 as follows, providing a clearer explanation of the dynamic programming formulation.\n\n_\"The OPTW can be formulated as a special case of the classic Resource constrained Elementary Shortest Path Problem [1], for which no polynomial-time algorithm is known. Dynamic programming is considered an efficient exact approach for solving this problem. Let $F(S, \\tau, i)$ denote the maximum collected score of a path starts from the depot and ends at vertex $i$, visiting each vertex in set $S$ exactly once, with an elapsed time of $\\tau$. $F(S, \\tau, i)$ can be computed by solving the recurrence equation:_\n\n\\begin{equation}F(S, \\tau, i) = \\max_{(j,i)\\in E}\\\\{F_i(S\\setminus \\\\{i\\\\}, \\tau^{\\prime}, j) + s_j | \\tau+t_{ji}\\leq w_i^2, w_j^1 \\leq \\tau^{\\prime}\\leq w_j^2\\\\}, \\forall i\\in V, S\\subseteq V,   w_i^1 \\leq \\tau \\leq w_i^2.  \\quad \\(1\\)\\end{equation}\n\n _Set $S$ denotes the set of visited vertices and can be interpreted as a set of dummy resources, each with a unit capacity. This set is typically encoded as a binary vector of length $|V|$. Clearly, the size of the state-space graph is heavily influenced by this vector which enforces the elementarity restrictions over all the vertices in $V$.To reduce the number of states to be explored, we employ the ng-route relaxation technique Baldacci et al. [2] to project the original state space $(S, \\tau, i)$ onto a lower-dimensional space, inspired by the state space relaxation procedure proposed by Christofides et al. [3] and developed by  Boland et al. [4], Righini and Salani [1].\"_\n\n**2. Clearer explanation of ng-route relaxation**\n\nWe rephrase the entire Section 3.2 to better clarify the concept of ng-route relaxation as follows:\n\n_\"The ng-route relaxation, introduced by  Baldacci et al. [2], provides a good compromise between enforcing elementarity constraints and enabling efficient exploration of the state space. For each vertex $i \\in V$, we define an ng-set $N_i  \\subseteq V$,  which is a selected subset of vertices associated with vertex $i$ (according to some criterion). Let $P=\\\\{0,i_1,...,i_p\\\\}$ be a partial path starting from the depot to vertex $i_p$, which is associated with the set of visited vertices $\\mathcal{S}(P)$ and an elapsed time $\\tau$. The basic DP algorithm explores the state space by extending paths to all possible succeeding vertices using equation (1). We define $\\Pi(P) \\subseteq \\mathcal{S}(P)$ as the `memory' of path $P$. During the past extension of path $P$, for any intermediate vertex $i_k$, only the visited vertices that belong to the ng-set of $i_k$ can be retained in memory. Therefore, the memory set $\\Pi(P)$ is defined as the intersection of the visited vertices and the ng-sets of all subsequently visited vertices, and is given by:_ \n\\begin{equation}\n\t\\Pi(P)=\\\\{i_k\\in \\mathcal{S}(P)\\setminus \\\\{i_{p}\\\\}:i_k\\in \\cap_{q=k+1}^{p} N_{i_q}\\\\}\\cup \\\\{i_{p}\\\\}.   \\quad \\(2\\) \n\\end{equation}\n_In this way, the original state $(\\mathcal{S}(P), \\tau, i)$ of path $P$ is projected onto a lower-dimensional state $(\\Pi(P), \\tau, i)$, where $\\Pi(P)$ can be encoded as a binary vector of length $|N_i|$. Since $|N_i|\\leq |V|$ for each vertex $i$, the size of the state-space graph is significantly reduced. Figure 1 illustrates the path extension using given ng-sets. Note that if a visited vertex is excluded from the memory of path $P$, it may be revisited in the future extensions of $P$. This is the main drawback of the relaxation technique. As a result, the search in the relaxed state space does not guarantee to find optimal solution. A practical compromise is to iteratively tighten the relaxation, i.e., enlarge the ng-sets, based on the optimal non-elementary path obtained in each iteration of DP, until an optimal elementary path is found._\n\n_Note that this iterative framework may incur higher computational costs compared to the basic DP algorithm, as the dimensionality of the state space increases with each iteration. An inappropriate criterion for expanding the ng-sets may introduce `unnecessary' vertices, further inflating the search space. We demonstrate that this issue can be mitigated by leveraging machine learning techniques to predict the ng-sets based on hidden patterns extracted from data. Moreover, the data-driven approach serves as an effective heuristic to initialize the ng-sets, thereby reducing the number of required iterations. Essentially, our goal is to train a neural network that approximates the projection function, mapping the original state space to a suitable lower-dimension space in a one-shot manner. In this case, the ng-set of vertex $i$ can be viewed as a set of directed edges originating from $i$.\"_\n\n**3. A concise version of DP with ng-route relaxation**\n   \nWe move part of the content from Section 3.3 to Section 3.2, and rephrase this Section accordingly:\n\n_\"A state of path $P$ can be interpreted as a label $L(P)=(i,\\tau(P),s(P),\\Pi(P))$, where $i$ is the last visited vertex and $s(P)$ is the collected score. Extending label $L(P)$ to vertex $j$ indicates adding $j$ to the end of $P$, thereby generating a new label. This extension is feasible only if the time window constraint at $j$ is satisfied and $j$ has not been visited by path $P$, i.e., $j \\notin \\Pi(P)$. To limit the exponential growth in the number of labels, a dominance test is applied to identify and discard labels that cannot lead to an optimal solution. By exploring the state space defined by the current ng-sets, the path with the highest scores is considered the optimal path for that iteration. If the obtained path is non-elementary, the vertices involved in a cycle is updated to include the duplicate vertex, thereby preventing the same cycle from occurring in the next iteration. This exact approach is referred to as the DP-NG algorithm, and a detailed explanation is provided in Appendix A.2. Figure 2 illustrates an example of the DP-NG algorithm applied to a seven-vertex instance. It can be expected that states with lower time consumption and higher collected scores are more likely to survive the dominance test. Consequently, pairs of vertices with high individual scores, lose spatial proximity and highly overleaped time windows are more likely to form cycles. This observation motivates the use of graph structural features for predicting the ng-sets.\"_\n\n**4. The content of edge reduction procedure**\n\nWe move the content of the edge reduction procedure from  Appendix B.1 to the main text, and rephrase it as follows:\n\n_\"To improve prediction accuracy, we propose an edge reduction procedure that leverages problem-specific characteristics to exclude edges that cannot belong to ng-sets. Two types of edges are excluded: (1) the edges connected to the depot or self-loops; (2) any edge $e\\_{ij}$ satisfying the following condition:_\n\n\\begin{equation}\n\\max \\\\{w_j^1 + d_j + t_{ji}, w_i^1\\\\} + d_i + t_{ij} > w_j^2.   \\quad \\(3\\) \n\\end{equation}\n_The first type of edges is excluded by definition, while the second type corresponds to a situation where cycle $(j-i-j)$ is infeasible due to the time window constraints.\"_\n\n**5. Review of our contributions**\n\nWe sincerely appreciate the constructive suggestion on reorganizing the content of Section 3. This provides a valuable opportunity for us to reflect more deeply on the innovations of our methodology and its potential contributions to both the OR and AI communities.\n\nIn essence, our work successfully demonstrates a novel paradigm that integrates machine learning (ML) technique with dynamic programming for solving combinatorial optimization problems (COPs), particularly in the context of network optimization. A variety of such NP-hard problems can be solved using dynamic programming, but the approach often suffers from the 'curse of dimensionality'. Approximating the state-space relaxation with ML enables dynamic programming to operate in a lower-dimensional state space, rather than the original one, while preserving optimality. In our case, we focus on the elementarity restrictions over all the vertices in $V$, which correspond to $|V|$ state variables in dynamic programming recursion. With accuracy prediction of the state space relaxation, the number of state variables can be reduced to $|N_i|$, where $N_i \\subseteq V$.\n\nAccording to the recent survey on ML for COPs by Bengio et al. [5], no prior research has presented a similar paradigm. We believe that this work serves as a valuable starting point and demonstrates the potential of our approach to be generalized to other network optimization problems.\n\n**Reference**\n\n[1] G. Righini and M. Salani. Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming. Computers & Operations Research, 36(4):1191–1203, 2009.\n\n[2] R. Baldacci, A. Mingozzi, and R. Roberti. New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem. Operations Research, 59(5):1269–1283, 2011.\n\n[3] N. Christofides, A. Mingozzi, and P. Toth. State-space relaxation procedures for the computation of bounds to routing problems. Networks, 11(2):145–164.\n\n[4] N. Boland, J. Dethridge, and I. Dumitrescu. Accelerated label setting algorithms for the elementary resource constrained shortest path problem. Operations Research Letters, 34(1):58–68, Jan. 2006.\n\n[5] Y. Bengio, A. Lodi, and A. Prouvost. Machine learning for combinatorial optimization: A methodological tour d’horizon. European Journal of Operational Research, 290(2):405–421, 2021."}]

Author rebuttal:

Meta-review: The paper augments a dynamic programming formulation for the Orienteering Problem with Time Windows by edge selection for a combinatorial structure (ng-sets) that is used in the DP base algorithm. Reviewers acknowledge that the paper is well written and that the improvements are significant. On the other hand, methodological contribution is criticized as well as practical relevance, since the method was evaluated on a very specific problem formulation only, hence generalization to other problems is open, and additionally all instances can be solved quickly with established classical algorithms. Also, as another disadvantage, the method is supervised, hence ground truth labels must be computed first.
The rebuttal has addressed partially the issue of generalizability to other problems. On the topic of relevance, it is positively noted that the machine learning component is embedded in an exact algorithm, hence not sacrificing solution quality for faster runtime and making it an overall elegant approach. As such, even though reviewers have mixed feelings and there remained some disagreement, the paper merits acceptance at NeurIPS.
Decision: Accept (poster)