LocalSolver


Benchmark QAP

The Quadratic Assignment Problem (QAP) is a fundamental operational research problem based on a real-life problem. There are a set of n facilities and a set of n locations. A distance is specified for each pair of locations and a weight or flow is specified for each pair of facilities (for instance, the amount of supplies transported between the two facilities). The problem is to assign all facilities to different locations with the goal of minimizing the sum of the distances multiplied by the corresponding flows. The main difficulty of this problem comes from the quadratic nature of the cost function.


Data

The instances used here come from the QAP Library. In the literature, various techniques have been applied to compute solutions or lower bounds to these instances, some of which exploit the special structure of some instances or use supercomputing clusters with days of runtime.

In this benchmark, we compare the results obtained by LocalSolver and its competitors, with default settings and limited running times (from 10 seconds to 1 hour). We report results on the 124 instances for which the optimal solution is known and we use the gap to this optimal solution as the metric in the benchmark below. All the experiments are performed on a MacBook Pro (Intel Core i5 2.5GHz, 6GB RAM).


LocalSolver model

As described in our Example Tour, the simplest 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 city, and so on. Then, the objective function is straightforward and the full model takes only four lines.


function model()
 {
    x <- list(n);

    constraint count(x) == n;

    obj <- sum[i in 0..n-1][j in 0..n-1]( distance[i][j] * flow[x[i]][x[j]] );

    minimize obj;
}

LocalSolver against commercial MIP solvers

Most commercial MIP solvers deal with quadratic programming problems. In this part, we compare their performance against LocalSolver with default settings for both solvers.

The comparison is made between LocalSolver 6.0 and a state-of-the-art commercial MIP solver, both without any specific configuration or tuning. The model used for LocalSolver is the 4-line model presented above and the MIP model is the standard quadratic (MIQP) formulation.

Results

The chart below reports the results with the instance size on a horizontal logarithmic scale and the gap to the known optimal 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.

The MIP solver has difficulties finding quality solutions in the given running time, even for small instances. For instance, after 5 minutes the gap for instance chr15b (15 locations) is still above 30%. Moreover, due to the O(n^4)-size of the MIQP model, no feasible solution is produced for instances with more that 45 locations.

On the contrary, we observe that LocalSolver produces feasible solutions instantly whatever the size of the problem, and quickly reaches high-quality solutions: within 10 seconds, an optimality gap smaller than 10% is obtained for most instances. Increasing the computation time to 5 minutes decreases the gap below 2% for 90% of the instances. For all instances and time limits, LocalSolver provides a better solution than the MIP solver in 99.5% of cases.

Comparative tables

The following tables summarise the information contained in the previous chart. They present for each solver and runtime the portion of the instances solved such that the gap to optimality is under a given threshold. You can change the displayed threshold with the slider bar.

Conclusion

The modeling formalism offered by LocalSolver allows modeling the Quadratic Assignment Problem (QAP) in four lines and its internal optimization algorithms produce high-quality solutions in seconds, without any tuning. Relying on a compact mathematical model and innovative resolution techniques, LocalSolver is able to deal with QAP instances that are out of reach of MIP solvers.

Contact us - Disclaimer - Copyright 2017 Innovation 24