The traveling-salesman problem

The TSP is a famous problem in computer science. Given a list of cities and the shortest distance between each of them, the goal is to find the shortest path visiting all cities once and only once, and returning to the starting point. The following map illustrates a solution to the traveling-salesman problem, visiting some cities in Germany:

Image credit: https://commons.wikimedia.org/wiki/File:TSP_Deutschland_3.png

So we have an optimization problem with the following:

• An objective function: The cost of the path. This cost can be the total distance, but if the driver is only paid hourly, it may be more useful to use the total travel time as the objective to minimize.
• Constraints:
• Each city must be visited once and only once.
• The path must start and end in the same city.

Despite the straightforward formulation, this is an NP-hard problem. The only way to reach the exact solution in all cases is the brute-force approach, where you compute the shortest...