,
Franz Rendl [ctb, cph]| Title: | Heuristics for the Quadratic Assignment Problem (QAP) |
|---|---|
| Description: | Implements heuristics for the Quadratic Assignment Problem (QAP). 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. The problem is NP-hard and the package implements a simulated annealing heuristic. |
| Authors: | Michael Hahsler [aut, cre, cph]
,
Franz Rendl [ctb, cph] |
| Maintainer: | Michael Hahsler <[email protected]> |
| License: | GPL-3 |
| Version: | 0.1-2.1 |
| Built: | 2024-10-31 21:07:23 UTC |
| Source: | https://github.com/mhahsler/qap |
This function implements Quadratic Assignment Problems (QAP) heuristics. Currently there is only a simulated annealing heuristic available, but more will be added in the future.
qap(A, B, method = NULL, ...) qap.obj(A, B, o)qap(A, B, method = NULL, ...) qap.obj(A, B, o)
A |
a symmetric matrix with positive weights/flows between pairs facilities. |
B |
a symmetric matrix with positive distances between pairs of locations. |
method |
a character string indicating the used solver. Defaults
to |
... |
further arguments are passed on to the solver (see details). |
o |
a permutation vector for the assignment of facilities to locations. |
The QAP is a facilities location problem. Given facilities and
locations with a matrix specifying the flows between facilities and
a matrix with location distances,
find the best facility to location assignment that minimizes the total transportation cost given
as flow times distance.
The assignment is represented by a permutation matrix and
the objective is
iqap.obj calculates the objective function for and
with the permutation o.
Although, the QAP was introduced as a combinatorial optimization problem for the facility location problem in operations research (see Koopmans and Beckmann;1957), it also has many applications in data analysis (see Hubert and Schultz; 1976).
The QAP is known to be NP-hard. This function implements the simple simulated annealing heuristic described by Burkard and Rendl (1984). The code is based on Rendl's FORTRAN implementation of the algorithm available at the QAPLIB website. The authors suggests that it can produce heuristic solutions for QAPs with a dimension of 256 objects or less. However, this is not a hard limit in the implementation.
The solver has the additional arguments
rep = 1L, miter = 2 * nrow(A), fiter = 1.1,
ft = 0.5 and maxsteps = 50L
integer; number of restarts.
integer; number of iterations at fixed temperature.
multiplication factor for miter after miter random transposition trials.
multiplication factor for t after miter random transposition trials (between 0 and 1).
integer; maximal number of allowed cooling steps.
Returns an integer vector with facility to location assignments. The
objective function value is provided as attribute "obj".
Michael Hahsler
R.E. Burkard and F. Rendl (1984). A thermodynamically motivated simulation procedure for combinatorial optimization problems. European Journal of Operations Research, 17(2):169-174. doi: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. doi: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. doi:10.1111/j.2044-8317.1976.tb00714.x
## load the had12 QAPLIB problem p <- read_qaplib(system.file("qaplib", "had12.dat", package="qap")) p ## run 1 repetitions verbose a <- qap(p$A, p$B, verbose = TRUE) a ## compare with known optimum (gap, % above optimum) (attr(a, "obj") - p$opt)/p$opt * 100 ## run more repetitions quietly a <- qap(p$A, p$B, rep = 100) a ## compare with known optimum (gap, % above optimum) (attr(a, "obj") - p$opt)/p$opt * 100## load the had12 QAPLIB problem p <- read_qaplib(system.file("qaplib", "had12.dat", package="qap")) p ## run 1 repetitions verbose a <- qap(p$A, p$B, verbose = TRUE) a ## compare with known optimum (gap, % above optimum) (attr(a, "obj") - p$opt)/p$opt * 100 ## run more repetitions quietly a <- qap(p$A, p$B, rep = 100) a ## compare with known optimum (gap, % above optimum) (attr(a, "obj") - p$opt)/p$opt * 100
Reads example file in the format used by QAPLIB.
read_qaplib(file)read_qaplib(file)
file |
file name. |
Problems end with the extension .dat and solutions with .sln.
The code tries to read the problem and, if available in the same directory,
it also reads the solution and the known optimal value from the
solution file.
The package contains a copy of the problem instances and solutions
from QAPLIB. The data is stored in the package in directory qaplib.
Returns a list with the components
D |
distance matrix. |
W |
weight matrix. |
solution |
a known optimal solution (if available). |
opt |
known optimal value (if available). |
Michael Hahsler
R.E. Burkard, E. Cela, S.E. Karisch and F. Rendl, QAPLIB - A Quadratic Assignment Problem Library, https://coral.ise.lehigh.edu/data-sets/qaplib/
## load a QAPLIB problem instance p <- read_qaplib(system.file("qaplib", "had12.dat", package="qap")) p ## list all QAPLIB instances dir(system.file("qaplib", package="qap"), pattern = "*.dat")## load a QAPLIB problem instance p <- read_qaplib(system.file("qaplib", "had12.dat", package="qap")) p ## list all QAPLIB instances dir(system.file("qaplib", package="qap"), pattern = "*.dat")