Approximate solution of the quadratic assignment problem – TDA's
mqap, adapted from CACM algorithm 608 (D.H. West). Tries to
find a permutation p of 1:n minimizing
$$\sum_i \left( C_{i,p(i)} + \sum_j F_{ij} D_{p(i),p(j)} \right)$$
This is a heuristic, not an exact solver: the value returned is an
upper bound on the true minimum, and need not be optimal for larger
n (see examples/coverage/mqapops.cf for the objective
and small hand-verified instances). flows and distances
must have a zero main diagonal; a nonzero diagonal is silently reset
to zero with a warning from TDA itself.
Usage
tda_mqap(flows, distances, costs = NULL, dir = tempfile("tda"), ...)Arguments
- flows
the flow matrix
F(n x n).- distances
the distance matrix
D(n x n).- costs
the fixed placement cost matrix
C(n x n), default all zero.- dir
working directory.
- ...
passed to
tda_run.
Value
A list: value, the objective at the returned
permutation; permutation, integer vector p with
p[i] the location assigned to facility i.
See also
Other optimization:
tda_boolean_min(),
tda_mlp(),
tda_mlpi(),
tda_mls(),
tda_mqp()