qap - Heuristics for the Quadratic Assignment Problem (QAP) - R package

Implements heuristics for the Quadratic Assignment Problem (QAP). Currently only the simulated annealing heuristic described in Burkard and Rendl (1984) is available.

Installation

Stable CRAN version: install from within R with

install.packages("qap")

Current development version: Download package from AppVeyor or install from GitHub (needs devtools).

install_git("mhahsler/qap")

Usage

Load the had12 QAPLIB problem (shipped with the package) and run 100 repetitions.

library(qap)
p <- read_qaplib(system.file("qaplib", "had20.dat", package="qap"))

a <- qap(p$A, p$B, rep = 100)
a

[1]  8 15 16 14 19  6  7 12  1 11 10  5  3 20  2 17  4  9 18 13
attr(,"obj")
[1] 6926

Compare with known optimum (% above optimum).

(attr(a, "obj") - p$opt)/p$opt * 100

[1] 0.05778677

References

• R.E. Burkard and F. Rendl. A thermodynamically motivated simulation procedure for combinatorial optimization problems. European Journal of Operations Research, 17(2):169-174, 1984.
• qap reference manual