Software for QAP
The following codes are available through the QAPLIB Home Page. We intend to extend this list of codes, and would like to include also further software, contributed by other researchers.
Unless otherwise stated, the following programs are selfcontained, i.e. compiling them should result in an executable main program. The input convention is the same for all files. The main program expects a QAP instance (in the format of the QAPLIB) from the primary input.
qapbb.f (Fortran)
The Branch and Bound code from [BuDe:80] solves QAPs to optimality. The code qapbb.f is a modified version of it (a linear term can be included) and is quite efficient on problems of sizes n <= 15. Running it on larger problems may result in unpredictably long computation times. Currently the code is dimensioned to handle problems of sizes at most n <= 30.
A typical call might look like
bbqap < nug12.dat
qapglb.f (Fortran)
The Gilmore-Lawler bound can be computed quite efficiently for all instances of the QAPLIB. Currently the code is dimensioned for problems with n <= 256. It uses some of the subroutines from [BuDe:80] in modified form.
qapeli.f (Fortran)
This routine computes the elimination bound. It is applicable only if the problem is symmetric. It is also dimensioned for n <= 256.
GRASP (Fortran)
This is the GRASP heuristic of [LiPaRe:94]. GRASP codes for dense and sparse QAPs can be obtained from the home page of M.G.C. Resende, and consist of compressed tar-files.
qapsim.f (Fortran)
This is the code from [BuRe:84], and produces heuristic solutions for QAPs of dimension n <= 256, based on simulated annealing.
Ro-TS (Pascal)
From here can be downloaded a code of the robust taboo search procedure from [Taillard:91]. The implementation is due to Eric Taillard and produces heuristic solutions for QAPs of dimension n <= 150.
FANT (C++) *
Here can be found a code of the ant system approach for the QAP from [Taillard:98]. The implementation is due to Eric Taillard and produces heuristic solutions for QAPs of dimension n <= 51.
SA (C) *
Here can be found a code of the simulated annealing approach for the QAP from [Connolly:90]. The implementation is due to Eric Taillard, 1998.
Li-Pardalos generator (Fortran)
The problem generator of Y. Li and P.M. Pardalos [LiPa:92] can be obtained by sending an E-Mail to and putting “send 92006” in the body of the mail message.