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 source:Examples/stable/0.5/qap/src/main_ts.cc implements a simple TS solver for the model (using single swaps) and the source: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.
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
to see it in action.
- Mirko Maischberger