Hexaly vs Concorde vs Gurobi on the Traveling Salesman Problem (TSP) – Optimality Gap

Benchmarks Transportation Routing

Ronan Optimization Engineer November 13, 2026

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 achieves an average optimality gap of 0.4% within 10 minutes on the TSPLIB benchmark, covering symmetric instances with up to 10,000 cities. This benchmark demonstrates Hexaly’s ability to outperform traditional general-purpose optimization solvers, such as Gurobi 12.0, in finding high-quality solutions and computing tight optimality bounds, while delivering performance close to that of state-of-the-art specialized solvers, such as Concorde.

Input data

TSPLIB is the reference library of Traveling Salesman Problem (TSP) instances, covering various TSP variants. In this benchmark, we compare the performance of Hexaly, Gurobi and Concorde on 104 symmetric TSPLIB instances with up to 10,000 cities.

All three solvers compute bounds on the optimal objective value to assess solution quality and establish optimality guarantees. We therefore compare their performance using the relative optimality gap, calculated from the best feasible objective value (ObjValue) and the best bound (ObjBound) returned by each solver. The gap is capped at 100% and defined as follows:

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.

Concorde model

Concorde is a state-of-the-art specialized solver designed specifically for the symmetric Traveling Salesman Problem (TSP). Unlike general-purpose optimization solvers, Concorde relies on a highly optimized branch-and-cut algorithm, combining linear programming relaxations, cutting planes, and branching to find optimal tours and prove their optimality. Its specialization enables outstanding performance on symmetric TSP instances, but it does not directly support asymmetric TSP instances or other optimization problems. As a dedicated TSP solver, Concorde accepts TSP instance files directly as input, without requiring users to formulate an optimization 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, Gurobi and Concorde results on the Traveling Salesman Problem (TSP)

We compare the performance of the three solvers with a time limit of 10 minutes per instance. At the end of each run, we measure the relative optimality gap between the best feasible solution and the best bound returned by the solver. The benchmark uses Hexaly 15.0, Gurobi 12.0, and Concorde 03.12.19, with Concorde relying on the QSopt linear programming solver. All solvers are run with their default parameters on a machine equipped with an AMD Ryzen 7 7700 processor (8 cores, 3.8 GHz base clock, 32 MB L3 cache) and 32 GB of RAM.

The table below reports the average optimality gap achieved by each solver across the benchmark instances.

Hexaly finds near-optimal solutions and computes tight optimality bounds even for instances with up to 10,000 cities, whereas Gurobi struggles to find high-quality solutions for instances with more than 600 cities.

Conclusion

On a widely studied optimization problem such as the Traveling Salesman Problem (TSP), Hexaly achieves performance close to that of state-of-the-art specialized solvers such as Concorde, despite being a general-purpose optimization solver. Hexaly’s innovative modeling approach, based on list variables, enables it to compute tighter optimality bounds on large-scale vehicle routing problems than traditional mixed-integer programming (MIP) solvers such as Gurobi.

Want to compare the quality of feasible solutions against the best-known solutions? Explore our TSP solution quality benchmark.

1. Dantzig, G. B., Fulkerson, D. R., & Johnson, S. M. (1954). Solution of a Large-Scale Traveling-Salesman Problem. Journal of the Operations Research Society of America, 2(4), 393–410. ↩︎