Hexaly vs Gurobi on the Traveling Salesman Problem (TSP)
The Traveling Salesman Problem (TSP) is defined as follows: given a set of cities and distances for all pairs of cities, find a roundtrip of minimal total length visiting each city exactly once.
Hexaly Optimizer reaches an average optimality gap of 0.25% in 60 seconds of running time on Traveling Salesman Problem instances with up to 2,000 cities. This page illustrates how Hexaly Optimizer outperforms traditional general-purpose optimization solvers, like Gurobi 9.1, on this challenging problem.
Input data
The TSPLIB is the reference repository for TSP instances. It includes many variants of the TSP. In this benchmark, we compare the results obtained by Hexaly and Gurobi on the 109 symmetric instances of the TSPLIB from 14 to 18,512 cities. Since all these instances have a known optimum, our metric will be the relative gap to optimality.
Mathematical models of the Traveling Salesman Problem (TSP)
Mixed-Integer Linear Programming (MILP) model
The results reported for Gurobi are obtained with the canonical Mixed Integer Programming approach to the TSP, introduced by Dantzig, Fulkerson, and Johnson. It consists of a quadratic number of binary variables representing the succession of two cities in the tour and an exponential number of subtour elimination constraints, which are lazily added to the model.
Hexaly model
The Hexaly model has only one list variable representing the permutation of cities. The first element of the list is the first city visited, and so on. The distance between consecutive cities is retrieved thanks to an at operator. Compared to MIP models, the Hexaly model is straightforward, almost literally translated from the natural TSP definition. Besides, it is compact: there is no need for a constraint generation subroutine. We will show that it also produces much better results.
function model() {
// List variable: cities[i] is the index of the ith city in the tour
cities <- list(nbCities);
// All cities must be visited once
constraint count(cities) == nbCities;
// Minimize the total distance
obj <- sum(1..nbCities-1, i => distanceWeight[cities[i-1]][cities[i]])
+ distanceWeight[cities[nbCities-1]][cities[0]];
minimize obj;
}Gurobi and Hexaly results on the Traveling Salesman Problem (TSP)
We compare both solvers’ performance with three solving times: 1 minute, 10 minutes, and 1 hour. At the end of the running time, we measure the gap to the optimal solution in %. We use Hexaly 12.0 and Gurobi 9.1, known as a state-of-the-art MIP solver. Both are used with default parameters. We ran them on a server equipped with an Intel Core i7-7700K processor (4 cores, 4.5GHz, 8MB cache) and 32GB RAM.
Below are charts showing the results. The instance size is on a horizontal scale, and the gap to the optimal value is on the vertical axis. When a solver doesn’t obtain any feasible solution within the time limit, the failure is reported with a square (■) with the highest displayed gap value. We focus on instances with less than 2,000 cities for a 1-minute time limit on the first chart below.
For instances with less than 200 cities, both solvers can compute near-optimal solutions within 1 minute. In contrast, for larger instances, Gurobi doesn’t obtain any feasible solution, while Hexaly keeps on delivering near-optimal solutions. The second chart below, on which we report the results for instances with up to 20,000 cities, illustrates Hexaly’s scalability. With 1 hour of running time, Gurobi fails to get solutions on instances with less than 1,000 cities. Hexaly provides a solution with gap 1.45% for the instance with 18,512 cities.
Conclusion
Hexaly offers an innovative modeling approach based on list variables, which made the mathematical modeling of the Traveling Salesman Problem (TSP) much simpler than traditional MIP solvers. The resulting model for the TSP is compact and natural while providing much better results, particularly for large instances and limited running times.
You can find the complete model of the Traveling Salesman Problem (TSP) and many other Vehicle Routing problems in Python, Java, C#, and C++ in our Example Tour.
Are you interested in trying it out? Get free trial licenses here. In the meantime, feel free to contact us; we will be glad to discuss your optimization problems.