In the Quadratic Assignment Problem (QAP) a set of n locations and n facilities is given, and each facility must be assigned a location. To compute the cost of each possible assignment we multiply the flow between each pair of facilities by the distance between their assigned locations, and sum over all the pairs. The aim is to find the assignment that minimizes this cost.

METSlib includes a naive QAP solver that is able to solve QAPLIB problems with up to 100 nodes at the optimum or at few percent points to it.

The model is implemented in Examples/stable/0.5/qap/src/qap_model.hpp. It is a permutation problem with two matrices (a and b) the flow and the distance.

The Examples/stable/0.5/qap/src/main_ts.cc implements a simple TS solver for the model (using single swaps) and the Examples/stable/0.5/qap/src/main.cc implements an iterated local search with a randomly varying tabu list tenure.

The code is provided in the examples under the qap subfolder.

You can also browse the code online.

To compile the program you must first install the metslib 0.5.x library. Once done ./configure and make as usual.

The sample program includes some instances from QAPLIB, just run

 ./src/tsqap data/chr12a.dat

or

 ./src/itsqap data/chr12a.dat

to see it in action.

Happy hacking.

• Mirko Maischberger