Hexaly vs Gurobi on the Quadratic Assignment Problem (QAP)

Benchmark Transportation Location

Frédéric Senior Optimization Scientist September 25, 2024

The Quadratic Assignment Problem (QAP) consists of assigning facilities to locations. For each pair of locations, a distance is given. For each pair of facilities, a flow is given. This flow corresponds to the number of goods transported from one facility to another. The goal is to assign all facilities to locations while minimizing the sum of distances between facilities multiplied by the corresponding flows to be supplied. Despite its simple definition, the quadratic nature of the objective function makes the problem particularly hard to solve.

On the Quadratic Assignment Problem (QAP), Hexaly reaches an average gap of 1.1% to the best known solutions after 1 minute of running time on the QAPLIB benchmark. This page illustrates how Hexaly outperforms traditional general-purpose optimization solvers, like Gurobi 11.0, a state-of-the-art Mixed-Integer Linear and Quadratic Programming (MILP/MIQP) solver, on this challenging problem.

Input data

The instances used for the benchmark come from the QAPLIB. We use the largest and most recent dataset introduced by Taillard. It contains 26 instances considered challenging in the Operations Research literature. The smallest involves 12 facilities to locate, whereas the largest counts 256 facilities. The resulting Mixed-Integer Quadratic Programming (MIQP) model comprises 65,000 binary decisions and 4 billion quadratic terms in the objective function. Most remain open to this day, meaning that the optimal solution is unknown. Over the years, researchers have improved upper and lower bounds for these instances by using innovative mathematical and algorithmic methods, but also by exploiting the particular structure of the instances or leveraging supercomputing capabilities with days of runtime.

Mathematical models of the Quadratic Assignment Problem (QAP)

Mixed-Integer Quadratic Programming (MIQP) model

The results reported below for Gurobi are obtained using the standard Mixed-Integer Quadratic Programming (MIQP) model for the Quadratic Assignment Problem (QAP). This formulation consists of a quadratic number of binary variables representing the assignment of one facility to one location.

Hexaly model

The Hexaly model for the QAP is based on a single list variable representing the permutation of factories. The first item in the list corresponds to the factory’s index assigned to the first location, and so on. Then, the objective function is straightforward to write, and the whole model takes only four lines.

function model()
{
    // List variable: x[i] is the index of the facility at location i 
    x <- list(N);

    // All facilities must be located
    constraint count(x) == N;

    // Minimize the sum of product Distance * Flow
    obj <- sum[i in 0..N-1][j in 0..N-1](Distance[i][j] * Flow[x[i]][x[j]]);

    minimize obj;
}

Gurobi and Hexaly results on the Quadratic Assignment Problem (QAP)

We compare both solvers’ performance within 1 minute of running time. At the end of the running time, we measure the gap in % to the best solutions known in the literature, also called State Of The Art (SOTA). The comparison is made between Hexaly 13.0 and Gurobi 11.0, a state-of-the-art Mixed-Integer Quadratic Programming (MIQP) solver. Both are used with default parameters. We ran our experiments 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 each solver and the SOTA, as reported here.

Hexaly delivers solutions with small gaps in seconds, even for large-scale instances. After 1 minute, the average gap observed for Hexaly over the 26 instances is 1.1%. On the other hand, the average gap observed for Gurobi is 18.5% after 1 minute. On the largest-scale instance of the benchmark involving 256 facilities to locate, Hexaly delivers a solution with a gap lower than 0.4% in 1 minute; in contrast, Gurobi cannot reach any feasible solution in 1 hour of computation time.

Conclusion

Hexaly offers an innovative modeling approach based on list variables, making the mathematical modeling of the Quadratic Assignment Problem (QAP) much more straightforward than traditional Mixed Integer Quadratic Programming solvers. The resulting model for the QAP 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 Quadratic Assignment Problem (QAP) in Python, Java, C#, and C++ in our Example Tour.