# Learning to repeatedly solve routing problems

Mouad Morabit  MAGI, Polytechnique Montréal, Canada  GERAD, Montréal, Canada
CERC, Polytechnique Montréal, Canada  Guy Desaulniers  MAGI, Polytechnique
Montréal, Canada  GERAD, Montréal, Canada  Andrea Lodi  CERC, Polytechnique
Montréal, Canada  Jacobs Technion-Cornell Institute
Cornell Tech, USA

###### Abstract

In the last years, there has been a great interest in machine-learning-based
heuristics for solving NP-hard combinatorial optimization problems. The
developed methods have shown potential on many optimization problems. In this
paper, we present a learned heuristic for the reoptimization of a problem
after a minor change in its data. We focus on the case of the capacited
vehicle routing problem with static clients (i.e., same client locations) and
changed demands. Given the edges of an original solution, the goal is to
predict and fix the ones that have a high chance of remaining in an optimal
solution after a change of client demands. This partial prediction of the
solution reduces the complexity of the problem and speeds up its resolution,
while yielding a good quality solution. The proposed approach resulted in
solutions with an optimality gap ranging from 0% to 1.7% on different
benchmark instances within a reasonable computing time.
Keywords : heuristics, reoptimization, machine learning.

##  1 Introduction

In the recent years, the idea of integrating machine learning (ML) and
combinatorial optimization (CO) has been greatly explored. CO problems are NP-
hard and there are generally two approaches to solve them. The exact methods
that are guaranteed to obtain an optimal solution but can be computationally
very expensive for large instances, and the heuristic methods that trade off
the optimality of the solution for a reasonable computing time. The idea of
leveraging ML for the development of new heuristics has shown potential in
many CO problems such as traveling salesman problem (TSP), capacited vehicle
routing problem (CVRP), etc. It is true that most of these learned heuristics
do not outperform highly optimized and specialized CO algorithms, especially
for problems that have been extensively studied in the literature.
Nevertheless, the ideas behind them provide a certain flexibility for
adjustments and applications to other problems for which no good heuristic
exists, or they can be integrated in already existing algorithms to speed them
up.

In this paper, we focus on CO applications in which a problem is repeatedly
solved, e.g., daily or hourly, or even within a shorter interval, by changing
neither its structure (e.g., its constraints) nor even its size (i.e., its
variables), but only the data that define each instance solved in the specific
time interval. This is the case of applications in which the infrastructure
whose operations must be optimized does not change, for example a fleet of
vehicles that deliver goods or the power plants producing energy, but the
demand of goods or energy changes. And it is also the case of real-time
changes to the data due to disruptions in the infrastructure, for example arcs
disappearing from a network (i.e., their capacity going to 0) due to
accidents.

Applications of this type might be difficult to solve in reasonable amount of
time, or, more precisely, each instance in isolation might require a
significant computational effort even if the solution method has been designed
after intensively studying the characteristics of the CO problem. This is the
theoretical consequence of NP-hardness, and, on the practical side, it is due
to the fact that the solution methods are largely designed to be agnostic to
the data.

The goal of this paper is to propose a learned heuristic allowing a fast
reoptimization of a CO problem after a slight modification of its data. In
other words, we put ourselves in a way more restrictive context with respect
to the use of ML for CO problems: we do not want to leverage ML to devise a
heuristic that produces good feasible solutions for all, say, TSP instances
within the same distribution. We are settling for a lesser objective, i.e.,
that of learning what can be (more or less with high probability) safely left
unchanged in the solution of a reference instance of a CO problem when the
data of the instance are perturbed. Indeed, the intuition is that given an
instance and its solution $S_{1}$, if the instance is reoptimized after a
slight change in its data, the new solution $S_{2}$ will have a significant
overlap with $S_{1}$, while only some (minor) parts of the solutions will be
different. Therefore, instead of reoptimizing from scratch, the goal is to
predict the parts of the solution that have a high probability of remaining
the same. The corresponding variables can be fixed, thus reducing the search
space and accelerating the resolution of the problem, almost independently of
the solution method applied.

To provide a concrete example, let us consider the CVRP, which is the problem
where we will apply the method proposed in this paper. The goal of the CVRP is
to construct vehicle routes in order to serve geographically-dispersed clients
while minimizing the travel costs and respecting vehicle capacity. Let us take
the example of a delivery company that solves CVRPs on a daily basis. For a
given day, the company observes that the clients are the same as in the
instance solved the previous day (i.e., same client locations) and that only
some clients have a different demand. After the optimization of the problem, a
similarity between the solutions is noticed. Given the optimal solution (or a
heuristic one) already in hand and the new demands, the objective would be to
predict and fix the sequences of edges that have a high probability to remain
the same. In case of a graph-structured problem like the CVRP, it is also
possible to reduce the size of the network by aggregating the nodes/edges of
the fixed sequences, therefore accelerating the resolution of the problem and
reducing its complexity. Note that the predictions obtained by the learned
model are not necessarily 100% accurate, misclassifications may occur and thus
affect the quality of the solution. The goal is to find a good compromise
between the quality of the solution (i.e., optimality gap) and the computing
time.

As observed, one can think of several CO problems where slight modifications
to the problem data lead to similar solutions after reoptimization, especially
for problems that are solved repeatedly and for which a data set is already
available (e.g., the unit commitment problem in which the power plants
producing energy are always the same but the demand changes daily or hourly).
The learned model will try to partially predict an optimal solution. In this
paper, we will only consider the case of the CVRP with changing demands and
fixed customers, but the method offers some flexibility and has the potential
to be applied to other problems or to be integrated into existing algorithms.

The remainder of the paper is organized as follows. In Section 2, we present
some recent work on using ML for solving CO problems or accelerating their
solution process. Section 3 is devoted to presenting the CVRP, with a focus on
the methods we consider to solve it. In Section 4, we cover all the details of
the method we propose. Section 5 reports our computational results. Finally,
conclusions are drawn in Section 6.

##  2 Related work

In the literature, several heuristics incorporating ML models for solving NP-
hard CO problems were explored (see, the recent surveys Bengio et al. (2021);
Kotary et al. (2021); Cappart et al. (2021)). The proposed learning methods
mostly fall into one of two categories. In the first category, supervised
learning methods (examples of the imitation learning paradigm) are algorithms
that learn from data and try to mimic an expert. The data is given to the
learner as a pair of features and expected outputs (or labels) and the learner
tries to find patterns in the data while optimizing a performance measure.
Generally, the aim of this approach is to replace known expensive computations
by fast approximations (e.g., for our case, the expensive computation
corresponds to reoptimizing the problem from scratch). In the second category,
we find the reinforcement learning (RL) algorithms that apply a “learning-by-
experience” paradigm. Instead of giving the learner the data on which to
learn, RL algorithms explore the decision space by interacting with its
environment in order to achieve a certain goal. In response to a decision
(i.e., an action), the learner receives a real-valued reward. The goal is to
find the best decisions to make at each state while maximizing the expected
rewards. This learning approach has the advantage of not requiring any data
and has generally shown a better generalization, i.e., the ability of
continuing to be effective when the problems change for example in size or
even better in data distribution.

Several studies have tried to tackle the TSP, the most classical CO problem
where the goal is to visit a set of nodes exactly once with a single vehicle
while minimizing the travel distance. For the supervised approaches, we
mention the work of Joshi et al. (2019), where a learned heuristic method is
presented. The method is based on a graph convolutional network model that
takes the entire graph as an input and outputs an adjacency matrix with
associated edge probabilities, which are then used to build a valid tour using
a beam search algorithm. The authors report good results on fixed size
instances. However, a very poor generalization is noticed when testing the
models on instances of different size. Instead, the methods based on RL have
shown more potential. The idea of using RL to solve CO problems was explored
in Bello et al. (2016) with an application to the TSP and the knapsack
problem. Further studies were then conducted, such as Kool et al. (2018),
where the authors present an encoder-decoder model based on the attention
mechanism (Vaswani et al., 2017). In a similar line, Nazari et al. (2018)
present a framework focusing on solving the CVRP, which can be considered as a
generalization of the TSP for the case with multiple vehicles. The results
reported by the authors show a better performance when compared to the OR-
Tools solver and other heuristic algorithms. Other researchers contributed to
the methods for solving the broader class of graph-structured CO problems. Dai
et al. (2017) initiated the idea of learning on graphs, and the works of Li et
al. (2018) and Manchanda et al. (2019) enhanced further the scalability to
larger graphs. These methods have been applied to various NP-hard graph
problems such as the minimum vertex cover, maximum clique, influence
maximization problem, etc.

Unlike the previous works that seek to build an end-to-end solution to the
different problems, other methods focus on using ML to guide and accelerate
the solution process. Since we pay special attention to mixed-integer programs
(MIP), it is worth mentioning the various projects involving ML in the context
of branch and bound (Khalil et al., 2016; Alvarez et al., 2017; Gasse et al.,
2019; Zarpellon et al., 2020), many of which seek to learn a branching policy
imitating the strong branching strategy. Another potential use of ML is
embedding a learned model in MIP solvers in order to decide if a decomposition
of the problem is beneficial or not (Kruber et al., 2017), or if it is
favorable to linearize the quadratic part of a mixed-integer quadratic program
(Bonami et al., 2022).

Other learning-based methods have proven to be very effective on problems that
are solved repeatedly, especially when the input data changes only slightly,
which is the key idea of our project. These methods can exploit existing data
from previous solutions in order to speed up the resolution of similar unseen
instances. Xavier et al. (2021) exploit the idea and apply it on the security-
constrained unit commitment, a problem occuring in power systems and
electricity markets. The authors report high speedups on computing time, up to
10 times faster than solving the problem from scratch, and without a
noticeable loss in solution quality. Along the same lines, Lodi et al. (2020)
consider an application to the facility location problem. They seek to
estimate the proportion of a solution that has a high probability of remaining
unchanged after a perturbation. An additional constraint is added to the
original formulation according to the predictions obtained by a regression
model. Both Xavier et al. (2021) and Lodi et al. (2020) leverage ML for
speeding up the resolution of repeatedly solved problems and do not seek to
build an end-to-end solution, which is similar to our case. As opposed to
Xavier et al. (2021), our method is related to that of Lodi et al. (2020) in
the sense that both assume a reference solution to which changes
(perturbations) are applied. However, the main difference lies on the fact
that our approach revolves around fixing parts of the reference solution
(i.e., edges) instead of estimating a bound on the number of changes without
specifying which variables to set. Other than that, the CVRP remains a quite
different problem and the approaches developed in this paper have the
potential to be extended to other CVRP variants and also to other routing
problems.

##  3 The capacited vehicle routing problem

The CVRP is a CO problem that has been studied for many years, resulting in
several exact and heuristic methods to solve it. It is classified as an NP-
hard problem and remains a difficult problem to solve to optimality even with
just a few hundred clients. Given a fleet of vehicles assigned to a depot, the
problem consists in determining a set of possible routes (i.e., one route per
vehicle used) to deliver goods to a set of dispersed clients while minimizing
the travel costs. A route starts from the depot and visits a sequence of
clients before returning back, and is considered feasible if the total amount
of goods delivered does not exceed the vehicle capacity $Q$.

For solving this problem, we consider the algorithms based on column
generation (CG - Desaulniers et al. (2005)), which is an exact iterative
method for solving large linear programs. To ensure the obtention of integer
solutions, CG is often embedded in a branch-and-bound framework where the
linear relaxation of the problem is solved at each node using CG. In this case
the method is referred to as branch-and-price (B&P) and it is considered the
state-of-the-art exact method for solving the CVRP. But due to the complexity
of the problem, solving large instances to optimality can be computationally
expensive. Therefore, several heuristics have been proposed in the literature.

Note that our approach does not necessarily require learning from optimal
solutions. Since we want to apply it on instances of a reasonable size (i.e.,
100 clients and more), solving the instances to optimality in order to collect
data can be time consuming. Therefore, we chose to use a heuristic in the data
collection phase, but during the evaluation phase, we exploit an exact B&P
algorithm. In the next sections, we present the problem formulation along with
both the exact and the heuristic algorithms used.

###  3.1 CVRP formulation

In this section, we formulate the CVRP as a set partitioning problem. Let $C$
be the set of clients to be serviced, $\Omega$ the set of all feasible routes
and $c_{r}$ the cost of a route $r\in\Omega$. We define $a_{i}^{r}$ as a
binary parameter equal to $1$ if client $i\in C$ is serviced by route
$r\in\Omega$ and $0$ otherwise. Let $\theta_{r}$ be a binary decision variable
equal to $1$ if route $r$ is part of the solution and $0$ otherwise. The
problem can therefore be formulated as follows:

$\displaystyle(P)\hskip 14.22636pt\min_{\theta}\hskip
8.53581pt\sum_{r\in\Omega}c_{r}\theta_{r}$ (1) $\displaystyle\mbox{s.t.}\hskip
8.53581pt\sum_{r\in\Omega}a_{i}^{r}\theta_{r}=1$ $\displaystyle,\hskip
8.53581pt\forall i\in C,$ (2) $\displaystyle\theta_{r}\in\\{0,1\\}$
$\displaystyle,\hskip 8.53581pt\forall r\in\Omega,$ (3)

where the objective (1) minimizes the total cost of the routes. Constraints
(2) ensure that each client is visited exactly once and constraints (3) are
the binary requirements on the decision variables $\theta_{r}$.

One can notice that for large instances, the size of the route set $|\Omega|$
becomes prohibitively large and it would not be possible to enumerate all the
variables of the problem. This is why a CG-based algorithm is used. The goal
is to start with a subset of variables and generate potentially improving
columns when necessary.

###  3.2 Exact branch-and-price algorithm

B&P algorithms (Barnhart et al., 1996) are considered state-of-the-art exact
algorithms for solving a variety of optimization problems (e.g., routing,
scheduling, …). B&P is based on the branch-and-bound method in which the
linear relaxation at each node is solved using CG. The CG process is iterative
and consists in alternating between the resolution of a restricted version of
the original linear relaxation, called a restricted master problem (RMP), and
a pricing problem (PP). The goal of the PP is to find new improving columns of
negative reduced cost (for a minimization problem) that can be added to the
RMP. The CG process stops when no such columns are found. A branching then
occurs and the branch-and-bound tree exploration continues. Optionally,
cutting planes can also be added to strengthen the relaxation at each node,
resulting on what is called a branch-cut-and-price method.

####  3.2.1 The restricted master problem

The RMP corresponds to the linear relaxation of the formulation (1)-(3) but
limited to only a subset $\mathcal{R}\subset\Omega$ of the variables. It is
solved at each CG iteration, yielding a pair of primal and dual solutions
$(\theta,\pi)$. The dual values $(\pi_{i})_{i\in C}$ associated with the
constraints (2) are then used to find routes $r\in\Omega\backslash\mathcal{R}$
of negative reduced cost by solving the PP. If none exist, the CG process
stops and the solution to the current RMP is thus optimal for the whole linear
relaxation. Otherwise, the routes are added to the RMP (i.e., to the subset
$\mathcal{R}$) which is then reoptimized.

####  3.2.2 The pricing problem

The PP can be defined as $min_{r\in\Omega}\thickspace\\{c_{r}-\sum_{i\in
C}a_{i}^{r}\pi_{i}\\}$. For many applications, especially routing and
scheduling problems, this problem can be modeled as an elementary shortest
path problem with resource constraints (ESPPRC - Irnich and Desaulniers
(2005)) where the goal is to find the least cost path between the source and
destination nodes while visiting the nodes at most once (i.e., elementarity
requirements) and respecting the resource constraints. For the CVRP, the only
resource is the load, and a path is considered feasible if the load does not
exceed the vehicle capacity. This problem can be defined over a graph
$G=(V,A)$, where $V$ is the set of nodes representing the clients, in addition
to the depot nodes $s$ and $t$, i.e., the source and destination nodes,
respectively. The set $A$ represents the arcs, where each arc has an
associated cost $c_{ij},(i,j)\in A$. Hence, the cost of a path in $G$ is given
by the sum of the costs $c_{ij}$ of its arcs.

In order to take into account the dual values obtained by the RMP, at each
iteration and for each arc $(i,j)\in A$, a modified cost
$\bar{c}_{ij}=c_{ij}-\pi_{i}$ is used instead, where $\pi_{i}$ are the duals
associated with constraints (2) and $\pi_{s}=0$. This guarantees that the cost
of a feasible route in the network is equal to its reduced cost:

$\displaystyle\bar{c}_{r}=c_{r}-\sum_{i\in C}a_{i}^{r}\pi_{i}=\sum_{(i,j)\in
A}c_{ij}b_{ij}^{r}-\sum_{i\in C}a_{i}^{r}\pi_{i}=\sum_{(i,j)\in
A}(c_{ij}-\pi_{i})b_{ij}^{r}=\sum_{(i,j)\in V}\bar{c}_{ij}b_{ij}^{r}$ (4)

where $b_{ij}^{r}$ is equal to $1$ if arc $(i,j)\in A$ is traversed in route
$r\in\Omega$, $0$ otherwise.

The ESPPRC is an NP-hard problem, which is mainly due to the client
elementarity requirements since negative cost cycles can exist when using the
modified costs $\bar{c}_{ij}$. Relaxing this constraint (i.e., allowing the
generation of paths with cycles) leads to the SPPRC, which is an easier
problem that can be solved in pseudo-polynomial time but yields a lower bound
of inferior quality if solved as the PP. Other alternatives based on
relaxations have been proposed in the literature, e.g., SPPRC-k-cyc (Irnich
and Villeneuve, 2006) and ng-routes (Baldacci et al., 2011).

The success of B&P methods for solving the CVRP and other variants is in good
part due to the efficient methods for solving the PP, mainly using dynamic
programming. A labeling algorithm is commonly used where a label corresponds
to a partial path in $G$ (not to confound with the notion of label in ML). The
algorithm starts with an initial label representing the trivial path
containing only the source node $s$, it then gets extended forward along the
outgoing arcs until reaching the destination node $t$. A new label is created
at each extension if it yields a feasible path. At the end of the algorithm,
the labels at the destination node $t$ representing negative reduced cost
routes are used to build the new columns that are added to the RMP. Generally,
several routes are added at once, which is known to speed up the solution
process and to reduce the number of CG iterations.

The CVRP remains one of the most studied CO problems in the literature. An
efficient B&P algorithm can be quite sophisticated and may contain several
components. Discussing all the details is beyond the scope of this paper and
we refer the interested reader to the survey of (Costa et al., 2019) for an
in-depth overview of the methods.

####  3.2.3 Branch-and-price implementation

In this work, we consider using VRPSolver (Pessoa et al., 2020), which is a
generic implementation of an exact branch-cut-and-price method for VRP
problems. The advantage of using VRPSolver lies in the fact that it combines
several algorithms and acceleration techniques introduced by several authors,
e.g., ng-routes, path enumeration, bi-directional labeling, stabilization,
etc. Implementing these techniques from scratch would be otherwise very time
consuming. The authors report excellent performance on several benchmark
instances of various CVRP variants (e.g., with time windows, heterogeneous
fleet, multiple depots, pickups and deliveries, etc). For more information
about the implementation and the algorithms included in VRPSolver, the reader
is referred to Pessoa et al. (2020).

###  3.3 Heuristic algorithm

As previously mentioned, the CVRP remains a difficult problem to solve to
optimality and can be time consuming when working with large instances. For
our method, we need to solve several instances to collect enough data for the
training phase, but solving them to optimality is not required (although
recommended), since it is possible to obtain very high-quality solutions using
specialized CVRP heuristics. For this reason, we chose to use a recent
heuristic called FILO (Accorsi and Vigo, 2021), which is a short term for Fast
Iterated Localized Search Optimization.

The method is based on the iterated local search paradigm and is specifically
designed to solve large-scale instances of the CVRP. The algorithm starts by
constructing an initial feasible solution using an adaptation of the savings
algorithm by Clarke and Wright (1964). It is followed by an optional step that
aims at reducing the number of vehicles used in the initial solution, if the
latter is larger than a computed estimate (using a bin-packing greedy
algorithm). The algorithm then proceeds to the core optimization step, which
is based on a sequence of ruin and recreate steps. The ruin step removes a
certain number of vertices by means of a random walk of a given length (the
ruin intensity can be controlled by adapting the random walk length). Then,
the recreate step tries to reinsert the removed vertices while trying to
improve upon the best solution found. This is achieved by means of a number of
local search operators targetting the vertices involved in the disruptive
effects of the ruin step. The algorithm tries to keep a good balance between
intensification and diversification, i.e., the local search can be
concentrated on the parts of the solution that have not seen any improvement
after several attempts, and at the same time, a continuous diversification is
intended in order to escape from local optima. The algorithm stops after a
determined number of iterations and the best solution found is returned.

The performance of the FILO algorithm has been compared by the authors to
other state-of-the-art heuristics and has proven to be highly competitive on
the X instances introduced by Uchoa et al. (2017), which are also the
benchmark instances used by our method. Note that the purpose of this section
is not to present or compare the different heuristics that exist for solving
the CVRP, but simply to present the heuristic that we used to obtain high-
quality solutions during the data collection phase (i.e., with optimality gaps
of less than $0,1\%$ on average). The method has also the advantage of having
an open-source implementation that is freely accessible.

##  4 Methodology

The goal of this project is to accelerate the reoptimization of repeatedly
solved CO problems for which there is only a slight change in the problem
data. Let $\mathcal{P}_{o}$ and $\mathcal{S}_{o}$ be a problem instance and a
computed good-quality solution, respectively. Furthermore, let
$\mathcal{P}_{m}$ be a modified instance obtained by applying minor changes to
$\mathcal{P}_{o}$ and for which no solution is known. Instead of optimizing
$\mathcal{P}_{m}$ from scratch, the objective is to identify the parts of
$\mathcal{S}_{o}$ that have a high probability of also being part of a
solution to $\mathcal{P}_{m}$ denoted by $\mathcal{S}_{m}$.

In this paper, we focus on the CVRP where the locations of the clients are the
same but the demands are slightly different. Because we assume that the fleet
of vehicles is unlimited and the travel costs are symmetric, we consider for
the rest of this paper an undirected graph and denote by $E(\mathcal{S}_{o})$
the set of edges used in the known solution $\mathcal{S}_{o}$ to the original
instance $\mathcal{P}_{o}$. Since the solution consists of vehicle routes, if
we consider $E(\mathcal{S}_{o})$ as the set of edges used in a solution
$\mathcal{S}_{o}$ already in hand, the method aims at predicting the edges
$e\in E(\mathcal{S}_{o})$ that have a high chance to also be part of
$\mathcal{S}_{m}$. By fixing these edges, a significant reduction of the
problem complexity can be achieved, thus greatly reducing the computing time.
Let us take the example illustrated in Figure 1, where we can observe the
following: Figure (LABEL:subfig:original_solution) represents a solution
$\mathcal{S}_{o}$ to an original CVRP instance involving $110$ nodes. The
central node corresponds to the depot and the other nodes represent the
clients. Figure (LABEL:subfig:modified_solution) shows a solution
$\mathcal{S}_{m}$ to an instance $\mathcal{P}_{m}$ obtained by randomly
changing the demands of $20\%$ of the clients of $\mathcal{P}_{o}$ (the
clients with a changed demand are marked with a star node). By comparing the
two figures, one can notice a significant similarity between the two
solutions. Assuming we do not have yet the solution $\mathcal{S}_{m}$, if we
succeed in predicting and fixing the edges $e\in E(\mathcal{S}_{o})$ that will
be part of $\mathcal{S}_{m}$, a partial solution can be provided to the solver
before starting the optimization. This is shown in Figure
(LABEL:subfig:similarity_solutions), where the overlapping parts of the two
solutions are highlighted, i.e., the edges $e\in E(\mathcal{S}_{o})\cap
E(\mathcal{S}_{m})$. Furthermore, it is also possible to reduce the size of
the network by aggregating the sequences comprised of two or more edges into a
single one as shown in Figure (LABEL:subfig:aggregated_edges). As a result,
the number of nodes is reduced from $110$ to only $54$.

On the other hand, since the predictions obtained by the ML model are not
always accurate and errors may occur, fixing the wrong edges can affect the
quality of the solution obtained. In fact, fixing many edges implies shorter
computing times but more chances to fix the wrong ones. On the other hand, if
the number of fixed edges is small, there is a greater chance of obtaining a
better quality solution though with a higher computing time. By controlling
the number of fixed edges (e.g., by tuning the hyperparameters of the model),
it is possible to find the right compromise between the quality of the
solution and the computing time.

(a)

(b)

After changing demands

(c)

(d)

After aggregating sequences

Figure 1: Overview of the different steps of the method.

###  4.1 Data collection

We chose to address this learning problem using a supervised learning
approach. More precisely, a binary classification model is employed. The first
step in the process is to collect enough data for the training. Given a tuple
of original and modified instances and their solutions
$(\mathcal{P}_{o},\mathcal{S}_{o},\mathcal{P}_{m},\mathcal{S}_{m})$, a labeled
dataset $\mathcal{D}=\\{\\{\boldsymbol{x}_{e},y_{e}\\}|\forall e\in
E(\mathcal{S}_{o})\\}$ is built where each entry represents an edge in the
original solution, the vector $\boldsymbol{x}_{e}\in\mathbb{R}^{n}$
corresponds to the edge features (i.e., input), where $n$ is the number of
features and $y_{e}=\\{0,1\\}$ is the desired output (i.e., label). One can
notice that we are only interested in the edges of $\mathcal{S}_{o}$ and not
all the edges of the graph.

The labels. Since we tackle this problem in a supervised manner, we need both
solutions $\mathcal{S}_{o}$ and $\mathcal{S}_{m}$ to build the dataset, i.e.,
we need to give both the input and the desired output to the learner. The
labels are assigned by simply checking the overlapping edges between the
solutions $\mathcal{S}_{o}$ and $\mathcal{S}_{m}$ as follows:

$\displaystyle y_{e}=\begin{cases}1&\text{if $e\in E(\mathcal{S}_{o})\cap
E(\mathcal{S}_{m})$}\\\ 0&\text{otherwise}\end{cases},\hskip 14.22636pte\in
E(\mathcal{S}_{o}).$ (5)

The features. The features $\boldsymbol{x}_{e}$ represent the characteristics
of each edge $e=\langle i,j\rangle$ in the original solution. The extracted
features are the following:

  * •

The $(x,y)$ coordinates of both nodes $i$ and $j$;

  * •

The cost of edge $c_{e}$;

  * •

The old and new demands of nodes $i$ and $j$ (the demand is set to $0$ for the
depot nodes $s$ and $t$);

  * •

The distance between the depot and nodes $i$ and $j$;

  * •

A boolean value indicating whether the edge is a depot edge, i.e., equal to
$1$ if either $i$ or $j$ is a depot node;

  * •

A boolean value indicating whether the client $i$ or $j$, or both, have a
changed demand;

  * •

The rank of $i$ with respect to $j$ (and vice versa) according to the neighbor
distances, e.g., if $j$ is the nearest neighbor to $i$, then its rank is $1$,
if $j$ is the second closest neighbor to $i$ then its rank is $2$, and so on.

Note that since we are working on a symmetric version of the CVRP and that the
order of the entries in the vector $\boldsymbol{x}_{e}$ is important, we
always assume that $i<j$.

###  4.2 ML prediction

Once the dataset is in hand, we apply common ML practices such as data
preprocessing (i.e., normalization, encoding) and data splitting (i.e.,
dividing the data into a training, a validation and a test set), etc. As
mentioned before, the prediction task corresponds to a binary classification
problem and different ML models can be considered, e.g., Random Forest, SVM,
Neural network. In this section, we assume that we already have a trained
predictive model that takes as input the edge features $\boldsymbol{x}_{e}$
and outputs the predictions $\hat{y}_{e}$ and we wish to know what to do with
those predictions afterwards (the comparison of which ML model is best
performing is discussed in the next section).

####  4.2.1 ML-based edge fixing

Let $G=(V,E)$ be an undirected graph, where $V$ is the set of nodes including
the depot nodes and $E$ the set of edges. Let $c_{e},e\in E$ be the cost of
edge $e=\langle i,j\rangle$. The edge flow can be written in terms of the
master problem (1)-(3) variables as

$\displaystyle x_{e}=\sum_{r\in\Omega}b_{e}^{r}\theta_{r},$ (6)

where $b_{e}^{r}\in\\{0,1\\}$ indicates whether edge $e\in E$ is part of a
route $r\in\Omega$. Therefore, an edge can be fixed by adding a new constraint
to the master problem. For each edge in the original solution
$\mathcal{S}_{o}$, the flow is set to $1$ depending on the predictions
obtained by the ML model, namely

$\displaystyle x_{e}=1,\hskip 14.22636pt\forall e\in E(\mathcal{S}_{o})\hskip
2.84526pt:\hskip 2.84526pt\hat{y}_{e}=1.$ (7)

####  4.2.2 Infeasibility case

Sometimes fixing edges can lead to an infeasible restricted problem. This may
only occur in the case when the total demand of a sequence of clients fixed by
the ML model exceeds the vehicle capacity $Q$. For each edge, in addition to
the output $\hat{y}_{e}$ returned by the model, it is possible to obtain its
probability estimate $\hat{p}_{e}$ of being fixed. Generally, the model
assigns the class $1$ if the probability estimate $\hat{p}_{e}$ is greater
than $0.5$ and $0$ otherwise. For a sequence of clients whose sum of the
demands exceed $Q$, a possible solution would be to identify and unfix the
edges with lowest probabilities, until obtaining one or several feasible
subsequences.

Let $G_{\hat{y}}=(V_{\hat{y}},E_{\hat{y}})$ be the graph obtained by keeping
only the fixed edges and their corresponding nodes, i.e., $E_{\hat{y}}=\\{e\in
E\hskip 2.84526pt|\hskip 2.84526pt\hat{y}_{e}=1\\}$ and $V_{\hat{y}}=\\{i\in
V\hskip 5.69054pt|\hskip 5.69054pt\exists\langle k,l\rangle\in
E_{\hat{y}}:i=k\lor i=l\\}$. Depending on the predictions obtained by the
model, the graph may contain multiple sequences of two nodes or more. A
sequence can be defined as $p=(v^{p}_{1},v^{p}_{2},\dots,v^{p}_{|p|}),v_{i}\in
V_{\hat{y}}$, where $|p|$ is its length. Note that since the graph is
undirected, the sequence can start at either of its ends. Let
$E(p)=\\{\\{i,i+1\\}\hskip 5.69054pt|\hskip
5.69054pti\in\\{1,2,\dots,|p|-1\\}\\}$ be the set of edges of sequence $p$ and
$S(G_{\hat{y}})$ the set of all sequences in $G_{\hat{y}}$. We denote by
$d_{i}$ the demand of node $i$ ($d_{s}=d_{t}=0)$. The steps followed to
identify and to deal with the infeasible sequences are described in Algorithm
1.

Algorithm 1 Infeasibility check.

1:procedure resolve_infeasibility($G_{\hat{y}},\boldsymbol{\hat{p}}$)

2: do

3: infeasibilityDetected = False

4: for each sequence $p\in S(G_{\hat{y}})$ do

5: if $\sum_{i=1}^{|p|}d_{v^{p}_{i}}>Q$ then

6: $e=\operatorname*{arg\,min}_{e\in E(p)}\hat{p}_{e}$ $\triangleright$
Identify the edge with lowest probability

7: $E_{\hat{y}}=E_{\hat{y}}\setminus\\{e\\}$

8: $\hat{y}_{e}=0$

9: infeasibilityDetected = True

10: end if

11: end for

12: while infeasibilityDetected = True

13:end procedure

The algorithm takes as input the graph $G_{\hat{y}}$ and starts by
initializing the variable infeasibilityDetected to False (Step 3). Then, it
proceeds by looping over the sequences of the set $S(G_{\hat{y}})$ in Step 4.
For each sequence $p$, if the total demand of the clients exceeds the capacity
$Q$ of a vehicle (Step 5), the edge with the lowest probability estimate is
identified (Step 6), then unfixed and removed from the set of edges
$E_{\hat{y}}$ (Steps 7-8). This procedure is repeated until there are no more
infeasible sequences.

####  4.2.3 Network reduction

Once there are no more infeasible sequences, it is possible to make an
improvement that can further accelerate the optimization, which consists in
reducing the number of nodes and edges in the network. The simple (and well-
known) idea is to shrink the sequences of three nodes (i.e., two edges) or
more into a single edge, while making sure that the cost and the demands are
updated accordingly.
For a sequence $p=(v^{p}_{1},\dots,v^{p}_{|p|})\in S(G_{\hat{y}})$ with
$|p|\geq 3$, the goal is to remove all intermediate nodes
$v^{p}_{2},\dots,v^{p}_{|p|-1}$ and link directly the two ends of the sequence
by adding the edge $e_{new}=\langle v^{p}_{1},v^{p}_{|p|}\rangle$. Its cost is
updated to the cost of the whole sequence, i.e., $c_{e_{new}}=\sum_{e\in
E(p)}c_{e}$, and the demand of the removed nodes
$\sum_{i=2}^{|p|-1}d_{v^{p}_{i}}$ is added to the demand of either $v^{p}_{1}$
or $v^{p}_{|p|}$. Lastly, the edge is fixed by setting the corresponding flow
variable $x_{e_{new}}=1$. By doing so, traversing the edge $e_{new}$ becomes
equivalent to traversing the sequence $p$. The reduction of the network size
depends on the number of sequences and their lengths, in some cases a
significant reduction can be obtained, as illustrated in Figure
(LABEL:subfig:aggregated_edges).

####  4.2.4 Method summary

By putting all the pieces together, Algorithm 2 summarizes the different steps
of our method. Given the initial data
$(\mathcal{P}_{o},\mathcal{P}_{m},\mathcal{S}_{o})$, the algorithm starts by
extracting the edge features yielding the features matrix $\mathbf{X}$ (Step
1), then obtaining the predictions $\boldsymbol{\hat{y}}$ of the ML model and
the probability estimates $\boldsymbol{\hat{p}}$ in Steps 2-3. The graph
$G_{\hat{y}}$ representing the edges to fix is built (Steps 4-5) and the
procedure resolve_infeasibility described in Algorithm 1 is called to check
for any infeasible sequences. The algorithm proceeds by aggregating the
sequences in $S(G_{\hat{y}})$ by connecting each sequence ends (Step 9),
updating the cost and the demand (we added the demands of the intermediate
nodes to one of the two ends) in Steps 10-11, then removing the intermediate
nodes and their adjacent edges (Steps 12-13). Any removed node from
$G_{\hat{y}}$ must be removed from the original graph also. This is achieved
by updating $G$ to the induced subgraph $G[V_{\hat{y}}]$. At this point, the
graph $G$ corresponds to the original complete graph minus the removed nodes
from the network reduction step. Finally, the master problem is initialized
and solved after adding the flow constraints for each fixed edge (Steps
17-21).

Algorithm 2 ML-based edge fixing heuristic.

Data:
$\mathcal{P}_{o}$ : Original instance
$\mathcal{P}_{m}$ : Modified instance
$\mathcal{S}_{o}$ : Solution of the original instance
$G=(V,E)$ : Original graph

1:$\boldsymbol{X}\longleftarrow$ extractEdgeFeatures($\mathcal{P}_{o}$,
$\mathcal{P}_{m}$, $\mathcal{S}_{o}$)

2:$\boldsymbol{\hat{y}}\longleftarrow$ predict($\boldsymbol{X}$)

3:$\boldsymbol{\hat{p}}\longleftarrow$ predict_proba($\boldsymbol{X}$)

4:$V_{\hat{y}}=V,\hskip 5.69054ptE_{\hat{y}}=\\{e\in E\hskip 2.84526pt|\hskip
2.84526pt\hat{y}_{e}=1\\}$

5:$G_{\hat{y}}=(V_{\hat{y}},E_{\hat{y}})$

6:resolve_infeasibility($G_{\hat{y}},\boldsymbol{\hat{p}}$)

7:for each sequence $p=(v^{p}_{1},\dots,v^{p}_{|p|})\in S(G_{\hat{y}})$ do

8: if $|p|>2$ then

9: $e=\langle v^{p}_{1},v^{p}_{|p|}\rangle$

10: $c_{e}=\sum_{u\in E(p)}c_{u}$

11: $d_{v^{p}_{1}}=d_{v^{p}_{1}}+\sum_{i=2}^{|p|-1}d_{v^{p}_{i}}$

12: $V_{\hat{y}}=V_{\hat{y}}\setminus\\{v^{p}_{i}\hskip 5.69054pt|\hskip
5.69054pti\in\\{2,\dots,|p|-1\\}\\}$

13: $E_{\hat{y}}=E_{\hat{y}}\setminus\\{\langle i,j\rangle\in E\hskip
5.69054pt|\hskip 5.69054pti\notin V_{\hat{y}}\lor j\notin V_{\hat{y}}\\}$

14: end if

15:end for

16:$G=G[V_{\hat{y}}]$

17:MP $\longleftarrow$ initialize_MP($\mathcal{P}_{m}$)

18:for each edge $e\in E_{\hat{y}}$ do

19: add_constraint(MP,"$x_{e}=1$")

20:end for

21:solve($\mathcal{P}_{m},G$)

Network reduction

##  5 Computational experiments

This section start by describing the CVRP instances we used and the data
generation process. Next, we present the details about the ML phase. Finally,
the results of our heuristic method on different benchmark instances are
reported. All the experiments were conducted on a Linux machine with an
Xeon(R) Gold 6142 CPU @ 2.60GHz and 512GB of RAM.

###  5.1 CVRP instances

The instances used are based on the X benchmark dataset introduced by Uchoa et
al. (2017). Each instance is characterized by the following attributes:

  * •

Depot position: The possible values are Central (C) (i.e., the depot is
positioned at the center of the grid), Eccentric (E) (i.e., the depot is
positioned at the South-West corner $(0,0)$ of the grid) and Random (R).

  * •

Client positioning: The three possibilities are Random (R) (i.e., the clients
are randomly dispersed on the grid), Clustered (C) (i.e., the clients are
grouped in clusters) and a combination of both, referred to as Random-
Clustered (RC).

  * •

Demand distribution: For the client demands, there are seven options with
different intervals, and all demands are drawn uniformally from each
distribution. The demands can range from: (a) [1-10], (b) [5-10], (c) [1-100],
(d) [50-100], (e) clients located in an even quadrant have demands in the
range [1-50] and [50,100] for the others, (f) $70\%$ to $95\%$ of the clients
have a demand in the range [1,10] and [50,100] for the remaining ones and
finally, (g) unit demands, where all the demands are equal to $1$.

  * •

Average route size: This represents the average number of clients that can be
visited by the same route, which is directly controlled by the vehicles
capacity. This is computed as $n/K_{min}$ where $n$ is the number of clients
and $K_{min}$ is an estimate of the minimum number of vehicles required to
service all clients.

Since we are interested in modifying the demands of the clients, we exclude
the instances with unit demands. Table 1 describes the instances we picked for
our experiments. The instance names are written in the form
“X-n[$n_{nodes}$]-k[$n_{vehicles}$]” where $n_{nodes}$ is the number of nodes
including the depot and $n_{vehicles}$ is an estimate of the number of
vehicles required to service all clients. The remaining columns report the
characteristics described above.

Instance name | Depot | Client | Demand | Avg. route
---|---|---|---|---
position | positioning | distribution | size
X-n101-k25 | R | RC | $[1-100]$ | 4.0
X-n106-k14 | E | C | $[50-100]$ | $7.5$
X-n110-k13 | C | R | $[5-10]$ | 8.4
X-n125-k30 | R | C | $Quadrant$ | 4.1
X-n129-k18 | E | RC | $[1-10]$ | 7.1
X-n134-k13 | R | C | $Quadrant$ | 10.2
X-n139-k10 | C | R | $[5-10]$ | 13.8
X-n143-k07 | E | R | $[1-100]$ | 20.3

Table 1: CVRP instances from the X benchmark instances.

###  5.2 Data generation

For each instance described in Table 1, we generate a set of modified
instances by randomly changing the demands of $N_{c}\%$ of the clients. The
new demand of each of these clients is chosen randomly in the interval
$[d_{i}-\Delta_{d},d_{i}+\Delta_{d}],$ where $d_{i}$ is the original demand of
the client $i$ and $\Delta_{d}$ a parameter controlling the interval width. In
order to analyze the impact of the demand changes on the performance of the
heuristic and the predictions, we used different values of
$N_{c}\in\\{10,20,30\\}$. As for $\Delta_{d}$, since each instance has a
different demand distribution, we created three classes of intervals: Small
(S), Medium (M) and Large (L), controlled by the value of $\Delta_{d}$ as
shown in Table 2.

Demand |  $\Delta_{d}$ (interval size)
---|---
distribution |  S |  M |  L
$[1-100]$ | 5 | 10 | 15
$[50-100]$ | 5 | 10 | 15
$[5-10]$ | 1 | 2 | 3
$Quadrant$ | 5 | 10 | 15
$[1-10]$ | 2 | 3 | 4

Table 2: $\Delta_{d}$ values used depending on the demand distribution.

By combining the three different values of $N_{c}$ and the three interval
sizes, this results in nine different scenarios $\Phi=$ {10S, 10M, 10L, 20S,
20M, 20L, 30S, 30M, 30L}. We then proceeded as follows. For each instance in
Table 1 and each scenario $\phi\in\Phi$, $100$ modified instances are
generated, where $95$ of them are used for the ML phase (i.e., training,
parameters tuning, etc.) and the remaining $5$ for the optimization phase
(i.e., when the ML model is incorporated in the CG algorithm). We therefore
consider the eight instances of Table 1 as the original instances (i.e.,
$\mathcal{P}_{o}^{1},\dots,\mathcal{P}_{o}^{8}$) and, for each scenario
$\phi$, we generate $100$ modified versions (i.e.,
$(\mathcal{P}_{m}^{i})_{\phi}^{1},\dots,(\mathcal{P}_{m}^{i})_{\phi}^{100},i\in\\{1,2,\dots,8\\},\phi\in\Phi$).
One ML-model is trained for each instance and for each scenario. The idea of
training a model for each instance comes from the assumption that we have a
specific instance that we solve repeatedly. Therefore we want a specific model
for that particular instance. This makes a total of $8$ instances
$\times\hskip 2.84526pt9$ scenarios $\times\hskip 2.84526pt100=7,200$ modified
instances generated (and $8\times 9=72$ ML models). Given the large number of
instances, instead of using an exact B&P method for solving and collecting
solutions, we opted to use the FILO heuristic of Accorsi and Vigo (2021)(see
Section 3.3). For each of the $7,200$ instances, we run the heuristic using
$10$ different random seed values for 1,000,000 iterations and the solution
with the smallest cost is retained.

Once the solutions of the original and modified instances are obtained, for
each instance $i\in\\{1,\dots,8\\}$ and scenario $\phi\in\Phi$, the solutions
are grouped in a set of tuples, i.e.,
$\\{(\mathcal{P}_{o}^{i},\mathcal{S}_{o}^{i},(\mathcal{P}_{m}^{i})_{\phi}^{1},(\mathcal{S}_{m}^{i})_{\phi}^{1}),\allowbreak\dots,\allowbreak(\mathcal{P}_{o}^{i},\mathcal{S}_{o}^{i},(\mathcal{P}_{m}^{i})_{\phi}^{100},(\mathcal{S}_{m}^{i})_{\phi}^{100})\\}$
that are used to extract the edge features and labels as detailed in Section
4.1.

###  5.3 Machine learning phase

Before starting the training, common practices in ML are followed, starting by
a pre-processing phase that consists of scaling and normalizing the data. The
dataset (i.e., the data from the 95 instances) is then split into a training
set, a validation set and a test set. The goal of the validation set is to
tune the different hyperparameters, whereas the purpose of the test set is to
compare different classification algorithms, such as logistic regression,
K-nearest neighbors, random forest, artificial neural network (ANN), etc.
According to the results obtained on the test set, the ANN model is the
overall most robust model with accuracies ranging from $70\%$ to $88\%$
depending on the instance and the scenario $\phi\in\Phi$ (more detailed
results about the models performance are reported in the next section). The
hyperparameter values used during the training of the ANN models are described
in Table 3.

Hyperparameter | Value
---|---
Learning rate | $10^{-3}$
Number of epochs | 1000
Epoch size | 64
Batch size | 32
NN Architecture | $32\times 32\times 32\times 1$
Activation function | ReLU
Output function | Sigmoid
Optimizer | Adam
Class weights | Balanced
Table 3: Hyperparameters values of the ANN models.

###  5.4 Optimization phase

In this section, we present the results obtained by our edge-fixing heuristic.
Since a ML model is trained for each original instance and scenario, we report
the ML model performance in this section as well. Tables 4 to 6 summarize the
results obtained on the test instances. Each row corresponds to the average
values obtained on the 5 test instances (for each original instance), whereas
the details of each individual instance can be found in Appendix A. There is
one table for each $N_{c}$ value (i.e., 10, 20 and 30 for Tables 4, 5 and 6,
respectively). The first column corresponds to the interval used when changing
the demands (i.e., S, M and L, respectively), followed by the name of the
original instance $\mathcal{P}_{o}$. Next, the average cost of the best
solutions $\mathcal{S}_{m}$ obtained by the FILO heuristic (over the 10
executions of the heuristic with different seeds). In the fourth column, we
report the average similarity between the solution of the original instance
and the solution of the modified instances computed by the following formula:

$\displaystyle
sim(\mathcal{S}_{o},\mathcal{S}_{m})=\frac{|E(\mathcal{S}_{o})\cap
E(\mathcal{S}_{m})|}{|E(\mathcal{S}_{o})|}.$ (8)

Notice that this similarity also matches the percentage of edges to fix (i.e.,
with the label $1$). The next three columns summarize the performance of the
ML model and show the following metrics: the True Negative Rate (TNR)
corresponds to the percentage of edges that should not be fixed and that are
predicted accurately; the True Positive Rate (TPR) is equal to the percentage
of edges that should be fixed and that are predicted correctly; and the
(balanced) accuracy is the mean of the two previous columns. By fixing the
edges suggested by the ML model and solving the instance using VRPSolver, we
obtain the results shown under the heading “Edge-fixing”: the average costs of
the solutions as well as the computing times in seconds. To evaluate the
quality of this solution, we report the average gap that compares the cost of
the solution of our method with that of the solution $\mathcal{S}_{m}$ of the
FILO heuristic (third column). The next three columns provide the average cost
of the solutions computed by the exact algorithm in VRPSolver, the average
computing time and the ratio with respect to the computing time of our method
(i.e., the computing time of the exact B&P algorithm divided by the computing
time of our edge-fixing method). For the exact algorithm, a time limit of five
hours is set. Empty values mean that the exact B&P failed to find an optimal
solution in the time limit for one or more of the 5 instances, refer to
Appendix A for additional details.

A natural question with respect to the proposed approach is if there is value
in trying to learn the difference between solutions of slightly modified
instances. Indeed, ML-based CVRP heuristics should be in a very favorable
position in our computational setting because the instances are from a
specific data distribution and of the same size, i.e., no generalization is
needed. In order to give a tentative answer to this question, we compare the
performance of our method with another ML method for the CVRP not designed for
reoptimization purposes but with excellent overall performance on recent
benchmarks. We chose the Dual-Aspect Collaborative Transformer algorithm (DACT
- Ma et al. (2021)) that is considered one of the most effective methods for
solving the CVRP to-date in terms of solution quality according to the recent
survey Bogyrbayeva et al. (2022). Unlike our approach, DACT is a reinforcement
learning method that learns an improvement heuristic, which means that it
starts with an initial solution and tries to improve it in an iterative way.
In this method, the learner (i.e., the agent) learns to identify a pair of
nodes on which to apply a pairwise operator (e.g., 2-opt, swap, insert) and is
rewarded when a better solution is found. The authors report good results that
outperform several other learning methods on the X benchmark instances (same
instances we are using) in a reasonable computing time. In our case, we
proceeded by using the same pretrained model that the authors used in their
paper but with additional training on the 8 instances we focus on (see Table
1), in addition to using the same parameters of their best performing model.
The results obtained are reported in the last two columns of Tables 4 to 6,
representing respectively the average cost of the solutions and the gap with
respect to the FILO heuristic (just like Edge-Fixing).

Interval | $\mathcal{P}_{o}$ | $\mathcal{S}_{m}$ cost | $sim(\mathcal{S}_{o},\mathcal{S}_{m})$ | ML model metrics | Edge-fixing | Exact B&P | DACT
---|---|---|---|---|---|---|---
TNR | TPR | Accuracy | Cost | Time (s) | Gap | Cost | Time (s) | Ratio | Cost | Gap
Small | X-n101-k25 | 27637 | 84% | 71% | 70% | 70% | 27718 | 13 | 0.29% | 27635 | 211 | 22.4 | 28184 | 1.98%
X-n106-k14 | 26376 | 85% | 89% | 60% | 75% | 26436 | 25 | 0.23% | 26376 | 962 | 61.3 | 26897 | 1.98%
X-n110-k13 | 14987 | 93% | 100% | 66% | 83% | 14987 | 8 | 0.00% | 14987 | 265 | 36.7 | 15159 | 1.15%
X-n125-k30 | 55613 | 63% | 76% | 73% | 75% | 55683 | 235 | 0.13% | - | - | - | 58581 | 5.34%
X-n129-k18 | 28765 | 62% | 78% | 72% | 75% | 28982 | 78 | 0.75% | 28765 | 3479 | 53.4 | 29697 | 3.24%
X-n134-k13 | 10888 | 80% | 89% | 54% | 72% | 10917 | 77 | 0.27% | - | - | - | 11284 | 3.64%
X-n139-k10 | 13590 | 85% | 92% | 81% | 86% | 13599 | 26 | 0.06% | - | - | - | 13846 | 1.88%
X-n143-k07 | 15722 | 81% | 87% | 88% | 88% | 15726 | 54 | 0.02% | - | - | - | 16245 | 3.32%
Average | 23886 | 79% | 85% | 71% | 78% | 24256 | 65 | 0.22% | - | - | - | 24987 | 2.82%
Medium | X-n101-k25 | 27606 | 83% | 77% | 63% | 70% | 27736 | 18 | 0.47% | 27606 | 324 | 20.4 | 28298 | 2.51%
X-n106-k14 | 26358 | 66% | 95% | 73% | 84% | 26380 | 14 | 0.08% | 26358 | 355 | 23.9 | 26871 | 1.95%
X-n110-k13 | 14971 | 87% | 98% | 67% | 82% | 14993 | 12 | 0.15% | 14969 | 283 | 24.5 | 15137 | 1.11%
X-n125-k30 | 55713 | 60% | 74% | 73% | 74% | 55758 | 198 | 0.08% | 55655 | 5156 | 58.4 | 58735 | 5.42%
X-n129-k18 | 28862 | 60% | 74% | 75% | 75% | 29124 | 105 | 0.91% | - | - | - | 29801 | 3.26%
X-n134-k13 | 10888 | 63% | 74% | 73% | 74% | 11024 | 320 | 1.25% | - | - | - | 11304 | 3.82%
X-n139-k10 | 13601 | 90% | 85% | 76% | 81% | 13608 | 27 | 0.05% | - | - | - | 13863 | 1.92%
X-n143-k07 | 15707 | 85% | 97% | 79% | 88% | 15710 | 63 | 0.02% | - | - | - | 16200 | 3.14%
Average | 24213 | 74% | 84% | 72% | 78% | 24292 | 95 | 0.38% | - | - | - | 25026 | 2.89%
Large | X-n101-k25 | 27651 | 70% | 63% | 77% | 70% | 28125 | 122 | 1.71% | 27648 | 399 | 7.9 | 28142 | 1.98%
X-n106-k14 | 26412 | 65% | 84% | 74% | 79% | 26557 | 250 | 0.54% | - | - | - | 26846 | 1.64%
X-n110-k13 | 15030 | 75% | 86% | 73% | 80% | 15107 | 35 | 0.51% | 15030 | 2283 | 60.7 | 15187 | 1.04%
X-n125-k30 | 55733 | 55% | 81% | 75% | 78% | 55825 | 422 | 0.16% | - | - | - | 58500 | 4.97%
X-n129-k18 | 28755 | 62% | 78% | 73% | 75% | 28972 | 171 | 0.76% | 28748 | 2457 | 22.5 | 29546 | 2.75%
X-n134-k13 | 10908 | 69% | 72% | 68% | 70% | 10908 | 164 | 0.66% | - | - | - | 11267 | 3.29%
X-n139-k10 | 13600 | 83% | 85% | 75% | 80% | 13635 | 47 | 0.26% | - | - | - | 13850 | 1.84%
X-n143-k07 | 15716 | 88% | 97% | 73% | 85% | 15717 | 62 | 0.00% | - | - | - | 16265 | 3.49%
Average | 24226 | 71% | 81% | 73% | 77% | 24365 | 159 | 0.58% | - | - | - | 24950 | 2.62%

Table 4: Average results for scenarios with $N_{c}=10$.

Interval | $\mathcal{P}_{o}$ | $\mathcal{S}_{m}$ cost | $sim(\mathcal{S}_{o},\mathcal{S}_{m})$ | ML model metrics | Edge-fixing | Exact B&P | DACT
---|---|---|---|---|---|---|---
TNR | TPR | Accuracy | Cost | Time (s) | Gap | Cost | Time (s) | Ratio | Cost | Gap
Small | X-n101-k25 | 27486 | 83% | 73% | 75% | 74% | 27628 | 29 | 0.51% | 27486 | 231 | 8.6 | 28220 | 2.67%
X-n106-k14 | 26338 | 72% | 90% | 71% | 81% | 26401 | 30 | 0.24% | 26336 | 1147 | 88.5 | 26845 | 1.93%
X-n110-k13 | 14980 | 77% | 86% | 74% | 80% | 15024 | 9 | 0.29% | 14980 | 429 | 55.5 | 15152 | 1.15%
X-n125-k30 | 55493 | 63% | 85% | 68% | 77% | 55509 | 233 | 0.03% | - | - | - | 58372 | 5.19%
X-n129-k18 | 29020 | 56% | 71% | 78% | 74% | 29408 | 143 | 1.33% | 29009 | 5791 | 76.5 | 29703 | 2.35%
X-n134-k13 | 10909 | 73% | 85% | 69% | 77% | 10943 | 150 | 0.32% | - | - | - | 11323 | 3.80%
X-n139-k10 | 13613 | 87% | 91% | 81% | 86% | 13616 | 103 | 0.02% | - | - | - | 13870 | 1.89%
X-n143-k07 | 15715 | 86% | 90% | 86% | 88% | 15748 | 30 | 0.21% | - | - | - | 16261 | 3.47%
Average | 24194 | 75% | 84% | 75% | 80% | 24284 | 91 | 0.37% | - | - | - | 24968 | 2.81%
Medium | X-n101-k25 | 27512 | 68% | 74% | 72% | 73% | 27694 | 32 | 0.66% | 27512 | 518 | 19.4 | 28076 | 2.05%
X-n106-k14 | 26306 | 64% | 87% | 71% | 79% | 26400 | 20 | 0.36% | 26306 | 5257 | 238.2 | 26785 | 1.72%
X-n110-k13 | 14983 | 73% | 86% | 77% | 82% | 15078 | 27 | 0.64% | 14983 | 548 | 30.3 | 15217 | 1.56%
X-n125-k30 | 55503 | 54% | 82% | 74% | 78% | 55579 | 233 | 0.14% | - | - | - | 58528 | 5.45%
X-n129-k18 | 29171 | 57% | 73% | 76% | 74% | 29655 | 315 | 1.66% | - | - | - | 30001 | 2.85%
X-n134-k13 | 10877 | 55% | 82% | 80% | 81% | 10956 | 127 | 0.73% | - | - | - | 11258 | 3.50%
X-n139-k10 | 13605 | 72% | 87% | 80% | 84% | 13631 | 205 | 0.20% | - | - | - | 13855 | 1.84%
X-n143-k07 | 15708 | 81% | 80% | 83% | 82% | 15745 | 49 | 0.24% | - | - | - | 16233 | 3.35%
Average | 24208 | 65% | 81% | 77% | 79% | 24342 | 126 | 0.58% | - | - | - | 24991 | 2.79%
Large | X-n101-k25 | 27645 | 59% | 70% | 73% | 72% | 27871 | 56 | 0.81% | 27645 | 466 | 30.8 | 28244 | 2.17%
X-n106-k14 | 26413 | 61% | 79% | 74% | 77% | 26555 | 100 | 0.54% | - | - | - | 26834 | 1.59%
X-n110-k13 | 15034 | 68% | 81% | 79% | 80% | 15161 | 23 | 0.84% | 15034 | 487 | 25.4 | 15216 | 1.21%
X-n125-k30 | 55958 | 58% | 79% | 70% | 74% | 56168 | 433 | 0.37% | - | - | - | 58629 | 4.77%
X-n129-k18 | 29123 | 55% | 77% | 74% | 75% | 29462 | 386 | 1.16% | 29092 | 3106 | 16.0 | 29848 | 2.49%
X-n134-k13 | 10909 | 55% | 82% | 80% | 81% | 11051 | 254 | 1.31% | - | - | - | 11317 | 3.75%
X-n139-k10 | 13585 | 73% | 88% | 77% | 83% | 13619 | 139 | 0.25% | - | - | - | 13788 | 1.50%
X-n143-k07 | 15743 | 84% | 79% | 79% | 79% | 15775 | 41 | 0.20% | - | - | - | 16332 | 3.74%
Average | 24301 | 64% | 79% | 76% | 78% | 24458 | 179 | 0.69% | - | - | - | 25026 | 2.65%

Table 5: Average results for scenarios with $N_{c}=20$.

Interval | $\mathcal{P}_{o}$ | $\mathcal{S}_{m}$ cost | $sim(\mathcal{S}_{o},\mathcal{S}_{m})$ | ML model metrics | Edge-fixing | Exact B&P | DACT
---|---|---|---|---|---|---|---
TNR | TPR | Accuracy | Cost | Time (s) | Gap | Cost | Time (s) | Ratio | Cost | Gap
Small | X-n101-k25 | 27562 | 75% | 80% | 70% | 75% | 27669 | 37 | 0.39% | 27562 | 178 | 5.9 | 28219 | 2.38%
X-n106-k14 | 26383 | 65% | 89% | 69% | 79% | 26438 | 148 | 0.21% | 26378 | 1577 | 25.9 | 26833 | 1.70%
X-n110-k13 | 15005 | 74% | 92% | 77% | 84% | 15083 | 32 | 0.52% | 15005 | 555 | 21.8 | 15157 | 1.01%
X-n125-k30 | 55776 | 53% | 77% | 73% | 75% | 55834 | 259 | 0.10% | - | - | - | 58601 | 5.06%
X-n129-k18 | 29414 | 58% | 80% | 74% | 77% | 29778 | 237 | 1.24% | 29405 | 3742 | 24.8 | 30086 | 2.28%
X-n134-k13 | 10925 | 77% | 90% | 62% | 76% | 10952 | 140 | 0.25% | - | - | - | 11361 | 4.00%
X-n139-k10 | 13622 | 83% | 91% | 73% | 82% | 13692 | 154 | 0.51% | - | - | - | 13829 | 1.52%
X-n143-k07 | 15754 | 83% | 79% | 87% | 83% | 15822 | 56 | 0.43% | - | - | - | 16328 | 3.65%
Average | 24305 | 71% | 85% | 73% | 79% | 24409 | 133 | 0.46% | - | - | - | 25052 | 2.70%
Medium | X-n101-k25 | 27654 | 63% | 68% | 73% | 71% | 27804 | 51 | 0.54% | 27651 | 243 | 24.8 | 28277 | 2.25%
X-n106-k14 | 26437 | 59% | 75% | 70% | 73% | 26615 | 247 | 0.67% | - | - | - | 26780 | 1.30%
X-n110-k13 | 15058 | 77% | 87% | 72% | 79% | 15095 | 14 | 0.24% | 15058 | 269 | 33.6 | 15292 | 1.55%
X-n125-k30 | 55925 | 50% | 82% | 78% | 80% | 56009 | 451 | 0.15% | - | - | - | 58859 | 5.25%
X-n129-k18 | 29221 | 54% | 79% | 75% | 77% | 29698 | 137 | 1.63% | 29215 | 3574 | 34.8 | 29849 | 2.16%
X-n134-k13 | 10926 | 56% | 83% | 80% | 81% | 11048 | 129 | 1.12% | - | - | - | 11301 | 3.43%
X-n139-k10 | 13640 | 75% | 89% | 78% | 83% | 13708 | 256 | 0.49% | - | - | - | 13926 | 2.09%
X-n143-k07 | 15782 | 80% | 78% | 85% | 82% | 15870 | 49 | 0.55% | - | - | - | 16423 | 4.06%
Average | 24330 | 64% | 80% | 76% | 78% | 24481 | 167 | 0.67% | - | - | - | 25088 | 2.76%
Large | X-n101-k25 | 27617 | 66% | 76% | 72% | 74% | 27929 | 185 | 1.12% | 27617 | 339 | 19.4 | 28207 | 2.13%
X-n106-k14 | 26440 | 54% | 79% | 68% | 74% | 26637 | 275 | 0.75% | - | - | - | 26913 | 1.79%
X-n110-k13 | 15090 | 66% | 82% | 72% | 77% | 15211 | 88 | 0.80% | 15090 | 1120 | 18.7 | 15318 | 1.51%
X-n125-k30 | 56228 | 52% | 84% | 71% | 78% | 56221 | 475 | -0.01% | - | - | - | 58725 | 4.44%
X-n129-k18 | 29674 | 58% | 75% | 73% | 74% | 30179 | 75 | 1.69% | 29670 | 4914 | 69.9 | 30554 | 2.97%
X-n134-k13 | 10950 | 53% | 83% | 82% | 82% | 11029 | 145 | 0.72% | - | - | - | 11423 | 4.31%
X-n139-k10 | 13616 | 73% | 91% | 76% | 84% | 13635 | 128 | 0.14% | - | - | - | 13868 | 1.85%
X-n143-k07 | 15884 | 79% | 82% | 83% | 83% | 15941 | 313 | 0.36% | - | - | - | 16326 | 2.79%
Average | 24437 | 63% | 82% | 75% | 78% | 24598 | 211 | 0.70% | - | - | - | 25167 | 2.72%

Table 6: Average results for scenarios with $N_{c}=30$.

According to the results reported in Tables 4 to 6, we can notice that on
average the similarity decreases by increasing the number of changes we make
on the demands (controlled by the parameter $N_{c}$ and the intervals), which
is expected. A high similarity of 79% is noticed on average on the instances
with 10% change and small interval, while the instances with 30% change and
large interval have an average similarity of 63%. At the instance level, it
seems that the dispersion of the clients as well as the length of the routes
can have an impact on the similarity of the solutions. For example, the
instances with randomly dispersed clients and medium to long routes (e.g.,
X-n110-k13, X-n139-k10, X-n143-k07) tend to have a higher similarity compared
to instances with clustered clients (e.g., X-n106-k14 and X-n125-k30).

Before evaluating the performance of the model, we would like to highlight the
impact that a bad prediction may have in the obtained solution. If some edges
are not fixed when they should be (false negatives), it can affect the
computing time but the solver can still include them in the final solution.
However, the edges with label 0 can have a more serious impact, since they can
affect the quality of the solution if predicted inaccurately (false
positives), which potentially leads to a higher gap. As previously mentioned,
the similarity is also the percentage of edges to be fixed. A high similarity
means that most of the edges in the solution of the original instance are
labeled $1$, which also implies that the ML model tends to make fewer
“significant” errors since there are not many edges with label $0$. If we
focus on the solution quality, it is possible to give a higher weight to the
edges with label 0, which can lead to a high TNR (thus reducing the false
positives) and probably a lower TPR, meaning that less edges will be fixed
resulting in a higher computing time. Conversely, if we do the opposite and
assign a higher weight to the edges with label 1, we will likely fix more
edges and achieve a lower computing time but at the expense of bad-quality
solutions. In our case, we use a balanced weight between the two classes as
shown in Table 3. Depending on the desired goal, one seeks to find a
compromise between quality and computing time.

From the ML metrics obtained we can observe an average accuracy ranging from
$78\%$ to $80\%$, but if we look closer at the individual instances, we can
notice some variance and a slight positive correlation between the accuracy
and the similarity. By fixing the edges proposed by the model and comparing
the solution with the one of the FILO heuristic, we obtain an average gap
ranging from $0.22\%$ to $0.70\%$. We can also notice that the gap follows the
same tendency as the similarity, i.e., more changes of the demands imply less
similarity, more possible misclassifications and thus a higher gap. Therefore,
the instances with high similarity (e.g., instances with dispersed clients and
long routes) generally have a lower gap compared to the others. The detailed
results in Appendix A indicate that the gap of the individual instances can
vary between $0\%$ and $1.71\%$. A perfect solution is obtained (i.e., same
solution as the FILO heuristic, thus a $0\%$ gap) when the TNR is $100\%$. In
a few rare cases, the solver was able to find a better solution than the
heuristic even after fixing parts of the solution, such as X-n125-k30_10M_4 in
Table 8 and X-n125-k30_30L_3 in Table 15. Generally, the FILO heuristic finds
very good solutions (especially when considering 10 runs): it succeeds in
finding the optimal solution in many cases when compared to the available
exact B&P results. We believe that the gap reported between the edge-fixing
and the FILO heuristic must not be far from the one with the exact B&P
algorithm.

In terms of computing time, the edge fixing method takes only a few minutes or
even a few seconds in some cases to find the optimal solution of the modified
problem (that with fixed variables according to the ML prediction), whereas
the exact B&P algorithm that solves the (original) problem from scratch can
take hours of computation to find an optimal solution, and in many cases no
solution is found after the time limit especially for large instances.
Apparently, the current version of VRPSolver does not have strong heuristics
to produce feasible solutions. On the one side, this is not an issue for our
computational investigation because we use VRPSolver as well (and we are
definitely not using it for comparison). On the other side, this is somehow
reinforcing the fact that, after our proposed fixing, the instances are much
easier and even without good heuristics VRPSolver is very effective on them.
Note that in our experiments, the FILO heuristic with 1,000,000 iterations
takes about 8 to 13 minutes per execution depending on the instance size, not
to forget that we executed the heuristic 10 different times with different
seeds and retained the best solution. Overall, the computing time of the edge-
fixing heuristic remains lower than a single execution of FILO and way lower
than an exact B&P algorithm.

Concerning the DACT method, we can notice an average gap of $2.7\%$. The
method performs better on some instances than on others with gaps ranging from
$0.03\%$ up to $5.72\%$ according to the detailed results in Appendix A. Since
the method is iterative and performs a certain number of steps at the
inference phase (more precisely 10,000 steps as described in Ma et al.
(2021)), its computing time is not negligible and can range from 10 to 15
minutes on average depending on the instance size. Therefore, the edge-fixing
method outperforms DACT both in terms of computing time and solution quality.

##  6 Conclusion

In this paper, we proposed a ML-based heuristic for the reoptimization of
repeatedly solved problems after minor changes in the problem data. More
precisely, we put ourselves in the context of a company that solves CVRPs on a
daily basis where the locations of the clients are the same but slightly
different demands occur. Given that there can be a great similarity between
the solutions, the goal was to exploit the ones obtained from previous
executions (not necessarily optimal ones) in order to speed up the
reoptimization of future instances. The aim was to predict and fix the edges
that have a high chance of remaining in the solution after a change of the
demands.

Following a supervised learning approach, we trained neural network models on
the data collected from a recent heuristic for the CVRP called FILO. The
models achieved an average accuracy of 78% on the test instances. By
incorporating the predictions in our edge-fixing method, we were able to find
solutions in reasonable computing times with gaps ranging from $0\%$ to
$1.71\%$ (with an average of $0.51\%$) when compared to the FILO heuristic we
learned from. These gaps are also lower compared to other recent ML methods
proposed in the literature such as the DACT method used to compute the entire
CVRP solution. We also obtained an acceleration effect, considerably reducing
the size of the network and allowing an even faster reoptimization.

Future work can seek some improvements, for example by the exploration of more
complex learning models that can take advantage of the graph structure of the
problem or even sequence models since we are dealing with routes. This may
potentially lead to a better accuracy and therefore better gaps and lower
computing times.

## References

  * Accorsi and Vigo (2021) Luca Accorsi and Daniele Vigo.  A fast and scalable heuristic for the solution of large-scale capacitated vehicle routing problems.  _Transportation Science_ , 55(4):832–856, 2021\.  doi: 10.1287/trsc.2021.1059.
  * Alvarez et al. (2017) Alejandro Marcos Alvarez, Quentin Louveaux, and Louis Wehenkel.  A machine learning-based approximation of strong branching.  _INFORMS Journal on Computing_ , 29(1):185–195, 2017.  doi: 10.1287/ijoc.2016.0723.
  * Baldacci et al. (2011) Roberto Baldacci, Aristide Mingozzi, and Roberto Roberti.  New route relaxation and pricing strategies for the vehicle routing problem.  _Operations Research_ , 59(5):1269–1283, 2011\.  doi: 10.1287/opre.1110.0975.
  * Barnhart et al. (1996) Cynthia Barnhart, Ellis L. Johnson, George L. Nemhauser, Martin W. P. Savelsbergh, and Pamela H. Vance.  Branch-and-price: Column generation for solving huge integer programs.  _Operations Research_ , 46:316–329, 1996.
  * Bello et al. (2016) Irwan Bello, Hieu Pham, Quoc V. Le, Mohammad Norouzi, and Samy Bengio.  Neural combinatorial optimization with reinforcement learning, 2016.  URL https://arxiv.org/abs/1611.09940.
  * Bengio et al. (2021) Yoshua Bengio, Andrea Lodi, and Antoine Prouvost.  Machine learning for combinatorial optimization: a methodological tour d’horizon.  _European Journal of Operational Research_ , 290(2):405–421, 2021.  doi: 10.1016/j.ejor.2020.07.063.
  * Bogyrbayeva et al. (2022) Aigerim Bogyrbayeva, Meraryslan Meraliyev, Taukekhan Mustakhov, and Bissenbay Dauletbayev.  Learning to solve vehicle routing problems: A survey, 2022.  URL https://arxiv.org/abs/2205.02453.
  * Bonami et al. (2022) Pierre Bonami, Andrea Lodi, and Giulia Zarpellon.  A classifier to decide on the linearization of mixed-integer quadratic problems in cplex.  _Operations Research_ , 0(0):0, 2022.  doi: 10.1287/opre.2022.2267.
  * Cappart et al. (2021) Quentin Cappart, Didier Chételat, Elias Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković.  Combinatorial optimization and reasoning with graph neural networks.  _arXiv preprint arXiv:2102.09544_ , 2021.
  * Clarke and Wright (1964) G. Clarke and J. W. Wright.  Scheduling of vehicles from a central depot to a number of delivery points.  _Operations Research_ , 12(4):568–581, 1964.
  * Costa et al. (2019) Luciano Costa, Claudio Contardo, and Guy Desaulniers.  Exact branch-price-and-cut algorithms for vehicle routing.  _Transportation Science_ , 53(4):946–985, 2019\.  doi: 10.1287/trsc.2018.0878.
  * Dai et al. (2017) Hanjun Dai, Elias B. Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song.  Learning combinatorial optimization algorithms over graphs, 2017.  URL https://arxiv.org/abs/1704.01665.
  * Desaulniers et al. (2005) Guy Desaulniers, Jacques Desrosiers, and Marius M. Solomon.  _Column generation_.  Springer, New York, January 2005.
  * Gasse et al. (2019) Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi.  Exact combinatorial optimization with graph convolutional neural networks, 2019.  URL https://arxiv.org/abs/1906.01629.
  * Irnich and Desaulniers (2005) Stefan Irnich and Guy Desaulniers.  Shortest path problems with resource constraints.  In Guy Desaulniers, Jacques Desrosiers, and Marius M. Solomon, editors, _Column Generation_ , pages 33–65. Springer US, Boston, MA, 2005\.
  * Irnich and Villeneuve (2006) Stefan Irnich and Daniel Villeneuve.  The shortest-path problem with resource constraints and k-cycle elimination for k $\leq$ 3\.  _INFORMS Journal on Computing_ , 18(3):391–406, 2006.  doi: 10.1287/ijoc.1040.0117.
  * Joshi et al. (2019) Chaitanya K. Joshi, Thomas Laurent, and Xavier Bresson.  An efficient graph convolutional network technique for the travelling salesman problem, 2019.  URL https://arxiv.org/abs/1906.01227.
  * Khalil et al. (2016) Elias B. Khalil, Pierre Le Bodic, Le Song, George Nemhauser, and Bistra Dilkina.  Learning to branch in mixed integer programming.  In _Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence_ , AAAI’16, page 724–731. AAAI Press, 2016.
  * Kool et al. (2018) Wouter Kool, Herke van Hoof, and Max Welling.  Attention, learn to solve routing problems!, 2018.  URL https://arxiv.org/abs/1803.08475.
  * Kotary et al. (2021) James Kotary, Ferdinando Fioretto, Pascal Van Hentenryck, and Bryan Wilder.  End-to-end constrained optimization learning: A survey, 2021.  URL https://arxiv.org/abs/2103.16378.
  * Kruber et al. (2017) Markus Kruber, Marco E. Lübbecke, and Axel Parmentier.  Learning when to use a decomposition.  In Domenico Salvagnin and Michele Lombardi, editors, _Integration of AI and OR Techniques in Constraint Programming_ , pages 202–210, Cham, 2017. Springer International Publishing.  ISBN 978-3-319-59776-8.
  * Li et al. (2018) Zhuwen Li, Qifeng Chen, and Vladlen Koltun.  Combinatorial optimization with graph convolutional networks and guided tree search, 2018.  URL https://arxiv.org/abs/1810.10659.
  * Lodi et al. (2020) Andrea Lodi, Luca Mossina, and Emmanuel Rachelson.  Learning to handle parameter perturbations in combinatorial optimization: An application to facility location.  _EURO Journal on Transportation and Logistics_ , 9(4):100023, 2020.  doi: https://doi.org/10.1016/j.ejtl.2020.100023.
  * Ma et al. (2021) Yining Ma, Jingwen Li, Zhiguang Cao, Wen Song, Le Zhang, Zhenghua Chen, and Jing Tang.  Learning to iteratively solve routing problems with dual-aspect collaborative transformer, 2021.  URL https://arxiv.org/abs/2110.02544.
  * Manchanda et al. (2019) Sahil Manchanda, Akash Mittal, Anuj Dhawan, Sourav Medya, Sayan Ranu, and Ambuj Singh.  Learning heuristics over large graphs via deep reinforcement learning, 2019.  URL https://arxiv.org/abs/1903.03332.
  * Nazari et al. (2018) MohammadReza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takac.  Reinforcement learning for solving the vehicle routing problem.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc., 2018.
  * Pessoa et al. (2020) Artur Pessoa, Ruslan Sadykov, Eduardo Uchoa, and François Vanderbeck.  A generic exact solver for vehicle routing and related problems.  _Mathematical Programming_ , 183(1):483–523, Sep 2020.  doi: 10.1007/s10107-020-01523-z.
  * Uchoa et al. (2017) Eduardo Uchoa, Diego Pecin, Artur Pessoa, Marcus Poggi, Thibaut Vidal, and Anand Subramanian.  New benchmark instances for the capacitated vehicle routing problem.  _European Journal of Operational Research_ , 257(3):845–858, 2017.  doi: https://doi.org/10.1016/j.ejor.2016.08.012.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention is all you need, 2017.  URL https://arxiv.org/abs/1706.03762.
  * Xavier et al. (2021) Álinson S. Xavier, Feng Qiu, and Shabbir Ahmed.  Learning to solve large-scale security-constrained unit commitment problems.  _INFORMS Journal on Computing_ , 33(2):739–756, 2021.  doi: 10.1287/ijoc.2020.0976.
  * Zarpellon et al. (2020) Giulia Zarpellon, Jason Jo, Andrea Lodi, and Yoshua Bengio.  Parameterizing branch-and-bound search trees to learn branching policies, 2020.  URL https://arxiv.org/abs/2002.05120.

##  Appendix A Detailed results of the experiments

This section provides detailed computational results that are complementary to
those presented in Section 5. The results are grouped by scenario ($N_{c}$ and
interval) and reported in Tables 7-15. The same information as in Tables 4 to
6 is reported, with the only difference that each row represents an individual
instance. Also, an additional column has been added to indicate the name
suffix of the modified instance $\mathcal{P}_{m}$ (second column).

$\mathcal{P}_{o}$ | $\mathcal{P}_{m}$ | $\mathcal{S}_{m}$ cost | $sim(\mathcal{S}_{o},\mathcal{S}_{m})$ | ML model metrics | Edge-fixing | Exact BaP | DACT
---|---|---|---|---|---|---|---
TNR | TPR | Accuracy | Cost | Time (s) | Gap | Cost | Time (s) | Ratio | Cost | Gap
X-n101-k25 | _10S_1 | 27538 | 84% | 55% | 67% | 61% | 27733 | 26 | 0.71% | 27538 | 226 | 8.7 | 27943 | 1.47%
_10S_2 | 27775 | 71% | 61% | 73% | 67% | 27849 | 14 | 0.27% | 27764 | 199 | 14.2 | 28306 | 1.91%
_10S_3 | 27591 | 100% | 100% | 63% | 82% | 27591 | 7 | 0.00% | 27591 | 180 | 25.7 | 28287 | 2.52%
_10S_4 | 27703 | 73% | 60% | 76% | 68% | 27811 | 14 | 0.39% | 27703 | 276 | 19.7 | 27966 | 0.95%
_10S_5 | 27580 | 91% | 77% | 70% | 74% | 27605 | 4 | 0.09% | 27580 | 175 | 43.8 | 28417 | 3.03%
Average | - | 27637 | 84% | 71% | 70% | 70% | 27718 | 13 | 0.29% | 27635 | 211 | 22.4 | 28184 | 1.98%
X-n106-k14 | _10S_1 | 26403 | 77% | 74% | 64% | 69% | 26600 | 58 | 0.75% | 26403 | 1567 | 27.0 | 26977 | 2.17%
_10S_2 | 26398 | 85% | 85% | 59% | 72% | 26478 | 46 | 0.30% | 26398 | 1246 | 27.1 | 26860 | 1.75%
_10S_3 | 26365 | 94% | 100% | 56% | 78% | 26365 | 8 | 0.00% | 26365 | 589 | 73.6 | 26957 | 2.25%
_10S_4 | 26359 | 89% | 92% | 60% | 76% | 26366 | 8 | 0.03% | 26359 | 1250 | 156.3 | 26904 | 2.07%
_10S_5 | 26353 | 82% | 95% | 63% | 79% | 26369 | 7 | 0.06% | 26353 | 157 | 22.4 | 26789 | 1.65%
Average | - | 26376 | 85% | 89% | 60% | 75% | 26436 | 25 | 0.23% | 26376 | 962 | 61.3 | 26897 | 1.98%
X-n110-k13 | _10S_1 | 14971 | 95% | 100% | 64% | 82% | 14971 | 11 | 0.00% | 14971 | 141 | 12.8 | 15102 | 0.88%
_10S_2 | 15006 | 95% | 100% | 64% | 82% | 15006 | 6 | 0.00% | 15006 | 241 | 40.2 | 15275 | 1.79%
_10S_3 | 14996 | 92% | 100% | 68% | 84% | 14996 | 6 | 0.00% | 14996 | 338 | 56.3 | 15212 | 1.44%
_10S_4 | 14965 | 87% | 100% | 70% | 85% | 14965 | 7 | 0.00% | 14965 | 215 | 30.7 | 15076 | 0.74%
_10S_5 | 14996 | 96% | 100% | 66% | 83% | 14996 | 9 | 0.00% | 14996 | 389 | 43.2 | 15130 | 0.89%
Average | - | 14987 | 93% | 100% | 66% | 83% | 14987 | 8 | 0.00% | 14987 | 265 | 36.7 | 15159 | 1.15%
X-n125-k30 | _10S_1 | 55573 | 67% | 68% | 68% | 68% | 55715 | 71 | 0.26% | 55573 | 1044 | 14.7 | 58563 | 5.38%
_10S_2 | 55784 | 57% | 77% | 76% | 77% | 55786 | 788 | 0.004% | 55817 |  $>$5h | - | 58883 | 5.56%
_10S_3 | 55653 | 65% | 80% | 74% | 77% | 55654 | 169 | 0.002% | 55638 | 3161 | 18.7 | 58609 | 5.31%
_10S_4 | 55487 | 69% | 79% | 70% | 75% | 55661 | 84 | 0.31% | 55487 | 3243 | 38.6 | 58473 | 5.38%
_10S_5 | 55567 | 57% | 76% | 77% | 77% | 55599 | 64 | 0.06% | 55530 | 1927 | 30.1 | 58379 | 5.06%
Average | - | 55613 | 63% | 76% | 73% | 75% | 55683 | 235 | 0.13% | - | - | - | 58581 | 5.34%
X-n129-k18 | _10S_1 | 28981 | 59% | 77% | 75% | 76% | 29472 | 129 | 1.69% | 28981 | 2793 | 21.7 | 30015 | 3.57%
_10S_2 | 29061 | 62% | 81% | 74% | 78% | 29257 | 81 | 0.67% | 29061 | 1034 | 12.8 | 30055 | 3.42%
_10S_3 | 28644 | 58% | 70% | 68% | 69% | 28781 | 74 | 0.48% | 28643 | 3124 | 42.2 | 29630 | 3.44%
_10S_4 | 28598 | 70% | 81% | 67% | 74% | 28716 | 56 | 0.41% | 28598 | 9179 | 163.9 | 29265 | 2.33%
_10S_5 | 28541 | 60% | 82% | 77% | 80% | 28685 | 48 | 0.50% | 28541 | 1263 | 26.3 | 29518 | 3.42%
Average | - | 28765 | 62% | 78% | 72% | 75% | 28982 | 78 | 0.75% | 28765 | 3479 | 53.4 | 29697 | 3.24%
X-n134-k13 | _10S_1 | 10906 | 89% | 87% | 52% | 70% | 10913 | 37 | 0.06% | - |  $>$5h | - | 11416 | 4.68%
_10S_2 | 10916 | 100% | 100% | 45% | 73% | 10916 | 50 | 0.00% | - |  $>$5h | - | 11274 | 3.28%
_10S_3 | 10809 | 54% | 75% | 62% | 69% | 10929 | 190 | 1.11% | - |  $>$5h | - | 11205 | 3.66%
_10S_4 | 10892 | 56% | 85% | 67% | 76% | 10913 | 72 | 0.19% | - |  $>$5h | - | 11293 | 3.68%
_10S_5 | 10916 | 100% | 100% | 42% | 71% | 10916 | 37 | 0.00% | 10950 |  $>$5h | - | 11234 | 2.91%
Average | - | 10888 | 80% | 89% | 54% | 72% | 10917 | 77 | 0.27% | - | - | - | 11284 | 3.64%
X-n139-k10 | _10S_1 | 13586 | 93% | 100% | 76% | 88% | 13586 | 34 | 0.00% | 13586 | 10804 | 317.8 | 13753 | 1.23%
_10S_2 | 13605 | 89% | 100% | 81% | 91% | 13605 | 17 | 0.00% | 13609 |  $>$5h | - | 13869 | 1.94%
_10S_3 | 13607 | 85% | 100% | 81% | 91% | 13607 | 35 | 0.00% | - |  $>$5h | - | 13945 | 2.48%
_10S_4 | 13611 | 91% | 100% | 80% | 90% | 13611 | 19 | 0.00% | 13611 | 17189 | 904.7 | 13820 | 1.54%
_10S_5 | 13542 | 67% | 60% | 86% | 73% | 13586 | 24 | 0.32% | - |  $>$5h | - | 13841 | 2.21%
Average | - | 13590 | 85% | 92% | 81% | 86% | 13599 | 26 | 0.06% | - | - | - | 13846 | 1.88%
X-n143-k07 | _10S_1 | 15716 | 85% | 100% | 88% | 94% | 15716 | 21 | 0.00% | - |  $>$5h | - | 16347 | 4.02%
_10S_2 | 15726 | 85% | 85% | 85% | 85% | 15738 | 41 | 0.08% | - |  $>$5h | - | 16237 | 3.25%
_10S_3 | 15733 | 83% | 87% | 86% | 87% | 15736 | 117 | 0.02% | - |  $>$5h | - | 16063 | 2.10%
_10S_4 | 15730 | 68% | 62% | 93% | 78% | 15734 | 50 | 0.03% | - |  $>$5h | - | 16243 | 3.26%
_10S_5 | 15707 | 83% | 100% | 89% | 95% | 15707 | 41 | 0.00% | - |  $>$5h | - | 16334 | 3.99%
Average | - | 15722 | 81% | 87% | 88% | 88% | 15726 | 54 | 0.02% | - | - | - | 16245 | 3.32%

Table 7: Results for instances with $N_{c}=10$ and Small (S) intervals.

$\mathcal{P}_{o}$ | $\mathcal{P}_{m}$ | $\mathcal{S}_{m}$ cost | $sim(\mathcal{S}_{o},\mathcal{S}_{m})$ | ML model metrics | Edge-fixing | Exact BaP | DACT
---|---|---|---|---|---|---|---
TNR | TPR | Accuracy | Cost | Time (s) | Gap | Cost | Time (s) | Ratio | Cost | Gap
X-n101-k25 | _10M_1 | 27722 | 88% | 83% | 63% | 73% | 27969 | 36 | 0.89% | 27722 | 544 | 15.1 | 28417 | 2.51%
_10M_2 | 27636 | 76% | 72% | 66% | 69% | 27841 | 19 | 0.74% | 27636 | 246 | 12.9 | 28156 | 1.88%
_10M_3 | 27411 | 88% | 67% | 61% | 64% | 27482 | 19 | 0.26% | 27411 | 370 | 19.5 | 28143 | 2.67%
_10M_4 | 27655 | 69% | 61% | 65% | 63% | 27784 | 10 | 0.47% | 27655 | 117 | 11.7 | 28286 | 2.28%
_10M_5 | 27605 | 96% | 100% | 59% | 80% | 27605 | 8 | 0.00% | 27605 | 343 | 42.9 | 28489 | 3.20%
Average | - | 27606 | 83% | 77% | 63% | 70% | 27736 | 18 | 0.47% | 27606 | 324 | 20.4 | 28298 | 2.51%
X-n106-k14 | _10M_1 | 26399 | 56% | 90% | 79% | 85% | 26433 | 19 | 0.13% | 26399 | 684 | 36.0 | 26882 | 1.83%
_10M_2 | 26341 | 63% | 97% | 76% | 87% | 26370 | 20 | 0.11% | 26341 | 368 | 18.4 | 26898 | 2.11%
_10M_3 | 26340 | 61% | 96% | 78% | 87% | 26374 | 14 | 0.13% | 26340 | 210 | 15.0 | 26853 | 1.95%
_10M_4 | 26381 | 60% | 93% | 78% | 86% | 26392 | 13 | 0.04% | 26381 | 424 | 32.6 | 26796 | 1.57%
_10M_5 | 26330 | 88% | 100% | 55% | 78% | 26330 | 5 | 0.00% | 26330 | 88 | 17.6 | 26928 | 2.27%
Average | - | 26358 | 66% | 95% | 73% | 84% | 26380 | 14 | 0.08% | 26358 | 355 | 23.9 | 26871 | 1.95%
X-n110-k13 | _10M_1 | 14899 | 82% | 95% | 69% | 82% | 14910 | 13 | 0.07% | 14889 | 441 | 33.9 | 14972 | 0.49%
_10M_2 | 15032 | 82% | 95% | 69% | 82% | 15131 | 14 | 0.66% | 15032 | 502 | 35.9 | 15197 | 1.10%
_10M_3 | 15018 | 91% | 100% | 64% | 82% | 15018 | 15 | 0.00% | 15018 | 106 | 7.1 | 15187 | 1.13%
_10M_4 | 14933 | 86% | 100% | 68% | 84% | 14933 | 11 | 0.00% | 14933 | 131 | 11.9 | 15223 | 1.94%
_10M_5 | 14971 | 95% | 100% | 63% | 82% | 14971 | 7 | 0.00% | 14971 | 237 | 33.9 | 15107 | 0.91%
Average | - | 14971 | 87% | 98% | 67% | 82% | 14993 | 12 | 0.15% | 14969 | 283 | 24.5 | 15137 | 1.11%
X-n125-k30 | _10M_1 | 55529 | 70% | 79% | 68% | 74% | 55608 | 79 | 0.14% | 55529 | 2284 | 28.9 | 58614 | 5.56%
_10M_2 | 55735 | 53% | 82% | 82% | 82% | 55807 | 75 | 0.13% | 55620 | 7479 | 99.7 | 58916 | 5.71%
_10M_3 | 55828 | 68% | 65% | 64% | 65% | 55858 | 56 | 0.05% | 55828 | 6486 | 115.8 | 58461 | 4.72%
_10M_4 | 55773 | 51% | 72% | 78% | 75% | 55690 | 23 | -0.15% | 55647 | 834 | 36.3 | 58579 | 5.03%
_10M_5 | 55700 | 57% | 74% | 71% | 73% | 55828 | 755 | 0.23% | 55650 | 8696 | 11.5 | 59103 | 6.11%
Average | - | 55713 | 60% | 74% | 73% | 74% | 55758 | 198 | 0.08% | 55655 | 5156 | 58.4 | 58735 | 5.42%
X-n129-k18 | _10M_1 | 28661 | 54% | 72% | 77% | 75% | 29332 | 67 | 2.34% | 28661 | 356 | 5.3 | 29734 | 3.74%
_10M_2 | 29035 | 61% | 70% | 74% | 72% | 29203 | 27 | 0.58% | 29031 | 3817 | 141.4 | 30139 | 3.80%
_10M_3 | 29283 | 58% | 73% | 73% | 73% | 29559 | 115 | 0.94% | 29460 |  $>$5h | - | 30142 | 2.93%
_10M_4 | 28920 | 64% | 79% | 76% | 78% | 28931 | 30 | 0.04% | 28910 | 2674 | 89.1 | 29751 | 2.87%
_10M_5 | 28409 | 62% | 77% | 75% | 76% | 28594 | 286 | 0.65% | 28395 | 1290 | 4.5 | 29240 | 2.93%
Average | - | 28862 | 60% | 74% | 75% | 75% | 29124 | 105 | 0.91% | - | - | - | 29801 | 3.26%
X-n134-k13 | _10M_1 | 10891 | 59% | 79% | 77% | 78% | 11083 | 554 | 1.76% | - |  $>$5h | - | 11265 | 3.43%
_10M_2 | 10952 | 90% | 60% | 55% | 58% | 11095 | 645 | 1.31% | - |  $>$5h | - | 11387 | 3.97%
_10M_3 | 10792 | 54% | 71% | 76% | 74% | 10910 | 20 | 1.09% | - |  $>$5h | - | 11254 | 4.28%
_10M_4 | 10891 | 57% | 79% | 77% | 78% | 10979 | 165 | 0.81% | - |  $>$5h | - | 11265 | 3.43%
_10M_5 | 10915 | 55% | 80% | 81% | 81% | 11055 | 214 | 1.28% | - |  $>$5h | - | 11349 | 3.98%
Average | - | 10888 | 63% | 74% | 73% | 74% | 11024 | 320 | 1.25% | - | - | - | 11304 | 3.82%
X-n139-k10 | _10M_1 | 13584 | 97% | 100% | 71% | 86% | 13584 | 48 | 0.00% | 13584 |  $>$5h | - | 13727 | 1.05%
_10M_2 | 13605 | 89% | 93% | 78% | 86% | 13621 | 18 | 0.12% | - |  $>$5h | - | 14027 | 3.10%
_10M_3 | 13606 | 81% | 74% | 82% | 78% | 13610 | 28 | 0.03% | 13649 |  $>$5h | - | 13775 | 1.24%
_10M_4 | 13611 | 91% | 100% | 77% | 89% | 13611 | 12 | 0.00% | - |  $>$5h | - | 13894 | 2.08%
_10M_5 | 13600 | 93% | 60% | 72% | 66% | 13613 | 28 | 0.10% | - |  $>$5h | - | 13890 | 2.13%
Average | - | 13601 | 90% | 85% | 76% | 81% | 13608 | 27 | 0.05% | - | - | - | 13863 | 1.92%
X-n143-k07 | _10M_1 | 15724 | 81% | 96% | 84% | 90% | 15739 | 156 | 0.10% | - |  $>$5h | - | 16151 | 2.72%
_10M_2 | 15747 | 87% | 100% | 80% | 90% | 15747 | 41 | 0.00% | - |  $>$5h | - | 16370 | 3.96%
_10M_3 | 15667 | 83% | 100% | 80% | 90% | 15667 | 43 | 0.00% | - |  $>$5h | - | 16150 | 3.08%
_10M_4 | 15691 | 87% | 100% | 75% | 88% | 15691 | 41 | 0.00% | - |  $>$5h | - | 16193 | 3.20%
_10M_5 | 15706 | 85% | 90% | 78% | 84% | 15706 | 36 | 0.00% | - |  $>$5h | - | 16136 | 2.74%
Average | - | 15707 | 85% | 97% | 79% | 88% | 15710 | 63 | 0.02% | - | - | - | 16200 | 3.14%

Table 8: Results for instances with $N_{c}=10$ and Medium (M) intervals.

$\mathcal{P}_{o}$ | $\mathcal{P}_{m}$ | $\mathcal{S}_{m}$ cost | $sim(\mathcal{S}_{o},\mathcal{S}_{m})$ | ML model metrics | Edge-fixing | Exact BaP | DACT
---|---|---|---|---|---|---|---
TNR | TPR | Accuracy | Cost | Time (s) | Gap | Cost | Time (s) | Ratio | Cost | Gap
X-n101-k25 | _10L_1 | 27781 | 83% | 64% | 70% | 67% | 28176 | 85 | 1.42% | 27781 | 123 | 1.4 | 28420 | 2.30%
_10L_2 | 27493 | 61% | 66% | 86% | 76% | 27786 | 15 | 1.07% | 27493 | 154 | 10.3 | 27812 | 1.16%
_10L_3 | 27490 | 80% | 78% | 77% | 78% | 27526 | 15 | 0.13% | 27490 | 245 | 16.3 | 28297 | 2.94%
_10L_4 | 27775 | 64% | 60% | 78% | 69% | 28665 | 424 | 3.20% | 27759 | 788 | 1.9 | 28248 | 1.70%
_10L_5 | 27717 | 64% | 45% | 74% | 60% | 28472 | 71 | 2.72% | 27717 | 683 | 9.6 | 28210 | 1.78%
Average | - | 27651 | 70% | 63% | 77% | 70% | 28125 | 122 | 1.71% | 27648 | 399 | 7.9 | 28142 | 1.98%
X-n106-k14 | _10L_1 | 26400 | 60% | 89% | 84% | 87% | 26472 | 22 | 0.27% | 26400 | 454 | 20.6 | 26776 | 1.42%
_10L_2 | 26463 | 68% | 81% | 70% | 76% | 26705 | 408 | 0.91% | 26463 | 10289 | 25.2 | 26934 | 1.78%
_10L_3 | 26354 | 59% | 88% | 85% | 87% | 26423 | 146 | 0.26% | 26354 | 662 | 4.5 | 26860 | 1.92%
_10L_4 | 26515 | 50% | 64% | 72% | 68% | 26825 | 667 | 1.17% | 26549 |  $>$5h | - | 26974 | 1.73%
_10L_5 | 26330 | 88% | 96% | 60% | 78% | 26358 | 9 | 0.11% | 26330 | 95 | 10.6 | 26686 | 1.35%
Average | - | 26412 | 65% | 84% | 74% | 79% | 26557 | 250 | 0.54% | - | - | - | 26846 | 1.64%
X-n110-k13 | _10L_1 | 14945 | 86% | 91% | 66% | 79% | 14961 | 9 | 0.11% | 14945 | 529 | 58.8 | 14950 | 0.03%
_10L_2 | 15203 | 63% | 83% | 81% | 82% | 15314 | 82 | 0.73% | 15203 | 8812 | 107.5 | 15313 | 0.72%
_10L_3 | 14992 | 72% | 69% | 69% | 69% | 15181 | 62 | 1.26% | 14992 | 676 | 10.9 | 15169 | 1.18%
_10L_4 | 15088 | 64% | 89% | 84% | 87% | 15157 | 15 | 0.46% | 15088 | 1063 | 70.9 | 15473 | 2.55%
_10L_5 | 14923 | 92% | 100% | 64% | 82% | 14923 | 6 | 0.00% | 14923 | 333 | 55.5 | 15032 | 0.73%
Average | - | 15030 | 75% | 86% | 73% | 80% | 15107 | 35 | 0.51% | 15030 | 2283 | 60.7 | 15187 | 1.04%
X-n125-k30 | _10L_1 | 55480 | 59% | 88% | 74% | 81% | 55517 | 159 | 0.07% | 55480 | 2091 | 13.2 | 58240 | 4.97%
_10L_2 | 55409 | 58% | 84% | 74% | 79% | 55587 | 38 | 0.32% | 55383 | 17979 | 473.1 | 57890 | 4.48%
_10L_3 | 56244 | 49% | 76% | 76% | 76% | 56250 | 543 | 0.01% | 56143 | 11651 | 21.5 | 58517 | 4.04%
_10L_4 | 55829 | 57% | 80% | 72% | 76% | 55909 | 118 | 0.14% | 55717 | 5987 | 50.7 | 58796 | 5.31%
_10L_5 | 55705 | 51% | 79% | 77% | 78% | 55861 | 1252 | 0.28% | 55802 |  $>$5h | - | 59059 | 6.02%
Average | - | 55733 | 55% | 81% | 75% | 78% | 55825 | 422 | 0.16% | - | - | - | 58500 | 4.97%
X-n129-k18 | _10L_1 | 28546 | 64% | 64% | 63% | 64% | 29015 | 165 | 1.64% | 28546 | 2873 | 17.4 | 29354 | 2.83%
_10L_2 | 29109 | 60% | 89% | 81% | 85% | 29245 | 69 | 0.47% | 29109 | 5039 | 73.0 | 29824 | 2.46%
_10L_3 | 29042 | 60% | 81% | 75% | 78% | 29146 | 100 | 0.36% | 29042 | 889 | 8.9 | 29992 | 3.27%
_10L_4 | 28673 | 57% | 80% | 79% | 80% | 28839 | 269 | 0.58% | 28641 | 3035 | 11.3 | 29441 | 2.68%
_10L_5 | 28403 | 68% | 76% | 66% | 71% | 28615 | 251 | 0.75% | 28403 | 451 | 1.8 | 29120 | 2.52%
Average | - | 28755 | 62% | 78% | 73% | 75% | 28972 | 171 | 0.76% | 28748 | 2457 | 22.5 | 29546 | 2.75%
X-n134-k13 | _10L_1 | 10935 | 80% | 75% | 62% | 69% | 10964 | 27 | 0.27% | - |  $>$5h | - | 11251 | 2.89%
_10L_2 | 10941 | 54% | 85% | 88% | 87% | 10998 | 34 | 0.52% | - |  $>$5h | - | 11293 | 3.22%
_10L_3 | 10792 | 58% | 64% | 65% | 65% | 10963 | 307 | 1.58% | - |  $>$5h | - | 11129 | 3.12%
_10L_4 | 10944 | 56% | 78% | 75% | 77% | 10989 | 298 | 0.41% | - |  $>$5h | - | 11297 | 3.23%
_10L_5 | 10928 | 95% | 57% | 52% | 55% | 10984 | 152 | 0.51% | - |  $>$5h | - | 11363 | 3.98%
Average | - | 10908 | 69% | 72% | 68% | 70% | 10908 | 164 | 0.66% | - | - | - | 11267 | 3.29%
X-n139-k10 | _10L_1 | 13580 | 89% | 86% | 71% | 79% | 13581 | 73 | 0.01% | 13580 | 13184 | 180.6 | 13859 | 2.05%
_10L_2 | 13588 | 77% | 95% | 81% | 88% | 13674 | 58 | 0.63% | - |  $>$5h | - | 13870 | 2.08%
_10L_3 | 13595 | 82% | 82% | 77% | 80% | 13600 | 26 | 0.04% | 13595 | 7712 | 296.6 | 13833 | 1.75%
_10L_4 | 13625 | 76% | 72% | 78% | 75% | 13660 | 38 | 0.26% | 13625 | 13273 | 349.3 | 13832 | 1.52%
_10L_5 | 13612 | 91% | 91% | 70% | 81% | 13660 | 41 | 0.35% | - |  $>$5h | - | 13855 | 1.79%
Average | - | 13600 | 83% | 85% | 75% | 80% | 13635 | 47 | 0.26% | - | - | - | 13850 | 1.84%
X-n143-k07 | _10L_1 | 15735 | 89% | 100% | 72% | 86% | 15735 | 18 | 0.000% | - |  $>$5h | - | 16335 | 3.81%
_10L_2 | 15734 | 87% | 94% | 75% | 85% | 15736 | 54 | 0.013% | - |  $>$5h | - | 16196 | 2.94%
_10L_3 | 15727 | 90% | 100% | 71% | 86% | 15727 | 60 | 0.000% | - |  $>$5h | - | 16175 | 2.85%
_10L_4 | 15703 | 90% | 92% | 71% | 82% | 15703 | 40 | 0.000% | - |  $>$5h | - | 16020 | 2.02%
_10L_5 | 15683 | 85% | 100% | 74% | 87% | 15683 | 139 | 0.000% | - |  $>$5h | - | 16598 | 5.83%
Average | - | 15716 | 88% | 97% | 73% | 85% | 15717 | 62 | 0.00% | - | - | - | 16265 | 3.49%

Table 9: Results for instances with $N_{c}=10$ and Large (L) intervals.

$\mathcal{P}_{o}$ | $\mathcal{P}_{m}$ | $\mathcal{S}_{m}$ cost | $sim(\mathcal{S}_{o},\mathcal{S}_{m})$ | ML model metrics | Edge-fixing | Exact BaP | DACT
---|---|---|---|---|---|---|---
TNR | TPR | Accuracy | Cost | Time (s) | Gap | Cost | Time (s) | Ratio | Cost | Gap
X-n101-k25 | _20S_1 | 27524 | 73% | 75% | 82% | 79% | 27761 | 13 | 0.86% | 27524 | 140 | 10.8 | 28402 | 3.19%
_20S_2 | 27543 | 96% | 75% | 70% | 73% | 27543 | 27 | 0.00% | 27543 | 328 | 12.1 | 28145 | 2.19%
_20S_3 | 27461 | 84% | 87% | 75% | 81% | 27551 | 26 | 0.33% | 27461 | 227 | 8.7 | 28137 | 2.46%
_20S_4 | 27522 | 88% | 64% | 69% | 67% | 27709 | 44 | 0.68% | 27522 | 288 | 6.5 | 27980 | 1.66%
_20S_5 | 27382 | 73% | 62% | 78% | 70% | 27575 | 36 | 0.70% | 27382 | 171 | 4.8 | 28436 | 3.85%
Average | - | 27486 | 83% | 73% | 75% | 74% | 27628 | 29 | 0.51% | 27486 | 231 | 8.6 | 28220 | 2.67%
X-n106-k14 | _20S_1 | 26357 | 76% | 92% | 68% | 80% | 26391 | 11 | 0.13% | 26357 | 407 | 37.0 | 26884 | 2.00%
_20S_2 | 26318 | 72% | 96% | 72% | 84% | 26359 | 33 | 0.16% | 26318 | 453 | 13.7 | 26888 | 2.17%
_20S_3 | 26360 | 74% | 73% | 64% | 69% | 26524 | 66 | 0.62% | 26360 | 784 | 11.9 | 26897 | 2.04%
_20S_4 | 26292 | 60% | 91% | 82% | 87% | 26372 | 31 | 0.30% | 26292 | 432 | 13.9 | 26804 | 1.95%
_20S_5 | 26361 | 78% | 100% | 69% | 85% | 26361 | 10 | 0.00% | 26355 | 3660 | 366.0 | 26753 | 1.49%
Average | - | 26338 | 72% | 90% | 71% | 81% | 26401 | 30 | 0.24% | 26336 | 1147 | 88.5 | 26845 | 1.93%
X-n110-k13 | _20S_1 | 15039 | 63% | 70% | 77% | 74% | 15068 | 17 | 0.19% | 15039 | 297 | 17.5 | 15153 | 0.76%
_20S_2 | 14985 | 92% | 83% | 64% | 74% | 15033 | 8 | 0.32% | 14985 | 208 | 26.0 | 15116 | 0.87%
_20S_3 | 15047 | 84% | 100% | 72% | 86% | 15047 | 7 | 0.00% | 15047 | 1487 | 212.4 | 15219 | 1.14%
_20S_4 | 14930 | 69% | 86% | 82% | 84% | 15024 | 10 | 0.63% | 14930 | 114 | 11.4 | 15148 | 1.46%
_20S_5 | 14899 | 79% | 92% | 76% | 84% | 14946 | 4 | 0.32% | 14899 | 41 | 10.3 | 15122 | 1.50%
Average | - | 14980 | 77% | 86% | 74% | 80% | 15024 | 9 | 0.29% | 14980 | 429 | 55.5 | 15152 | 1.15%
X-n125-k30 | _20S_1 | 55528 | 62% | 80% | 67% | 74% | 55589 | 189 | 0.11% | - |  $>$5h | - | 58525 | 5.40%
_20S_2 | 55486 | 57% | 86% | 76% | 81% | 55546 | 387 | 0.11% | 55481 | 3074 | 7.9 | 58331 | 5.13%
_20S_3 | 55688 | 57% | 81% | 71% | 76% | 55624 | 282 | -0.11% | 55612 | 11840 | 42.0 | 58771 | 5.54%
_20S_4 | 55371 | 74% | 87% | 60% | 74% | 55394 | 154 | 0.04% | - |  $>$5h | - | 58010 | 4.77%
_20S_5 | 55390 | 65% | 92% | 68% | 80% | 55390 | 151 | 0.00% | - |  $>$5h | - | 58221 | 5.11%
Average | - | 55493 | 63% | 85% | 68% | 77% | 55509 | 233 | 0.03% | - | - | - | 58372 | 5.19%
X-n129-k18 | _20S_1 | 28574 | 60% | 74% | 78% | 76% | 28675 | 28 | 0.35% | 28523 | 1670 | 59.6 | 29357 | 2.74%
_20S_2 | 29397 | 55% | 72% | 79% | 76% | 29932 | 354 | 1.82% | 29391 | 6230 | 17.6 | 30012 | 2.09%
_20S_3 | 29296 | 57% | 66% | 77% | 72% | 29868 | 172 | 1.95% | 29296 | 1894 | 11.0 | 30056 | 2.59%
_20S_4 | 29127 | 57% | 76% | 76% | 76% | 29587 | 108 | 1.58% | 29126 | 6979 | 64.6 | 29886 | 2.61%
_20S_5 | 28708 | 52% | 66% | 79% | 73% | 28977 | 53 | 0.94% | 28708 | 12182 | 229.8 | 29204 | 1.73%
Average | - | 29020 | 56% | 71% | 78% | 74% | 29408 | 143 | 1.33% | 29009 | 5791 | 76.5 | 29703 | 2.35%
X-n134-k13 | _20S_1 | 10916 | 57% | 85% | 79% | 82% | 11023 | 526 | 0.98% | - |  $>$5h | - | 11344 | 3.92%
_20S_2 | 10918 | 86% | 80% | 59% | 70% | 10934 | 40 | 0.15% | - |  $>$5h | - | 11256 | 3.10%
_20S_3 | 10899 | 63% | 87% | 76% | 82% | 10929 | 96 | 0.28% | - |  $>$5h | - | 11324 | 3.90%
_20S_4 | 10901 | 65% | 92% | 75% | 84% | 10916 | 39 | 0.14% | 10901 |  $>$5h | - | 11315 | 3.80%
_20S_5 | 10909 | 92% | 81% | 55% | 68% | 10913 | 49 | 0.04% | - |  $>$5h | - | 11377 | 4.29%
Average | - | 10909 | 73% | 85% | 69% | 77% | 10943 | 150 | 0.32% | - | - | - | 11323 | 3.80%
X-n139-k10 | _20S_1 | 13605 | 85% | 81% | 81% | 81% | 13605 | 60 | 0.00% | - |  $>$5h | - | 13815 | 1.54%
_20S_2 | 13624 | 89% | 100% | 80% | 90% | 13624 | 36 | 0.00% | 13624 | 6925 | 192.4 | 13819 | 1.43%
_20S_3 | 13602 | 91% | 92% | 78% | 85% | 13607 | 197 | 0.04% | 13595 | 13074 | 66.4 | 13856 | 1.87%
_20S_4 | 13624 | 86% | 100% | 82% | 91% | 13624 | 87 | 0.00% | - |  $>$5h | - | 13961 | 2.47%
_20S_5 | 13608 | 83% | 82% | 82% | 82% | 13619 | 135 | 0.08% | 13608 | 11745 | 87.0 | 13897 | 2.12%
Average | - | 13613 | 87% | 91% | 81% | 86% | 13616 | 103 | 0.02% | - | - | - | 13870 | 1.89%
X-n143-k07 | _20S_1 | 15708 | 87% | 100% | 89% | 95% | 15708 | 38 | 0.00% | - |  $>$5h | - | 16083 | 2.39%
_20S_2 | 15733 | 87% | 100% | 88% | 94% | 15733 | 13 | 0.00% | - |  $>$5h | - | 16231 | 3.17%
_20S_3 | 15730 | 93% | 100% | 82% | 91% | 15730 | 26 | 0.00% | - |  $>$5h | - | 16158 | 2.72%
_20S_4 | 15722 | 93% | 100% | 82% | 91% | 15722 | 56 | 0.00% | - |  $>$5h | - | 16386 | 4.22%
_20S_5 | 15684 | 69% | 50% | 88% | 69% | 15845 | 16 | 1.03% | - |  $>$5h | - | 16449 | 4.88%
Average | - | 15715 | 86% | 90% | 86% | 88% | 15748 | 30 | 0.21% | - | - | - | 16261 | 3.47%

Table 10: Results for instances with $N_{c}=20$ and Small (S) intervals.

$\mathcal{P}_{o}$ | $\mathcal{P}_{m}$ | $\mathcal{S}_{m}$ cost | $sim(\mathcal{S}_{o},\mathcal{S}_{m})$ | ML model metrics | Edge-fixing | Exact BaP | DACT
---|---|---|---|---|---|---|---
TNR | TPR | Accuracy | Cost | Time (s) | Gap | Cost | Time (s) | Ratio | Cost | Gap
X-n101-k25 | _20M_1 | 27709 | 63% | 77% | 75% | 76% | 28105 | 47 | 1.43% | 27709 | 550 | 11.7 | 28385 | 2.44%
_20M_2 | 27440 | 65% | 68% | 73% | 71% | 27646 | 64 | 0.75% | 27440 | 615 | 9.6 | 27696 | 0.93%
_20M_3 | 27530 | 70% | 81% | 72% | 77% | 27559 | 24 | 0.11% | 27530 | 983 | 41.0 | 28193 | 2.41%
_20M_4 | 27656 | 74% | 70% | 65% | 68% | 27767 | 11 | 0.40% | 27656 | 217 | 19.7 | 28413 | 2.74%
_20M_5 | 27226 | 67% | 76% | 75% | 76% | 27393 | 15 | 0.61% | 27226 | 223 | 14.9 | 27694 | 1.72%
Average | - | 27512 | 68% | 74% | 72% | 73% | 27694 | 32 | 0.66% | 27512 | 518 | 19.4 | 28076 | 2.05%
X-n106-k14 | _20M_1 | 26362 | 69% | 87% | 67% | 77% | 26467 | 28 | 0.40% | 26362 | 16266 | 580.9 | 26888 | 2.00%
_20M_2 | 26345 | 72% | 95% | 68% | 82% | 26437 | 24 | 0.35% | 26345 | 1522 | 63.4 | 26829 | 1.84%
_20M_3 | 26282 | 65% | 87% | 72% | 80% | 26442 | 17 | 0.61% | 26282 | 2024 | 119.1 | 26760 | 1.82%
_20M_4 | 26328 | 60% | 82% | 72% | 77% | 26353 | 18 | 0.09% | 26328 | 4543 | 252.4 | 26644 | 1.20%
_20M_5 | 26212 | 55% | 82% | 78% | 80% | 26299 | 11 | 0.33% | 26212 | 1928 | 175.3 | 26667 | 1.74%
Average | - | 26306 | 64% | 87% | 71% | 79% | 26400 | 20 | 0.36% | 26306 | 5257 | 238.2 | 26758 | 1.72%
X-n110-k13 | _20M_1 | 14943 | 76% | 74% | 73% | 74% | 15053 | 8 | 0.74% | 14943 | 167 | 20.9 | 15164 | 1.48%
_20M_2 | 15046 | 64% | 79% | 80% | 80% | 15102 | 30 | 0.37% | 15046 | 1616 | 53.9 | 15197 | 1.00%
_20M_3 | 14904 | 78% | 96% | 75% | 86% | 14981 | 6 | 0.52% | 14904 | 189 | 31.5 | 15131 | 1.52%
_20M_4 | 15018 | 65% | 84% | 84% | 84% | 15237 | 82 | 1.46% | 15018 | 363 | 4.4 | 15184 | 1.11%
_20M_5 | 15004 | 82% | 95% | 75% | 85% | 15018 | 10 | 0.09% | 15004 | 407 | 40.7 | 15408 | 2.69%
Average | - | 14983 | 73% | 86% | 77% | 82% | 15078 | 27 | 0.64% | 14983 | 548 | 30.3 | 15217 | 1.56%
X-n125-k30 | _20M_1 | 55433 | 56% | 85% | 74% | 80% | 55510 | 635 | 0.14% | 55668 |  $>$5h | - | 58555 | 5.63%
_20M_2 | 55593 | 48% | 81% | 80% | 81% | 55649 | 150 | 0.10% | 55563 | 3534 | 23.6 | 58829 | 5.82%
_20M_3 | 55966 | 55% | 81% | 73% | 77% | 56046 | 87 | 0.14% | 55918 | 15876 | 182.5 | 58710 | 4.90%
_20M_4 | 55251 | 66% | 82% | 63% | 73% | 55288 | 214 | 0.07% | 55147 | 12934 | 60.4 | 58736 | 6.31%
_20M_5 | 55272 | 47% | 80% | 79% | 80% | 55400 | 80 | 0.23% | - |  $>$5h | - | 57810 | 4.59%
Average | - | 55503 | 54% | 82% | 74% | 78% | 55579 | 233 | 0.14% | - | - | - | 58528 | 5.45%
X-n129-k18 | _20M_1 | 29301 | 53% | 76% | 80% | 78% | 29697 | 189 | 1.35% | 29301 | 2064 | 10.9 | 30306 | 3.43%
_20M_2 | 29203 | 61% | 75% | 71% | 73% | 29504 | 325 | 1.03% | 29169 | 4528 | 13.9 | 29736 | 1.83%
_20M_3 | 29368 | 60% | 69% | 73% | 71% | 29976 | 228 | 2.07% | 29653 |  $>$5h | - | 30326 | 3.26%
_20M_4 | 29426 | 48% | 74% | 84% | 79% | 30065 | 705 | 2.17% | 29412 | 8398 | 11.9 | 30069 | 2.19%
_20M_5 | 28556 | 62% | 71% | 71% | 71% | 29035 | 129 | 1.68% | 28556 | 4177 | 32.4 | 29568 | 3.54%
Average | - | 29171 | 57% | 73% | 76% | 74% | 29655 | 315 | 1.66% | - | - | - | 30001 | 2.85%
X-n134-k13 | _20M_1 | 10898 | 56% | 84% | 79% | 82% | 10939 | 38 | 0.38% | - |  $>$5h | - | 11409 | 4.69%
_20M_2 | 10942 | 56% | 88% | 81% | 85% | 10974 | 360 | 0.29% | - |  $>$5h | - | 11238 | 2.71%
_20M_3 | 10930 | 56% | 92% | 90% | 91% | 11024 | 137 | 0.86% | 11004 |  $>$5h | - | 11280 | 3.20%
_20M_4 | 10904 | 52% | 73% | 76% | 75% | 10925 | 30 | 0.19% | - |  $>$5h | - | 11398 | 4.53%
_20M_5 | 10712 | 54% | 72% | 74% | 73% | 10916 | 72 | 1.90% | - |  $>$5h | - | 10967 | 2.38%
Average | - | 10877 | 55% | 82% | 80% | 81% | 10956 | 127 | 0.73% | - | - | - | 11258 | 3.50%
X-n139-k10 | _20M_1 | 13545 | 70% | 80% | 80% | 80% | 13584 | 187 | 0.29% | 13545 | 12506 | 66.9 | 13811 | 1.96%
_20M_2 | 13618 | 70% | 90% | 83% | 87% | 13630 | 107 | 0.09% | 13618 | 6516 | 60.9 | 13783 | 1.21%
_20M_3 | 13591 | 66% | 93% | 89% | 91% | 13605 | 117 | 0.10% | - |  $>$5h | - | 13883 | 2.15%
_20M_4 | 13648 | 72% | 87% | 79% | 83% | 13690 | 320 | 0.31% | - |  $>$5h | - | 13820 | 1.26%
_20M_5 | 13621 | 82% | 86% | 71% | 79% | 13648 | 295 | 0.20% | - |  $>$5h | - | 13976 | 2.61%
Average | - | 13605 | 72% | 87% | 80% | 84% | 13631 | 205 | 0.20% | - | - | - | 13855 | 1.84%
X-n143-k07 | _20M_1 | 15722 | 92% | 100% | 77% | 89% | 15722 | 13 | 0.00% | - |  $>$5h | - | 16158 | 2.77%
_20M_2 | 15747 | 89% | 93% | 81% | 87% | 15768 | 11 | 0.13% | - |  $>$5h | - | 16183 | 2.77%
_20M_3 | 15709 | 73% | 71% | 86% | 79% | 15774 | 99 | 0.41% | - |  $>$5h | - | 16382 | 4.28%
_20M_4 | 15745 | 77% | 64% | 82% | 73% | 15745 | 47 | 0.00% | - |  $>$5h | - | 16254 | 3.23%
_20M_5 | 15616 | 73% | 74% | 88% | 81% | 15717 | 77 | 0.65% | - |  $>$5h | - | 16189 | 3.67%
Average | - | 15708 | 81% | 80% | 83% | 82% | 15745 | 49 | 0.24% | - | - | - | 16233 | 3.35%

Table 11: Results for instances with $N_{c}=20$ and Medium (M) intervals.

$\mathcal{P}_{o}$ | $\mathcal{P}_{m}$ | $\mathcal{S}_{m}$ cost | $sim(\mathcal{S}_{o},\mathcal{S}_{m})$ | ML model metrics | Edge-fixing | Exact BaP | DACT
---|---|---|---|---|---|---|---
TNR | TPR | Accuracy | Cost | Time (s) | Gap | Cost | Time (s) | Ratio | Cost | Gap
X-n101-k25 | _20L_1 | 27463 | 67% | 70% | 63% | 67% | 27637 | 107 | 0.63% | 27463 | 374 | 3.5 | 28221 | 2.76%
_20L_2 | 27507 | 66% | 69% | 70% | 70% | 27641 | 93 | 0.49% | 27507 | 196 | 2.1 | 28158 | 2.37%
_20L_3 | 27789 | 51% | 76% | 85% | 81% | 28245 | 50 | 1.64% | 27789 | 100 | 2.0 | 28369 | 2.09%
_20L_4 | 27837 | 53% | 65% | 76% | 71% | 28097 | 7 | 0.93% | 27837 | 707 | 101.0 | 28276 | 1.58%
_20L_5 | 27631 | 59% | 70% | 73% | 72% | 27733 | 21 | 0.37% | 27631 | 955 | 45.5 | 28194 | 2.04%
Average | - | 27645 | 59% | 70% | 73% | 72% | 27871 | 56 | 0.81% | 27645 | 466 | 30.8 | 28244 | 2.17%
X-n106-k14 | _20L_1 | 26348 | 66% | 87% | 76% | 82% | 26420 | 25 | 0.27% | - |  $>$5h | - | 26759 | 1.56%
_20L_2 | 26599 | 55% | 72% | 73% | 73% | 26792 | 171 | 0.73% | 26593 | 12168 | 71.2 | 26907 | 1.15%
_20L_3 | 26405 | 65% | 85% | 74% | 80% | 26655 | 97 | 0.95% | 26387 | 5847 | 60.3 | 26853 | 1.70%
_20L_4 | 26358 | 57% | 79% | 77% | 78% | 26520 | 199 | 0.61% | 26358 | 401 | 2.0 | 26871 | 1.95%
_20L_5 | 26357 | 62% | 74% | 71% | 73% | 26390 | 8 | 0.13% | - |  $>$5h | - | 26782 | 1.61%
Average | - | 26413 | 61% | 79% | 74% | 77% | 26555 | 100 | 0.54% | - | - | - | 26834 | 1.59%
X-n110-k13 | _20L_1 | 15011 | 77% | 75% | 69% | 72% | 15035 | 15 | 0.16% | 15011 | 231 | 15.4 | 15234 | 1.49%
_20L_2 | 15003 | 76% | 86% | 73% | 80% | 15226 | 9 | 1.49% | 15003 | 386 | 42.0 | 15160 | 1.05%
_20L_3 | 15062 | 59% | 78% | 83% | 81% | 15262 | 18 | 1.33% | 15062 | 307 | 17.1 | 15291 | 1.52%
_20L_4 | 15027 | 63% | 76% | 83% | 80% | 15150 | 49 | 0.82% | 15027 | 351 | 7.2 | 15193 | 1.10%
_20L_5 | 15066 | 65% | 88% | 85% | 87% | 15131 | 26 | 0.43% | 15066 | 1162 | 44.7 | 15203 | 0.91%
Average | - | 15034 | 68% | 81% | 79% | 80% | 15161 | 23 | 0.84% | 15034 | 487 | 25.4 | 15216 | 1.21%
X-n125-k30 | _20L_1 | 55584 | 57% | 73% | 69% | 71% | 55824 | 997 | 0.43% | - |  $>$5h | - | 57981 | 4.32%
_20L_2 | 56407 | 56% | 85% | 76% | 81% | 56870 | 379 | 0.82% | 56407 | 2428 | 6.4 | 59339 | 5.20%
_20L_3 | 55903 | 65% | 83% | 68% | 76% | 55898 | 181 | -0.01% | - |  $>$5h | - | 59042 | 5.62%
_20L_4 | 56451 | 61% | 76% | 63% | 70% | 56680 | 508 | 0.41% | - |  $>$5h | - | 58746 | 4.07%
_20L_5 | 55445 | 53% | 76% | 73% | 75% | 55567 | 100 | 0.22% | - |  $>$5h | - | 58035 | 4.67%
Average | - | 55958 | 58% | 79% | 70% | 74% | 56168 | 433 | 0.37% | - | - | - | 58629 | 4.77%
X-n129-k18 | _20L_1 | 29249 | 54% | 81% | 74% | 78% | 29428 | 286 | 0.61% | 29149 | 1455 | 5.1 | 30263 | 3.47%
_20L_2 | 29468 | 64% | 75% | 63% | 69% | 30008 | 380 | 1.83% | 29468 | 1557 | 4.1 | 30198 | 2.48%
_20L_3 | 29761 | 52% | 82% | 81% | 82% | 30170 | 306 | 1.37% | 29709 | 6152 | 20.1 | 30198 | 1.47%
_20L_4 | 28504 | 50% | 70% | 76% | 73% | 28766 | 59 | 0.92% | 28501 | 2751 | 46.6 | 29405 | 3.16%
_20L_5 | 28635 | 54% | 78% | 74% | 76% | 28940 | 900 | 1.07% | 28635 | 3614 | 4.0 | 29177 | 1.89%
Average | - | 29123 | 55% | 77% | 74% | 75% | 29462 | 386 | 1.16% | 29092 | 3106 | 16.0 | 29848 | 2.49%
X-n134-k13 | _20L_1 | 10934 | 56% | 86% | 83% | 85% | 11030 | 181 | 0.88% | - |  $>$5h | - | 11370 | 3.99%
_20L_2 | 10922 | 55% | 86% | 85% | 86% | 11073 | 622 | 1.38% | - |  $>$5h | - | 11343 | 3.85%
_20L_3 | 10987 | 54% | 85% | 82% | 84% | 11132 | 134 | 1.32% | - |  $>$5h | - | 11331 | 3.13%
_20L_4 | 10965 | 54% | 81% | 80% | 81% | 11048 | 238 | 0.76% | - |  $>$5h | - | 11276 | 2.84%
_20L_5 | 10736 | 56% | 74% | 70% | 72% | 10971 | 96 | 2.19% | 10736 | 12945 | 134.8 | 11264 | 4.92%
Average | - | 10909 | 55% | 82% | 80% | 81% | 11051 | 254 | 1.31% | - | - | - | 11317 | 3.75%
X-n139-k10 | _20L_1 | 13583 | 84% | 87% | 68% | 78% | 13597 | 154 | 0.10% | 13583 | 16053 | 104.2 | 13798 | 1.58%
_20L_2 | 13582 | 73% | 87% | 79% | 83% | 13612 | 36 | 0.22% | 13580 | 4350 | 120.8 | 13785 | 1.49%
_20L_3 | 13579 | 81% | 100% | 72% | 86% | 13597 | 33 | 0.13% | 13579 | 5595 | 169.5 | 13771 | 1.41%
_20L_4 | 13565 | 63% | 77% | 81% | 79% | 13662 | 407 | 0.72% | 13565 | 10501 | 25.8 | 13771 | 1.52%
_20L_5 | 13614 | 65% | 90% | 87% | 89% | 13628 | 64 | 0.10% | 13638 |  $>$5h | - | 13814 | 1.47%
Average | - | 13585 | 73% | 88% | 77% | 83% | 13619 | 139 | 0.25% | - | - | - | 13778 | 1.50%
X-n143-k07 | _20L_1 | 15799 | 88% | 91% | 78% | 85% | 15814 | 23 | 0.09% | - |  $>$5h | - | 16471 | 4.25%
_20L_2 | 15705 | 89% | 75% | 76% | 76% | 15715 | 76 | 0.06% | - |  $>$5h | - | 16193 | 3.11%
_20L_3 | 15815 | 71% | 52% | 82% | 67% | 15886 | 19 | 0.45% | - |  $>$5h | - | 16432 | 3.90%
_20L_4 | 15816 | 82% | 78% | 81% | 80% | 15879 | 74 | 0.40% | - |  $>$5h | - | 16373 | 3.52%
_20L_5 | 15580 | 89% | 100% | 79% | 90% | 15580 | 13 | 0.00% | - |  $>$5h | - | 16190 | 3.92%
Average | - | 15743 | 84% | 79% | 79% | 79% | 15775 | 41 | 0.20% | - | - | - | 16332 | 3.74%

Table 12: Results for instances with $N_{c}=20$ and Large (L) intervals.

$\mathcal{P}_{o}$ | $\mathcal{P}_{m}$ | $\mathcal{S}_{m}$ cost | $sim(\mathcal{S}_{o},\mathcal{S}_{m})$ | ML model metrics | Edge-fixing | Exact BaP | DACT
---|---|---|---|---|---|---|---
TNR | TPR | Accuracy | Cost | Time (s) | Gap | Cost | Time (s) | Ratio | Cost | Gap
X-n101-k25 | _30S_1 | 27645 | 73% | 79% | 69% | 74% | 27759 | 40 | 0.41% | 27645 | 247 | 6.2 | 28109 | 1.68%
_30S_2 | 27709 | 71% | 72% | 72% | 72% | 27838 | 33 | 0.47% | 27709 | 254 | 7.7 | 28579 | 3.14%
_30S_3 | 27485 | 78% | 77% | 66% | 72% | 27606 | 89 | 0.44% | 27485 | 256 | 2.9 | 28104 | 2.25%
_30S_4 | 27620 | 84% | 85% | 66% | 76% | 27712 | 8 | 0.33% | 27620 | 47 | 5.9 | 28422 | 2.90%
_30S_5 | 27350 | 68% | 87% | 79% | 83% | 27431 | 13 | 0.30% | 27350 | 87 | 6.7 | 27883 | 1.95%
Average | - | 27562 | 75% | 80% | 70% | 75% | 27669 | 37 | 0.39% | 27562 | 178 | 5.9 | 28219 | 2.38%
X-n106-k14 | _30S_1 | 26346 | 64% | 94% | 73% | 84% | 26433 | 19 | 0.33% | 26346 | 84 | 4.4 | 26900 | 2.10%
_30S_2 | 26440 | 60% | 80% | 67% | 74% | 26457 | 239 | 0.06% | 26419 | 5459 | 22.8 | 26932 | 1.86%
_30S_3 | 26424 | 60% | 85% | 71% | 78% | 26573 | 422 | 0.56% | 26423 | 903 | 2.1 | 26787 | 1.37%
_30S_4 | 26389 | 73% | 88% | 61% | 75% | 26400 | 53 | 0.04% | 26386 | 752 | 14.2 | 26875 | 1.84%
_30S_5 | 26317 | 67% | 97% | 73% | 85% | 26326 | 8 | 0.03% | 26317 | 689 | 86.1 | 26669 | 1.34%
Average | - | 26383 | 65% | 89% | 69% | 79% | 26438 | 148 | 0.21% | 26378 | 1577 | 25.9 | 26833 | 1.70%
X-n110-k13 | _30S_1 | 15054 | 80% | 87% | 72% | 80% | 15109 | 61 | 0.37% | 15054 | 337 | 5.5 | 15257 | 1.35%
_30S_2 | 15002 | 72% | 96% | 78% | 87% | 15092 | 32 | 0.60% | 15002 | 56 | 1.8 | 15139 | 0.91%
_30S_3 | 14990 | 71% | 92% | 81% | 87% | 15059 | 47 | 0.46% | 14990 | 1664 | 35.4 | 15175 | 1.23%
_30S_4 | 14949 | 75% | 90% | 77% | 84% | 15123 | 12 | 1.16% | 14949 | 304 | 25.3 | 15158 | 1.40%
_30S_5 | 15031 | 72% | 93% | 76% | 85% | 15032 | 10 | 0.01% | 15031 | 412 | 41.2 | 15057 | 0.17%
Average | - | 15005 | 74% | 92% | 77% | 84% | 15083 | 32 | 0.52% | 15005 | 555 | 21.8 | 15157 | 1.01%
X-n125-k30 | _30S_1 | 55714 | 47% | 75% | 78% | 77% | 55813 | 309 | 0.18% | 55643 | 4647 | 15.0 | 58197 | 4.46%
_30S_2 | 56124 | 56% | 73% | 68% | 71% | 56119 | 181 | -0.01% | 56037 | 7085 | 39.1 | 59211 | 5.50%
_30S_3 | 55919 | 46% | 75% | 80% | 78% | 56014 | 422 | 0.17% | 55779 | 1061 | 2.5 | 59158 | 5.79%
_30S_4 | 55619 | 51% | 79% | 74% | 77% | 55685 | 297 | 0.12% | 55614 |  $>$5h | - | 58320 | 4.86%
_30S_5 | 55504 | 64% | 84% | 66% | 75% | 55539 | 86 | 0.06% | 55674 |  $>$5h | - | 58117 | 4.71%
Average | - | 55776 | 53% | 77% | 73% | 75% | 55834 | 259 | 0.10% | - | - | - | 58601 | 5.06%
X-n129-k18 | _30S_1 | 29566 | 57% | 76% | 72% | 74% | 30061 | 213 | 1.67% | 29533 | 2806 | 13.2 | 30314 | 2.53%
_30S_2 | 29771 | 63% | 80% | 69% | 75% | 30035 | 43 | 0.89% | 29771 | 1578 | 36.7 | 30305 | 1.79%
_30S_3 | 29588 | 57% | 82% | 75% | 79% | 29740 | 82 | 0.51% | 29588 | 3659 | 44.6 | 30372 | 2.65%
_30S_4 | 28892 | 61% | 83% | 74% | 79% | 29356 | 500 | 1.61% | 28892 | 1303 | 2.6 | 29612 | 2.49%
_30S_5 | 29253 | 52% | 81% | 80% | 81% | 29700 | 346 | 1.53% | 29240 | 9362 | 27.1 | 29825 | 1.96%
Average | - | 29414 | 58% | 80% | 74% | 77% | 29778 | 237 | 1.24% | 29405 | 3742 | 24.8 | 30086 | 2.28%
X-n134-k13 | _30S_1 | 10925 | 89% | 93% | 53% | 73% | 10925 | 30 | 0.00% | - |  $>$5h | - | 11333 | 3.73%
_30S_2 | 10962 | 86% | 80% | 53% | 67% | 10973 | 53 | 0.10% | - |  $>$5h | - | 11409 | 4.08%
_30S_3 | 10960 | 56% | 87% | 79% | 83% | 11012 | 211 | 0.47% | - |  $>$5h | - | 11365 | 3.70%
_30S_4 | 10874 | 60% | 88% | 75% | 82% | 10949 | 366 | 0.69% | - |  $>$5h | - | 11294 | 3.86%
_30S_5 | 10903 | 95% | 100% | 51% | 76% | 10903 | 42 | 0.00% | - |  $>$5h | - | 11406 | 4.61%
Average | - | 10925 | 77% | 90% | 62% | 76% | 10952 | 140 | 0.25% | - | - | - | 11361 | 4.00%
X-n139-k10 | _30S_1 | 13610 | 91% | 91% | 64% | 78% | 13722 | 127 | 0.82% | 13610 | 13075 | 103.0 | 13831 | 1.62%
_30S_2 | 13655 | 81% | 83% | 72% | 78% | 13835 | 351 | 1.32% | 13655 | 3380 | 9.6 | 14047 | 2.87%
_30S_3 | 13623 | 89% | 87% | 67% | 77% | 13659 | 204 | 0.26% | 13623 | 7294 | 35.8 | 13730 | 0.79%
_30S_4 | 13621 | 77% | 97% | 81% | 89% | 13632 | 40 | 0.08% | - |  $>$5h | - | 13724 | 0.76%
_30S_5 | 13599 | 79% | 96% | 79% | 88% | 13610 | 48 | 0.08% | - |  $>$5h | - | 13812 | 1.57%
Average | - | 13622 | 83% | 91% | 73% | 82% | 13692 | 154 | 0.51% | - | - | - | 13829 | 1.52%
X-n143-k07 | _30S_1 | 15738 | 86% | 100% | 89% | 95% | 15738 | 9 | 0.00% | - |  $>$5h | - | 16338 | 3.81%
_30S_2 | 15822 | 85% | 83% | 87% | 85% | 15855 | 216 | 0.21% | - |  $>$5h | - | 16463 | 4.05%
_30S_3 | 15825 | 89% | 81% | 84% | 83% | 15972 | 34 | 0.93% | - |  $>$5h | - | 16429 | 3.82%
_30S_4 | 15707 | 91% | 83% | 82% | 83% | 15712 | 9 | 0.03% | - |  $>$5h | - | 16243 | 3.41%
_30S_5 | 15677 | 65% | 50% | 92% | 71% | 15833 | 14 | 1.00% | - |  $>$5h | - | 16169 | 3.14%
Average | - | 15754 | 83% | 79% | 87% | 83% | 15822 | 56 | 0.43% | - | - | - | 16328 | 3.65%

Table 13: Results for instances with $N_{c}=30$ and Small (S) intervals.

$\mathcal{P}_{o}$ | $\mathcal{P}_{m}$ | $\mathcal{S}_{m}$ cost | $sim(\mathcal{S}_{o},\mathcal{S}_{m})$ | ML model metrics | Edge-fixing | Exact BaP | DACT
---|---|---|---|---|---|---|---
TNR | TPR | Accuracy | Cost | Time (s) | Gap | Cost | Time (s) | Ratio | Cost | Gap
X-n101-k25 | _30M_1 | 27849 | 57% | 66% | 75% | 71% | 28118 | 110 | 0.97% | 27830 | 244 | 2.2 | 28118 | 0.97%
_30M_2 | 27660 | 60% | 67% | 72% | 70% | 27964 | 66 | 1.10% | 27660 | 91 | 1.4 | 28338 | 2.45%
_30M_3 | 27699 | 69% | 69% | 72% | 71% | 27718 | 8 | 0.07% | 27699 | 89 | 11.1 | 28401 | 2.53%
_30M_4 | 27724 | 60% | 67% | 71% | 69% | 27843 | 67 | 0.43% | 27724 | 149 | 2.2 | 28388 | 2.40%
_30M_5 | 27340 | 68% | 70% | 76% | 73% | 27375 | 6 | 0.13% | 27340 | 642 | 107.0 | 28139 | 2.92%
Average | - | 27654 | 63% | 68% | 73% | 71% | 27804 | 51 | 0.54% | 27651 | 243 | 24.8 | 28277 | 2.25%
X-n106-k14 | _30M_1 | 26419 | 61% | 66% | 60% | 63% | 26526 | 76 | 0.41% | 26419 | 599 | 7.9 | 26892 | 1.79%
_30M_2 | 26550 | 52% | 66% | 71% | 69% | 26741 | 312 | 0.72% | 26579 |  $>$5h | - | 26804 | 0.96%
_30M_3 | 26437 | 63% | 81% | 74% | 78% | 26659 | 73 | 0.84% | 26656 |  $>$5h | - | 26805 | 1.39%
_30M_4 | 26446 | 56% | 73% | 70% | 72% | 26731 | 769 | 1.08% | - |  $>$5h | - | 26621 | 0.66%
_30M_5 | 26333 | 63% | 89% | 76% | 83% | 26419 | 7 | 0.33% | - |  $>$5h | - | 26779 | 1.69%
Average | - | 26437 | 59% | 75% | 70% | 73% | 26615 | 247 | 0.67% | - | - | - | 26780 | 1.30%
X-n110-k13 | _30M_1 | 15183 | 81% | 71% | 65% | 68% | 15228 | 8 | 0.30% | 15183 | 339 | 42.4 | 15443 | 1.71%
_30M_2 | 15075 | 83% | 80% | 66% | 73% | 15079 | 9 | 0.03% | 15075 | 177 | 19.7 | 15502 | 2.83%
_30M_3 | 15129 | 70% | 86% | 78% | 82% | 15163 | 7 | 0.22% | 15129 | 150 | 21.4 | 15346 | 1.43%
_30M_4 | 14995 | 76% | 96% | 75% | 86% | 15093 | 41 | 0.65% | 14995 | 291 | 7.1 | 15040 | 0.30%
_30M_5 | 14910 | 77% | 100% | 76% | 88% | 14910 | 5 | 0.00% | 14910 | 387 | 77.4 | 15130 | 1.48%
Average | - | 15058 | 77% | 87% | 72% | 79% | 15095 | 14 | 0.24% | 15058 | 269 | 33.6 | 15292 | 1.55%
X-n125-k30 | _30M_1 | 55574 | 52% | 80% | 77% | 79% | 55711 | 892 | 0.25% | 55574 | 1425 | 1.6 | 58917 | 6.02%
_30M_2 | 56218 | 45% | 84% | 84% | 84% | 56292 | 114 | 0.13% | 56128 | 1280 | 11.2 | 59406 | 5.67%
_30M_3 | 56589 | 52% | 80% | 76% | 78% | 56691 | 685 | 0.18% | 56314 | 3800 | 5.5 | 59519 | 5.18%
_30M_4 | 55735 | 46% | 79% | 76% | 78% | 55793 | 86 | 0.10% | 55656 | 5232 | 60.8 | 58574 | 5.09%
_30M_5 | 55510 | 53% | 85% | 78% | 82% | 55558 | 476 | 0.09% | - |  $>$5h | - | 57880 | 4.27%
Average | - | 55925 | 50% | 82% | 78% | 80% | 56009 | 451 | 0.15% | - | - | - | 58859 | 5.25%
X-n129-k18 | _30M_1 | 29604 | 61% | 82% | 67% | 75% | 30105 | 324 | 1.69% | 29604 | 5594 | 17.3 | 30360 | 2.55%
_30M_2 | 29758 | 51% | 80% | 82% | 81% | 30408 | 91 | 2.18% | 29758 | 3348 | 36.8 | 30256 | 1.67%
_30M_3 | 29813 | 54% | 80% | 72% | 76% | 30221 | 89 | 1.37% | 29793 | 4689 | 52.7 | 30122 | 1.04%
_30M_4 | 28682 | 55% | 83% | 77% | 80% | 29212 | 122 | 1.85% | 28669 | 406 | 3.3 | 29629 | 3.30%
_30M_5 | 28249 | 48% | 72% | 77% | 75% | 28545 | 60 | 1.05% | 28249 | 3835 | 63.9 | 28878 | 2.23%
Average | - | 29221 | 54% | 79% | 75% | 77% | 29698 | 137 | 1.63% | 29215 | 3574 | 34.8 | 29849 | 2.16%
X-n134-k13 | _30M_1 | 10959 | 53% | 83% | 85% | 84% | 11039 | 36 | 0.73% | - |  $>$5h | - | 11168 | 1.91%
_30M_2 | 10977 | 52% | 80% | 81% | 81% | 11118 | 108 | 1.28% | - |  $>$5h | - | 11360 | 3.49%
_30M_3 | 10998 | 65% | 86% | 73% | 80% | 11139 | 372 | 1.28% | - |  $>$5h | - | 11464 | 4.24%
_30M_4 | 10942 | 58% | 90% | 80% | 85% | 11035 | 70 | 0.85% | - |  $>$5h | - | 11427 | 4.43%
_30M_5 | 10752 | 52% | 75% | 81% | 78% | 10907 | 60 | 1.44% | - |  $>$5h | - | 11086 | 3.11%
Average | - | 10926 | 56% | 83% | 80% | 81% | 11048 | 129 | 1.12% | - | - | - | 11301 | 3.43%
X-n139-k10 | _30M_1 | 13631 | 80% | 91% | 76% | 84% | 13742 | 133 | 0.81% | 13631 | 8248 | 62.0 | 13926 | 2.16%
_30M_2 | 13795 | 74% | 82% | 76% | 79% | 13932 | 585 | 0.99% | - |  $>$5h | - | 14235 | 3.19%
_30M_3 | 13598 | 86% | 95% | 68% | 82% | 13598 | 57 | 0.00% | 13598 | 10792 | 189.3 | 13834 | 1.74%
_30M_4 | 13617 | 66% | 90% | 87% | 89% | 13628 | 322 | 0.08% | 13617 | 7536 | 23.4 | 13927 | 2.28%
_30M_5 | 13560 | 70% | 87% | 82% | 85% | 13638 | 184 | 0.58% | 13560 | 16734 | 90.9 | 13710 | 1.11%
Average | - | 13640 | 75% | 89% | 78% | 83% | 13708 | 256 | 0.49% | - | - | - | 13926 | 2.09%
X-n143-k07 | _30M_1 | 15751 | 86% | 100% | 86% | 93% | 15751 | 7 | 0.00% | - |  $>$5h | - | 16292 | 3.43%
_30M_2 | 16039 | 69% | 63% | 89% | 76% | 16346 | 199 | 1.91% | - |  $>$5h | - | 16741 | 4.38%
_30M_3 | 15798 | 84% | 80% | 83% | 82% | 15869 | 16 | 0.45% | - |  $>$5h | - | 16912 | 7.05%
_30M_4 | 15690 | 91% | 84% | 79% | 82% | 15690 | 7 | 0.00% | - |  $>$5h | - | 16005 | 2.01%
_30M_5 | 15630 | 70% | 62% | 90% | 76% | 15692 | 15 | 0.40% | - |  $>$5h | - | 16165 | 3.42%
Average | - | 15782 | 80% | 78% | 85% | 82% | 15870 | 49 | 0.55% | - | - | - | 16423 | 4.06%

Table 14: Results for instances with $N_{c}=30$ and Medium (M) intervals.

$\mathcal{P}_{o}$ | $\mathcal{P}_{m}$ | $\mathcal{S}_{m}$ cost | $sim(\mathcal{S}_{o},\mathcal{S}_{m})$ | ML model metrics | Edge-fixing | Exact BaP | DACT
---|---|---|---|---|---|---|---
TNR | TPR | Accuracy | Cost | Time (s) | Gap | Cost | Time (s) | Ratio | Cost | Gap
X-n101-k25 | _30L_1 | 27736 | 61% | 76% | 75% | 76% | 28298 | 47 | 2.03% | 27736 | 555 | 11.8 | 28486 | 2.70%
_30L_2 | 27465 | 72% | 84% | 71% | 78% | 27590 | 13 | 0.46% | 27465 | 300 | 23.1 | 28045 | 2.11%
_30L_3 | 27809 | 66% | 70% | 70% | 70% | 28281 | 844 | 1.70% | 27809 | 126 | 0.1 | 28438 | 2.26%
_30L_4 | 27809 | 65% | 70% | 69% | 70% | 28156 | 12 | 1.25% | 27809 | 348 | 29.0 | 28358 | 1.97%
_30L_5 | 27267 | 65% | 82% | 73% | 78% | 27321 | 11 | 0.20% | 27267 | 364 | 33.1 | 27709 | 1.62%
Average | - | 27617 | 66% | 76% | 72% | 74% | 27929 | 185 | 1.12% | 27617 | 339 | 19.4 | 28207 | 2.13%
X-n106-k14 | _30L_1 | 26623 | 47% | 76% | 71% | 74% | 26874 | 666 | 0.94% | - |  $>$5h | - | 26976 | 1.33%
_30L_2 | 26502 | 58% | 78% | 62% | 70% | 26765 | 594 | 0.99% | 26494 | 6491 | 10.9 | 26907 | 1.53%
_30L_3 | 26345 | 59% | 82% | 66% | 74% | 26430 | 9 | 0.32% | 26345 | 74 | 8.2 | 26901 | 2.11%
_30L_4 | 26438 | 44% | 81% | 79% | 80% | 26710 | 90 | 1.03% | 26438 |  $>$5h | - | 26932 | 1.87%
_30L_5 | 26290 | 61% | 78% | 63% | 71% | 26406 | 18 | 0.44% | 26268 | 2157 | 119.8 | 26851 | 2.13%
Average | - | 26440 | 54% | 79% | 68% | 74% | 26637 | 275 | 0.75% | - | - | - | 26913 | 1.79%
X-n110-k13 | _30L_1 | 15269 | 66% | 74% | 67% | 71% | 15347 | 13 | 0.51% | 15269 | 795 | 61.2 | 15634 | 2.39%
_30L_2 | 15145 | 54% | 81% | 85% | 83% | 15363 | 144 | 1.44% | 15145 | 635 | 4.4 | 15297 | 1.00%
_30L_3 | 15076 | 69% | 89% | 71% | 80% | 15162 | 59 | 0.57% | 15076 | 252 | 4.3 | 15286 | 1.39%
_30L_4 | 14945 | 63% | 80% | 73% | 77% | 15050 | 201 | 0.70% | 14945 | 3822 | 19.0 | 15123 | 1.19%
_30L_5 | 15015 | 78% | 86% | 63% | 75% | 15134 | 21 | 0.79% | 15015 | 94 | 4.5 | 15248 | 1.55%
Average | - | 15090 | 66% | 82% | 72% | 77% | 15211 | 88 | 0.80% | 15090 | 1120 | 18.7 | 15318 | 1.51%
X-n125-k30 | _30L_1 | 56435 | 49% | 83% | 74% | 79% | 56463 | 622 | 0.05% | - |  $>$5h | - | 58481 | 3.63%
_30L_2 | 56372 | 58% | 82% | 65% | 74% | 56422 | 401 | 0.09% | - |  $>$5h | - | 59140 | 4.91%
_30L_3 | 56386 | 57% | 88% | 70% | 79% | 56210 | 312 | -0.31% | 56072 | 2397 | 7.7 | 58901 | 4.46%
_30L_4 | 56432 | 50% | 86% | 73% | 80% | 56494 | 702 | 0.11% | - |  $>$5h | - | 59352 | 5.17%
_30L_5 | 55514 | 46% | 82% | 72% | 77% | 55517 | 337 | 0.01% | 55453 | 15245 | 45.2 | 57751 | 4.03%
Average | - | 56228 | 52% | 84% | 71% | 78% | 56221 | 475 | -0.01% | - | - | - | 58725 | 4.44%
X-n129-k18 | _30L_1 | 29989 | 52% | 74% | 75% | 75% | 30723 | 136 | 2.45% | 29985 | 4123 | 30.3 | 30941 | 3.17%
_30L_2 | 30260 | 60% | 75% | 71% | 73% | 30736 | 72 | 1.57% | 30260 | 3099 | 43.0 | 31252 | 3.28%
_30L_3 | 30007 | 53% | 73% | 75% | 74% | 30656 | 85 | 2.16% | 30007 | 1201 | 14.1 | 30769 | 2.54%
_30L_4 | 29356 | 55% | 71% | 74% | 73% | 29944 | 65 | 2.00% | 29341 | 15778 | 242.7 | 30275 | 3.13%
_30L_5 | 28757 | 71% | 84% | 71% | 78% | 28836 | 19 | 0.27% | 28757 | 370 | 19.5 | 29535 | 2.71%
Average | - | 29674 | 58% | 75% | 73% | 74% | 30179 | 75 | 1.69% | 29670 | 4914 | 69.9 | 30554 | 2.97%
X-n134-k13 | _30L_1 | 11037 | 52% | 79% | 81% | 80% | 11125 | 337 | 0.80% | - |  $>$5h | - | 11627 | 5.35%
_30L_2 | 10974 | 52% | 88% | 87% | 88% | 11045 | 111 | 0.65% | - |  $>$5h | - | 11498 | 4.77%
_30L_3 | 10945 | 58% | 84% | 77% | 81% | 11043 | 39 | 0.90% | 10950 |  $>$5h | - | 11346 | 3.66%
_30L_4 | 10869 | 51% | 78% | 80% | 79% | 10940 | 76 | 0.65% | 10868 | 9388 | 123.5 | 11231 | 3.33%
_30L_5 | 10926 | 53% | 84% | 85% | 85% | 10994 | 161 | 0.62% | - |  $>$5h | - | 11412 | 4.45%
Average | - | 10950 | 53% | 83% | 82% | 82% | 11029 | 145 | 0.72% | - | - | - | 11423 | 4.31%
X-n139-k10 | _30L_1 | 13564 | 79% | 93% | 73% | 83% | 13583 | 95 | 0.14% | - |  $>$5h | - | 13854 | 2.14%
_30L_2 | 13696 | 72% | 92% | 77% | 85% | 13720 | 139 | 0.18% | 13696 | 9395 | 67.6 | 14082 | 2.82%
_30L_3 | 13648 | 77% | 94% | 75% | 85% | 13667 | 177 | 0.14% | 13648 | 10780 | 60.9 | 13859 | 1.55%
_30L_4 | 13580 | 61% | 79% | 82% | 81% | 13599 | 99 | 0.14% | 13580 | 9597 | 96.9 | 13669 | 0.66%
_30L_5 | 13593 | 78% | 96% | 75% | 86% | 13604 | 132 | 0.08% | - |  $>$5h | - | 13876 | 2.08%
Average | - | 13616 | 73% | 91% | 76% | 84% | 13635 | 128 | 0.14% | - | - | - | 13868 | 1.85%
X-n143-k07 | _30L_1 | 16065 | 78% | 87% | 85% | 86% | 16137 | 1297 | 0.45% | - |  $>$5h | - | 16566 | 3.12%
_30L_2 | 16110 | 70% | 64% | 86% | 75% | 16273 | 181 | 1.01% | - |  $>$5h | - | 16474 | 2.26%
_30L_3 | 15856 | 85% | 90% | 80% | 85% | 15878 | 55 | 0.14% | - |  $>$5h | - | 16364 | 3.20%
_30L_4 | 15712 | 91% | 100% | 77% | 89% | 15712 | 21 | 0.00% | - |  $>$5h | - | 16148 | 2.77%
_30L_5 | 15676 | 69% | 70% | 89% | 80% | 15704 | 11 | 0.18% | - |  $>$5h | - | 16079 | 2.57%
Average | - | 15884 | 79% | 82% | 83% | 83% | 15941 | 313 | 0.36% | - | - | - | 16326 | 2.79%

Table 15: Results for instances with $N_{c}=30$ and Large (L) intervals.