LocalSolver


Benchmark — 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. We illustrate on this page how LocalSolver 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 LocalSolver 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

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. These later ones are lazily added to the model.

The LocalSolver 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 LocalSolver 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;
}

Results

We compare both solvers' performance with three solving times: 1 minute, 10 minutes, 1 hour. At the end of the running time, we measure the gap to the optimal solution in %. We use LocalSolver 10.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 on the vertical axis. When a solver doesn't obtain any feasible solution within the time limit, the failure is reported with a cross (X) 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 LocalSolver keeps on delivering near-optimal solutions. On the second chart below, we report the results for instances with up to 20,000 cities. With 1 hour of running time, Gurobi fails to get solutions on instances with less than 1,000 cities. LocalSolver provides a solution with gap 4.88% for the instance with 18,512 cities. This illustrates the scalability of LocalSolver.

Conclusion

LocalSolver 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 in Python, Java, C#, and C++, and LSP in our Example Tour.

We are at your disposal to accompany you in the discovery of LocalSolver. Don't hesitate to contact us for any further information or support.

Contact us - Disclaimer - Privacy policy - Copyright 2021 LocalSolver