How to Evaluate Machine Learning Approaches for Combinatorial
  Optimization: Application to the Travelling Salesman Problem
  Combinatorial optimization is the field devoted to the study and practice of
algorithms that solve NP-hard problems. As Machine Learning (ML) and deep
learning have popularized, several research groups have started to use ML to
solve combinatorial optimization problems, such as the well-known Travelling
Salesman Problem (TSP). Based on deep (reinforcement) learning, new models and
architecture for the TSP have been successively developed and have gained
increasing performances. At the time of writing, state-of-the-art models
provide solutions to TSP instances of 100 cities that are roughly 1.33% away
from optimal solutions. However, despite these apparently positive results, the
performances remain far from those that can be achieved using a specialized
search procedure. In this paper, we address the limitations of ML approaches
for solving the TSP and investigate two fundamental questions: (1) how can we
measure the level of accuracy of the pure ML component of such methods; and (2)
what is the impact of a search procedure plugged inside a ML model on the
performances? To answer these questions, we propose a new metric, ratio of
optimal decisions (ROD), based on a fair comparison with a parametrized oracle,
mimicking a ML model with a controlled accuracy. All the experiments are
carried out on four state-of-the-art ML approaches dedicated to solve the TSP.
Finally, we made ROD open-source in order to ease future research in the field.
