Linear Sum Assignment Problem
Linear (sum) assignment problem, or LSAP.
assignment(cmat, dir = "min")
cmat |
quadratic (numeric) matrix, the cost matrix. |
dir |
direction, can be "min" or "max". |
Solves the linear (sum) assignment problem for quadratic matrices.
Uses the lp.assign function from the lpSolve package,
that is it solves LSAP as a mixed integer linear programming problem.
List with components perm, the permutation that defines the
minimum solution, min, the minimum value, and err is
always 0, i.e. not used at the moment.
Slower than the Hungarian algorithm in package clue.
Burkard, R., M. Dell'Amico, and S. Martello (2009). Assignment Problems. Society for Industrial and Applied Mathematics (SIAM).
Martello, S., and P. Toth (1990). Knapsack Problems: Algorithms and Computer Implementations. John Wiley & Sons, Ltd.
clue::solve_LSAP
## Example similar to clue::solve_LSAP
set.seed(8237)
x <- matrix(sample(1:100), nrow = 10)
y <- assignment(x)
# show permutation and check minimum sum
y$perm # 7 6 10 5 8 2 1 4 9 3
y$min # 173
z <- cbind(1:10, y$perm)
x[z] # 16 9 49 6 17 14 1 44 10 7
y$min == sum(x[z]) # TRUE
## Not run:
## Example: minimize sum of distances of complex points
n <- 100
x <- rt(n, df=3) + 1i * rt(n, df=3)
y <- runif(n) + 1i * runif(n)
cmat <- round(outer(x, y, FUN = function(x,y) Mod(x - y)), 2)
system.time(T1 <- assignment(cmat)) # elapsed: 0.003
T1$min / 100 # 145.75
## Hungarian algorithm in package 'clue'
library("clue")
system.time(T2 <- solve_LSAP(cmat)) # elapsed: 0.014
sum(cmat[cbind(1:n, T2)]) # 145.75
## End(Not run)Please choose more modern alternatives, such as Google Chrome or Mozilla Firefox.