IEEE Computational Intelligence Magazine - August 2023 - 15

comprehensive evaluation protocol for further benchmarking
NCOapproachesincomparisontoother approaches.
I. Introduction
C
ombinatorial optimization (CO) concerns optimizing
an objective function by selecting a solution from
a finite solution set, with the latter encoding constraints
on the solution space. It has been involved in
numerous real-world applications in logistics, supply chains, and
energy [1]. From the perspective of computational complexity,
many CO problems are NP-hard due to their discrete and nonconvex
nature [2]. In recent decades, methods for solving CO
problems have been extensively developed and can be broadly categorized
into exact and approximate/heuristic/meta-heuristic
methods [3]. The former methods are guaranteed to optimally
solve CO problems but suffer from an exponential time complexity.
In contrast, the latter methods seek to find good (but not necessarily
optimal) solutions within reasonable computation time,
i.e., they trade optimality for computational efficiency.
In general, most (ifnot all) ofthe above methods are manually
designed. By analyzing the structure ofthe CO problem of
interest, domain experts would leverage the algorithmic techniques
that most effectively exploit this structure (e.g., proposed
in the literature) and then continuously refine these methods
(e.g., introducing new algorithmic techniques). Such a design
process heavily depends on domain expertise and could be
extremely expensive in terms of human time. For example,
although the well-known traveling salesman problem (TSP) [4]
has been studied for approximately 70 years, its methods [5],
[6], [7], [8], [9] are still being actively and relentlessly updated.
Inspired by the success ofdeep learning (DL) in fields such as
image classification [10], machine translation [11], and board
games [12], recently there has been a surge ofresearch interest in
utilizing DL, especially deep reinforcement learning (DRL), to
automatically learn effective methods for CO problems [13].
The resultant new paradigm is termed neural combinatorial optimization
(NCO) [14], [15]. For the sake of clarity, henceforth,
the optimization methods (either hand-engineered or automatically
learned) are called solvers and the ways to design solvers are
called design approaches. Compared to the traditional manual
approach, NCO exhibits a significant paradigm shift in solver
design. As illustrated in Figure 1, traditional solver design process
is human-centered, while NCO is a learning-centered paradigm
that develops a solver by training. The training process ofNCO
essentially calibrates the parameters of the solver (model).
Although this approach induces a greater offline computational
cost, the training process allows solver design to be conducted in
an automatedmanner and thus involves much less human effort.1
Despite the appealing features NCO might bring, its advantages
and disadvantages relative to other approaches have not been
1It is noted that NCO still requires human time and expertise to carefully construct
the training set, which should sufficiently represent the target use cases of
the learned solver. However, this is not an easy task. This point will be further
discussed in Section V.
clearly specified. More specifically, although numerous computational
experiments comparing NCO solvers with other solvers
have been conducted in NCO works, they are generally nonconclusive
for several reasons. First, it is often the case that the
state-of-the-art traditional solvers are missing in the comparison,
whichwould distort the conclusion and undermine the whole validation
process. For example, theGoogleOR-Tools [16] is widely
considered by NCO works [17], [18], [19], [20], [21] to be the
baseline traditional solver for the vehicle routing problems
(VRPs); however, it performs far worse than the state-of-the-art
solvers for VRPs [22]. Second, for traditional solvers, their default
configurations (parameter values) are used when comparing them
with NCO solvers learned from training sets. Such an approach
neglects the fact that, when a training set is available, the performance
of traditional solvers could also be significantly enhanced
by tuning their parameters [23], [24]. In practice, it is always desirable
to make full use of the available technologies to achieve the
best possible performance. In fact, with the help of the existing
open-source algorithm configuration tools [24], [25], [26],the
tuning processes oftraditional solvers can be easily automated with
little human effort involved. Third, the benchmark instances used
in the comparative studies are often quite limited in terms ofproblem
types and sizes, making it difficult to gain insights into how
these approaches would performon problem instances with different
characteristics. For example, for TSP, the main testbed problem
in NCO, most works have only reported results obtained on
randomly generated instances with up to 100 nodes [18], [20],
[27], [28], [29], [30]. In comparison, traditional TSP solvers are
generally tested on problem instances collected from distinct applications,
with up to tens ofthousands ofnodes [5], [6], [7], [8], [9].
To better understand the benefits and limitations ofNCO, this
work presents a more comprehensive empirical study. Specifically,
TSP is employed as the testbed problem, since it is the originally
oriented problem for many widely-used architectures in NCO
and thus the conclusions drawn from it could have strong implications
for other problems. Three recently developed NCO
approaches and three state-of-the-art traditional TSP solvers are
involved in the experiments. These solvers are compared on five
problem types with node numbers ranging from 50 to 10000. The
performance ofthe solvers is compared in five aspectsthatare critical
in practice, i.e., effectiveness, efficiency, stability, scalability, and
generalization ability. In particular, the energy efficiency (in terms
of electric power consumption) of the solvers is also investigated,
since energy consumption is being recognized as an important factor
for solver selection if the applications of solvers continue to
develop. To the best ofour knowledge, this is the first comparative
study ofNCO approaches and traditional solvers on TSPs that 1)
considers five different problem types, 2) involves problem instances
with up to 10000 nodes, 3) includes tuned traditional solvers in
the comparison, and 4) investigates five different performance
aspects including the energy consumption ofthe solvers.
The presented comprehensive empirical study has led to several
interesting findings. First, traditional solvers still significantly
outperformNCO solvers in finding high-quality solutions regardless
of problem types and sizes. In particular, current NCO
AUGUST 2023 | IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE 15
IEEE Computational Intelligence Magazine - August 2023

Table of Contents for the Digital Edition of IEEE Computational Intelligence Magazine - August 2023
