Hexaly vs Gurobi on the Quadratic Assignment Problem (QAP)

The Quadratic Assignment Problem (QAP) consists in 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 to be 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.

Hexaly Optimizer reaches an average gap of 1.5% after 60 seconds of running time on the Quadratic Assignment Problem. This page illustrates how Hexaly Optimizer outperforms traditional general-purpose optimization solvers, like Gurobi 9.1, 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 of them 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 9.1 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 id of the factory assigned to the first location, and so on. The objective function is then straightforward to write, and the full 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 Hexlay Optimizer results on the Quadratic Assignment Problem (QAP)

We compare both solvers’ performance with three solving times: 1 minute, 10 minutes, and 1 hour. At the end of the running time, we measure the gap to the best known solution in %. The comparison is made between Hexaly 10.5 and Gurobi 9.1, known as a state-of-the-art MIP solver. Both are used with default parameters. We ran our experiments on a server equipped with an Intel Core i7-6700k processor (4 cores, 4.0GHz, 8MB cache) and 64GB RAM.

Hexaly delivers solutions with small gaps in seconds, even for the largest instances. After 1 minute, the average gap observed for Hexaly over the 26 instances is 1.5%. After 10 minutes, its average gap is 0.8%. Finally, its average gap after one hour of running time is 0.6%. On the other hand, the average gap observed for Gurobi is 17.2% after one minute, 11.8% after 10 minutes, and 9.5% after one hour. Note that on the largest instance of the benchmark, involving 256 facilities to locate, Hexaly delivers a solution with a gap lower than 0.4% in 1 minute, whereas Gurobi is unable to reach any feasible solution in 1 hour.

The chart below reports all the results with the instance size on a horizontal scale and the gap to the best known solution on the vertical axis. When a solver cannot reach a feasible solution within the time limit, it is plotted as a square. You can use the slider to select different time limits and update the chart accordingly.

Conclusion

Hexaly offers an innovative modeling approach based on list variables, making the mathematical modeling of the Quadratic Assignment Problem (QAP) much simpler than traditional MIP 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.

Are you interested in trying it out? Get free trial licenses here. In the meantime, feel free to contact us; we will be glad to exchange about your optimization problems.

Share