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.
On the Traveling Salesman Problem, Hexaly reaches an average optimality gap of 0.3% in 1 minute of running time on the TSPLIB research benchmark with instances up to 10,000 cities. This page illustrates how Hexaly outperforms traditional general-purpose optimization solvers, like Gurobi 11.0, on this seminal, challenging combinatorial optimization problem.
Input data
The TSPLIB is the reference repository for TSP instances, including many variants of the TSP. In this benchmark, we compare the results obtained by Hexaly and Gurobi on the 133 instances of the TSPLIB with up to 10,000 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 using 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, i => distanceWeight[cities[i-1]][cities[i]])
+ distanceWeight[cities[nbCities-1]][cities[0]];
minimize obj;
}Hexaly and Gurobi results on the Traveling Salesman Problem (TSP)
We compare both solvers’ performance in 1 minute of running time. At the end of the running time, we measure the gap to the optimal solution in %. We use Hexaly 12.5 and Gurobi 11.0, a state-of-the-art MILP solver. Both are used with default parameters. We ran them on a server equipped with an AMD Ryzen 7 7700 processor (8 cores, 3.8GHz, 8MB cache) and 32GB RAM. The table below presents the average gap between feasible solutions found by the solvers and the known optimal solutions.
| Hexaly 12.5 | Gurobi 11.0 | |
|---|---|---|
| 1 – 100 | 0.0 | 0.0 |
| 101 – 1000 | 0.2 | 28.4 |
| 1001 – 10000 | 1.0 | 100.0 |
Hexaly finds near-optimal solutions for instances with 10,000 cities, whereas Gurobi fails to find decent solutions for instances with more than 300 customers.
Conclusion
Hexaly offers an innovative modeling approach based on list variables, which simplifies the mathematical modeling of the Traveling Salesman Problem (TSP) compared to traditional MILP solvers. The resulting model is natural and compact while providing much better results, particularly for large-scale instances.
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 gladly discuss your optimization problems.