assignment: Linear Sum Assignment Problem

In adagio: Discrete and Global Optimization Routines

Linear Sum Assignment Problem

Description

Linear (sum) assignment problem, or LSAP.

Usage

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.

Value

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.

Note

Slower than the Hungarian algorithm in package clue.

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

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

adagio documentation built on Oct. 26, 2023, 3:01 p.m.