Heuristics for the Quadratic Assignment Problem (QAP) - R package
Fortran R C
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
R
inst/qaplib
man
src
tests
.Rbuildignore
.gitignore
.travis.yml
DESCRIPTION
LICENSE
NAMESPACE
NEWS.md
README.md
appveyor.yml

README.md

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

CRAN version CRAN RStudio mirror downloads Travis-CI Build Status AppVeyor Build Status

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).

library("devtools")
install_github("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