adagio (version 0.7.1)

assignment: Linear Sum Assignment Problem

Description

Linear (sum) assignment problem, or LSAP.

Usage

assignment(cmat)

Arguments

cmat

quadratic integer matrix, the cost matrix.

Value

List with components perm, the permutation that defines the minimum solution, min, the minimum value, and err, which is -1 if an integer overflow occured.

Details

Solves the linear (sum) assignment problem for quadratic matrices with integer entries.

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.

See Also

clue::solve_LSAP

Examples

# NOT RUN {
##  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; y$t                     # 4  5  7  2  6  1  3  8 10  9
z <- cbind(1:10, y$perm)        # 156
x[z]                            # 5  4 11  8 20  7 38 15 22 26
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)
dmat <- round(100*cmat, 2)
system.time(T1 <- assignment(dmat))   # elapsed: 0.003
T1$min / 100                          # 139.32

library("clue")
system.time(T2 <- solve_LSAP(cmat))     # elapsed: 0.034
sum(cmat[cbind(1:n, T2)])               # 139.32
# }