Hexaly vs Gurobi on the Traveling Salesman Problem (TSP)

Benchmark Transportation Routing

Frédéric Senior Optimization Scientist June 2, 2024

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 (TSP), Hexaly reaches a 0.3% average gap to the best known solutions in the research 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 but 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, expressed in %, to the optimal solution.

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 Linear Programming approach to the TSP introduced by Dantzig, Fulkerson, and Johnson. This modeling approach 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. The Gurobi model is detailed here.

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 in % to the optimal solution as reported here by the research. We use Hexaly 13.0 and Gurobi 11.0, a state-of-the-art Mixed Integer Linear Programming (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 finds near-optimal solutions for instances with 10,000 cities, whereas Gurobi fails to find quality solutions for instances with more than 300 cities.

Conclusion

Hexaly offers an innovative modeling approach based on list variables. This approach simplifies the mathematical modeling of the Traveling Salesman Problem (TSP) compared to traditional MILP solvers like Gurobi. 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.