Benchmark — 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 amount of goods to be transported from one facility to another. The problem 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 be solved.

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 as challenging in the Operations Research literature. The smallest one involves 12 facilities to locate whereas the largest one counts 256 facilities, thus implying a Mixed-Integer Quadratic Programming (MIQP) model with 65,000 binary decisions and 4 billions of quadratic terms in the objective function. Most of them remain open to this day, meaning that the optimal solution is not known. Along the years, researchers have improved upper and lower bounds for these instances by using innovative mathematical and algorithmic methods, but also by exploiting the special structure of the instances or leveraging supercomputing capabilities with days of runtime.

Mathematical models

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.

The LocalSolver 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. Then, the objective function is 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;
}

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 best known solution in %. The comparison is made between LocalSolver 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.

LocalSolver delivers solutions with small gaps in a matter of seconds, even on the largest instances. After 1 minute, the average gap observed for LocalSolver over the 26 instances is 1.5%; after 10 minutes, its average gap is 0.8%; after 1 hour, its average gap is 0.6%. On the other hand, the average gap observed for Gurobi after 1 minute is 17.2%; after 10 minutes, its average gap is 11.8%; after 1 hour, its average gap remains 9.5%. Note that on the largest instance of the benchmark, involving 256 facilities to locate, LocalSolver delivers a solution with a gap lower than 0.4% in 1 minute whereas Gurobi is not able 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 could not reach a feasible solution within the time limit, it is plotted as a 'X'. You can use the slider to select different time limits and update the chart accordingly.

Conclusion

LocalSolver offers an innovative modeling approach based on list variables, which made 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++, 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.