# assignment: Linear Sum Assignment Problem In adagio: Discrete and Global Optimization Routines

## Description

Linear (sum) assignment problem, or LSAP.

## Usage

 `1` ```assignment(cmat) ```

## Arguments

 `cmat` quadratic integer matrix, the cost matrix.

## Details

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

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

## Note

Faster than the Hungarian algorithm, but only applicable to quadratic cost matrices with integer components.

## Author(s)

Copyright(c) 1993 A. H. Morris, Jr., Naval Surface Warfare Center, using Fortran routines written by S. Martello and P. Toth, University of Bologna. Released for free and general use, now under GPL license, wrapped for R by Hans W Borchers <[email protected]>.

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

`clue::solve_LSAP`

## Examples

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25``` ```## 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 ## End(Not run) ```

### Example output

``` [1]  4  5  7  2  6  1  3  8 10  9
NULL
[1]  5  4 11  8 20  7 38 15 22 26
[1] TRUE
user  system elapsed
0.029   0.000   0.030
[1] 139.32
user  system elapsed
0.018   0.000   0.017
[1] 139.32
```

adagio documentation built on May 18, 2018, 1:08 a.m.