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 *coap@math.ufl.edu* and
putting "send 92006" in the body of the mail message.

GO BACK TO MAIN PAGE OF QAPLIB