Heuristics for the Quadratic Assignment Problem (QAP)

Implements heuristics for the Quadratic Assignment Problem (QAP). Currently only a simulated annealing heuristic is available.


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

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

News

qap 0.1-1 (2017-02-26)

  • fixed reading optimal solution in read_qaplib.
  • added test.
  • native routines are now registered.

qap 0.1-0 (2015-10-05)

  • initial release.

Reference manual

It appears you don't have a PDF plugin for this browser. You can click here to download the reference manual.

install.packages("qap")

0.1-1 by Michael Hahsler, 2 years ago


Report a bug at https://github.com/mhahsler/qap/issues


Browse source code at https://github.com/cran/qap


Authors: Michael Hahsler [aut, cre, cph] , Franz Rendl [ctb, cph]


Documentation:   PDF Manual  


Task views: Optimization and Mathematical Programming


GPL-3 license


Suggests testthat


Imported by seriation.


See at CRAN