The hardware and bandwidth for this mirror is donated by dogado GmbH, the Webhosting and Full Service-Cloud Provider. Check out our Wordpress Tutorial.
If you wish to report a bug, or if you are interested in having us mirror your free-software or open-source project, please feel free to contact us at mirror[@]dogado.de.

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

Maintainer: Michael Hahsler

Introduction

This package implements heuristics for the Quadratic Assignment Problem (QAP). The QAP was introduced as a facility location problem in operations research (Koopmans and Beckmann, 1957). It also has applications in data analysis, including cluster analysis and seriation (Hubert and Schultz, 1976).

The problem is NP-hard, and the package implements the simulated annealing heuristic described in Burkard and Rendl (1984).

The following R packages use qap: seriation

To cite package ‘qap’ in publications use:

Hahsler M (2022). qap: Heuristics for the Quadratic Assignment Problem (QAP). doi:10.32614/CRAN.package.qap https://doi.org/10.32614/CRAN.package.qap. R package version 0.1-2, https://CRAN.R-project.org/package=qap.

@Manual{,
  title = {qap: Heuristics for the Quadratic Assignment Problem (QAP)},
  author = {Michael Hahsler},
  year = {2022},
  note = {R package version 0.1-2},
  url = {https://CRAN.R-project.org/package=qap},
  doi = {10.32614/CRAN.package.qap},
}

Installation

Stable CRAN version: Install from within R with

install.packages("qap")

Current development version: Install from r-universe.

install.packages("qap",
    repos = c("https://mhahsler.r-universe.dev",
              "https://cloud.r-project.org/"))

Usage

The package contains a copy of the problem instances and solutions from QAPLIB. We load the had20 QAPLIB problem. It contains flow and distance matrices, a known optimal solution, and its objective value.

library(qap)
set.seed(1000)

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

##  [1]  8 15 16 14 19  6  7 17  1 12 10 11  5 20  2  3  4  9 18 13

p$opt

## [1] 6922

We run the simulated annealing heuristic 10 times and use the best solution.

a <- qap(p$A, p$B, rep = 10)
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 the solution with the known optimum (percentage above optimum).

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

## [1] 0.058

References

• Hahsler M (2022). qap: Heuristics for the Quadratic Assignment Problem (QAP). doi:10.32614/CRAN.package.qap https://doi.org/10.32614/CRAN.package.qap. R package version 0.1-2, https://CRAN.R-project.org/package=qap.
• R.E. Burkard and F. Rendl (1984). A thermodynamically motivated simulation procedure for combinatorial optimization problems. European Journal of Operational Research, 17(2):169-174. https://doi.org/10.1016/0377-2217(84)90231-5
• Koopmans TC, Beckmann M (1957). Assignment problems and the location of economic activities. Econometrica 25(1):53-76. https://doi.org/10.2307/1907742
• Hubert, L., and Schultz, J. (1976). Quadratic assignment as a general data analysis strategy. British Journal of Mathematical and Statistical Psychology, 29(2), 190–241. https://doi.org/10.1111/j.2044-8317.1976.tb00714.x

These binaries (installable software) and packages are in development.
They may not be fully stable and should be used with caution. We make no claims about them.
Health stats visible at Monitor.