How to Evaluate Machine Learning Approaches for Combinatorial Optimization: Application to the Travelling Salesman Problem

Understand

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.