assignment function

Linear Sum Assignment Problem

Linear (sum) assignment problem, or LSAP.

assignment(cmat, dir = "min")

Arguments

• cmat: quadratic (numeric) matrix, the cost matrix.
• dir: direction, can be "min" or "max".

Details

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.

Returns

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.

References

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.

Note

Slower than the Hungarian algorithm in package clue.

See Also

clue::solve_LSAP

Examples

##  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)