LocalSolver


Benchmark TSP

The travelling salesman problem is defined as follows: given a set of n cities and distances for each pair of cities, find a roundtrip of minimal total length visiting each city exactly once. The distance from city i to city j and the distance from city j to city i may be different.
We illustrate on this page how LocalSolver outperforms classical MIP solvers on this hard problem.


Data

The TSPLib is the reference repository for TSP instances. It includes many instances for several variants of the TSP.

In this benchmark we compare the results obtained by LocalSolver and its competitors for different solving times, on the 144 symmetric instances of the TSPLib. Since all these problems have a know optimum, our metric will be the relative gap to optimality.


Models

MIP model

The results reported below for commercial MIP solvers are obtained with the canonical Mixed Integer Programming approach to the Travelling Salesman problem, introduced by Dantzig, Fulkerson and Johnson. It consists in a quadratic number of binary variables representing the succession of two cities in the tour and an exponential number of subtour elimination constraints. The latter are added to the model in a lazy fashion.

LocalSolver model

The LocalSolver model only has 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, an advantage of this approach is that it is straightforward (almost literally translated from the natural TSP definition) and compact (no need of a constraint generation procedure). We will show that it also produces much better results.


function model() {
    // A list variable: cities[i] is the index of the ith city in the tour
    cities <- list(nbCities); 

    // All cities must be visited
    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;
}

LocalSolver vs. commercial MIP solvers

The LocalSolver model is already more straightforward and natural than MIP models, but does it provide better solutions ? Here we compare the performance of both models in an industrial context, where runtime must stay reasonable. To this end, we have measured the gap value regularly until 300 seconds. The comparison is made between LocalSolver 7.0 and a commercial MIP solver, both without any specific configuration or tuning.

Comparison on the symmetric instance set

Experiment parameters

Results

Below is a chart representing the results. The instance size is in a horizontal logarithmic scale and the gap to the best known solution on the vertical axis. Results for different time limits can be selected with the slider. When a solver could not obtain any feasible solution within the time limit, this failure is reported as an an 'x' with the highest displayed gap value.

We observe that for small instances all solvers are able to compute near-optimal solutions, whereas for medium and large size instances MIP solvers do not obtain any feasible solution within 5 minutes. It illustrate the all-or-nothing behaviour of this kind of approach: focused on the computation of lower bounds and optimality proofs, it can reach the allocated time-limit wihout feasible solution. We will see below that extending the time-limit does not fix this issue.

With LocalSolver, each instance has a feasible solution immediately and the gap gets improved as time increases: from a average gap of 0.5% after 10 seconds to an average gap of 0.2% after 5 minutes.

Extended runtime & instance sizes

Although a computation time of 5 minutes is often the maximum acceptable time in an industrial context, we report below the results obtained with a 1 hour time limit to see if it leads to different conclusions. For this benchmark we have considered TSPLib instances with up to 2400 cities.

Clearly the global picture remains the same. The tractability limit for MIP solvers is just shifted to around 400 cities while the trend observed for LocalSolver also applies for these extended runtime: feasible solutions are obtained wihtin seconds and the extended runtime is exploited for improving solution quality.


Conclusion

LocalSolver offers an innovative modelling approach, much simpler than the MIP formalism. The resulting model for the Travelling Salesman Problem is not only compact and natural, but it also provide much better results, even for large instances and limited running time. Feasible solutions are computed in seconds and high quality solutions are obtained in only minutes.

Contact us - Disclaimer - Copyright 2018 Innovation 24