 algorithm [Williams1992] and sampling which is then put into practice for the decoding.
greedy search or a beam-search procedure.
Despite the increasing performances, no ML model competes with Concorde nor the LKH algorithm. However, they are nevertheless able to find a feasible solution far more quickly by leveraging learned knowledge. Once the model has been trained, [Kool, van Hoof, and Welling2018] reported that approximate solutions with an average optimality gap of 4.53% can be found in 6 seconds for a data-set of 10000 euclidean TSPs of 100 nodes. For comparison, Concorde was able to solve the same instances at optimality in three minutes. By integrating a sampling selection, [Kool, van Hoof, and Welling2018] could reduce the optimality gap at 2.26% but at the expense of an execution time of one hour.
Interestingly, these recent ML approaches make use of various construction techniques (beam-search, active search, sampling, 2-OPT, etc.) but without discussing how they balanced the trade-off between performance and execution time. While spending more time in the search procedure will improve the performance, it will also increase the execution time. Finding an appropriate balance between both is only mentioned by [Joshi, Laurent, and Bresson2019] who identify it as a future challenge. Moreover, none of these papers discuss the learning accuracy of their learning component.
That being said, the development of ML approaches for the TSP has put a strong focus on improving the learning phase. The search phase was only done by simple methods, although there exists a myriad of more refined search procedures in the literature, such as simulated annealing [Kirkpatrick, Gelatt, and Vecchi1983], tabu search [Glover and Laguna1998], large neighbourhood search [Pisinger and Ropke2010], and many others [Aarts and Lenstra2003].
Based on these observations, our motivation is to provide more tools in order to help researchers make more informed choices when designing ML approaches for tackling COPs, in general. This paper answers this question by proposing a new metric for evaluating the pure learning component of ML models. This metric is complementary to the optimality gap, which, while commonly used, also suffers from some shortcomings.
The optimality gap, defined as the relative distance between an approximate solution and the optimal solution, is a standard and widely-used metric for evaluating approaches that solve COPs. Its main advantage is its simplicity, combined with its practical use (the performance of a model applied on a specific problem is summarized into a single value). It gives a good sense of how far we are from the optimal solution and how efficient the model is for finding the best solution. When the problem is still open and the optimal solution has not yet been proven, a relative gap can be computed using the best known solution as a baseline or using a dual bound, such as the linear relaxation or the Help-Karp lower bound for the TSP. The focus of such metrics is put on the quality of the solution where a solution is abstracted through a sequence of decisions.
[Lin2004], the BLEU metric for translation [Papineni et al.2002], or the ELO rating for reinforcement learning agents playing games [Silver et al.2017]. However, only the optimality gap has been used so far as the main evaluating metric for ML approaches tackling the TSP. Although the optimality gap also provides a comparison with a ground truth (i.e., the algorithm providing the optimal solution), we argue that this metric is not sufficient to evaluate the performance of ML approaches to COPs as it measures both the learning and search components together. If poor results are achieved, one does not really know whether the issues come from an insufficient learning ability or a weak search mechanism.
This problem is illustrated in Fig. 1. The left figure presents the optimal solution of a TSP (non labelled edges have a weight of 1). On the right, a sub-optimal solution is proposed. Although only one non-optimal decision has been done (the second misplaced edge being forced to complete the tour), the optimality gap is huge. When considering only the optimality gap, one might believe that a new DL architecture could help. However, the quasi-totality of edges were guessed correctly and a simple search heuristic would have fixed the problem. For this reason, we advocate the use of a second metric for evaluating ML models dedicated to solve COPs. The idea is to have a metric able to compare the accuracy of the learning component against a ground truth, independently of the search component.
(a) Optimality gap of 0%.
(b) Optimality gap of 27.3%.
Figure 1: Pathological example of a bad decision in the TSP.
This section describes ratio of optimal decisions (ROD), a new metric we introduce for evaluating the learning component of ML approaches dedicated to solve COPs. Its focus is not on the quality of the solution, such as the optimality gap, but rather on the quality of the individual decisions, which better reflects how good a model is performing against a ground truth.
When solving a COP, one has to assign a specific value to a set of variables in order to find a feasible assignment that minimizes (resp. maximizes) an objective function. A simple and general way to model such a problem is to use a Dynamic Programming (DP) formulation. The idea is to simplify the problem by breaking it down into a sequence of decision steps. At each step, a new variable is selected and assigned a value until all the variables have been set. A cost is induced after each assignment and the total cost, when all decisions are taken, corresponds to the outcome of the objective function. A fundamental property of DP is the so-called principle of optimality, introduced by [Bellman1966] : a sequence of optimal decisions done at each step gives the optimal solution of the complete problem.
In the ML terminology, an optimal oracle can be considered as a model having a perfect knowledge, which means that it never takes sub-optimal decisions. Let us assume that we have a parametrized oracle that is able to take each optimal decision with a certain accuracy. Based on this idea, the ROD metric we introduce is defined as follows.
Let P be a COP, M be a model dedicated to solve P, and Ω be a parametrized oracle that is able to take each optimal decision with a certain accuracy. The ROD of M regarding Ω is defined as the ratio of optimal decisions that is required by Ω in order to equal the optimality gap of M on P.
Let us consider the TSP of Fig. 1 that contains 13 decisions, and let us assume that the solution of Fig. (b)b has been obtained using a parametrized oracle Ω. Models having an optimality gap of 27.3% will have a ROD of 12/13=92.31% regarding Ω because they will have the same performance as a parametrized oracle that has made 12 optimal decisions among 13.
The goal of ROD is to measure the break-even ratio of a parametrized oracle, where its performance equals the one of the model we want to evaluate. This ratio will indicate that the model has similar performances as a function of having a parametrized level of knowledge. By doing so, the model is directly compared with a ground truth only, without integrating the difficulty of the problem. Indeed, if both of them make the same bad decision, the optimality gap increase will remain the same for both.
The last question remaining is how ROD can be computed. This question is tightly related to the construction of the parametrized oracle. Two design choices are required for that: (1) given a ratio, how do we select the decisions that will be optimal; and (2) when a non-optimal decision is made, which one must be selected? These questions are discussed in the next section.
The formulation proposed is generic, in the sense that it can be used for any COP. Let us consider a COP P=⟨X,D,C,O⟩ where X is the set of variables, D the set of domains restricting the values that variables x∈X can take, C the set of constraints and O the objective function.
The first step is to design a DP model associated to the COP. It requires adequately defining the tuple ⟨S,A,T,K⟩ where S is the set of all the possible states that can be generated, A is the set of possible actions, T:S×A→S is the transition function leading the system to move from a state to another one given the action taken and K:S×A→R is the cost function returning the cost of every action taken in a given state. The DP model of the parametrized oracle is defined as follows.
Let n be the number of variables x∈X and σ=⟨x1,…,xn⟩ be an arbitrarily ordered sequence of these variables. A state s∈S corresponds to the first non-assigned variable xi∈σ, with i∈{1,…,n}, or ⊥ if all of them are assigned. The initial state is then x1 and a state is terminal when s=⊥.
An action as done at state s is defined as the selection of a value for its assignment to the variable referenced by s. The action is valid if and only if (1) it is in the domain of the variable (as∈D(s)), and (2) its assignment does not violate any constraint c∈C.
The transition function is defined as T(s,as)=s←as, where x←a is a function assigning the value a to the variable