This package implements heuristics for the Quadratic Assignment Problem (QAP) first introduced by Koopmans and Beckmann (1957). Although, the QAP was introduced as a combinatorial optimization problem for the facility location problem in operations research, it also has many applications in data analysis (see Hubert and Schultz; 1976).
The problem is NP-hard and the package implements the simulated annealing heuristic described in Burkard and Rendl (1984).
Stable CRAN version: Install from within R with
install.packages("qap")
Current development version: Install from r-universe.
install.packages("qap", repos = "https://mhahsler.r-universe.dev")
The package contains a copy of the problem instances and solutions from
QAPLIB. We load the had20
QAPLIB problem. The problem contains the A and B matrices and the
optimal solution and the optimal objective function 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 known optimum (% above optimum).
(attr(a, "obj") - p$opt)/p$opt * 100
## [1] 0.058
Any scripts or data that you put into this service are public.
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.