IEEE Computational Intelligence Magazine - August 2023 - 16

FIGURE 1 Illustrations of the two solver design paradigms. (a) Human-centered traditional paradigm. (b) Learning-centered NCO.
approaches are not adept at handling large-size problem instances
and structural problem instances (e.g., clustered TSP instances).
Second, a potential benefitofNCO solversmight be theirefficiency
(both in time and energy). For example, to achieve the
same solution quality on small-size randomly generated problem
instances, NCO solvers consume at most one-tenth ofthe resources
consumed by traditional solvers. Third, when the training
instances cannot sufficiently represent the target cases ofthe problem,
both NCO solvers and tuned traditional solvers exhibit performance
degradation, although the degradation is more dramatic
for the former.
The remainder of the article is organized as follows. Section
II briefly reviews the literature on NCO. Section III
explains the design of the comparative study. Section IV
presents the experimental results and analysis. Finally, concluding
remarks are given in Section V.
II. Review of Neural Combinatorial Optimization
Before reviewing NCO, it is useful to first quickly recap typical
COsolvers. In general, COsolvers include exact ones and approximate
ones. Typical exact solvers are based on the branch-andbound
techniques that explore the solution space by branching
into sub-problems and then filtering the set of possible solutions
based on the upper and lower estimated bounds of the optimal
solution. Typical approximate CO solvers are heuristics, which
can be further roughly classified into constructive heuristics and
improvement heuristics. The former incrementally builds a solution
to a CO problem by adding one element at a time until a
complete solution is obtained. In contrast, the latter improves
upon a given solution by iteratively modifying it. The way of
modifying a given solution is called a move operator. In recent
decades, a lot ofmove operators have been proposed for different
CO problems. For a comprehensive overview ofCO, interested
readers are referred to [1].
It is worth noting that the applications ofneural networks to
solve CO problems are actually not new. The earlier works [31]
from the 80 s in the last century focused on using Hopfield neural
networks (HNNs) to solve small-size TSP instances, which were
later extended to other problems [32]. The main limitation of
HNN-based approaches is that they need to use a separate network
to solve each problem instance.
The termNCO refers to the series ofworks that utilize DL to
learn a solver (model) to solve a set ofdifferent problem instances.
According to the types of the learned solvers, the existing NCO
16 IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE | AUGUST 2023
approaches can be categorized into learning constructive heuristics
(LCH), learning improvement heuristics (LIH), and learning
hybrid solvers (LHS). As the names suggest, the solvers learned by
LCH approaches and LIH approaches are constructive heuristics
and improvement heuristics, respectively. Compared to traditional
heuristics, their main differences are that the heuristic rules are no
longer manually designed but are instead automatically learned.
For example, the well-known greedy constructive heuristic for
TSPs always selects the closest point for insertion, while LCH
approaches learn a deep neural network (DNN) to score each
point and finallyselectthe pointwiththe highestscore forinsertion.
Compared to the manually designed greedy heuristic rule,
the DNN model is trained with data and unnecessarily exhibits
greedy behavior. Finally, LHS approaches seek to learn solvers
that are hybrids oflearningmodels and traditional solvers. The following
sections will introduce these NCO approaches, mainly
focusing on the key works. For a comprehensive survey of this
area, interested readers are referred to [13], [33].
A. Learning Constructive Heuristics
1)Pointer Network-Based Approaches
As the seminal work, Vinyals et al. [27] introduced a sequence-tosequence
model, dubbed pointer network (Pr-Net), for solving
TSPs defined on the two-dimensional plane. Specifically, Pr-Net
is composed ofan encoder and a decoder, and both of them are
recurrent neural networks. Given a TSP instance, the encoder
parses all the nodes in it and outputs an embedding (a real-valued
vector) for each of them. Then, the decoder repeatedly uses an
attention mechanism, which has been successfully applied to
machine translation [11], to output a probability distribution over
these previously encoded nodes, eventually obtaining a permutation
over all the nodes, i.e., a solution to the input TSP instance.
This approach allows the network to be used for problem instances
with different sizes. However, Pr-Net is trained by supervised
learning (SL) with precomputed near-optimal TSP solutions as
labels. This could be a limiting factor, since in real-world applications
such solutions ofCO problems might be difficult to obtain.
To overcome the above limitation, Bello et al. [28] proposed
training Pr-Net with reinforcement learning (RL). In their implementation,
the tour length of the partial TSP solution is used as
the reward signal.
Another limitation of Pr-Net is that it treats the input as a
sequence, while many CO problems have no natural internal

IEEE Computational Intelligence Magazine - August 2023

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