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

 assignment R Documentation

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

`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. 3, 2022, 5:07 p.m.