Linear (sum) assignment problem

Compute the best bipartite matching using one of three methods. For an n x n score matrix it find \(\max_{v\in \Pi_n} \sum_{i=1}^n score_{i, v(i)}\) where \(\Pi_n\) denotes all permutations on n objects.

Usage

do_lap(score, method = "clue")

Arguments

score

matrix of pairwise scores

method

One of "lapjv", "lapmod", or "clue"

Value

do_lap returns a vector which indicates the best matching column for each row.

Details

Solves a linear assignment using one of three methods. "clue" uses solve_lsap from the clue package. "lapjv" uses the Jonker-Volgenaut approach implemented in this package. "lapmod" use a modification of JV that exploits sparsity in the score matrix.

Scores do not need to be non-negative. For "clue" the scores are pre-translated to be non-negative which preserves the LAP solution.

References

R. Jonker, A. Volgenant (1987). A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing, pages 325-340.

A. Volgenant (1996). Linear and Semi-Assignment Problems: A Core Oriented Approach. Computer Ops Res., pages 917-932.

C. H. Papadimitriou and K. Steiglitz (1998). Combinatorial Optimization: Algorithms and Complexity. Courier Corporation.

Examples

set.seed(12345)
cost <- Matrix::rsparsematrix(10, 10, .5)
cbind(
 do_lap(cost, "lapjv"),
 do_lap(cost, "lapmod"),
 do_lap(cost, "clue")
)
#>       [,1] [,2] [,3]
#>  [1,]    1    1    1
#>  [2,]    7    7    7
#>  [3,]    9    9    9
#>  [4,]    8    8    8
#>  [5,]    3    3    3
#>  [6,]    5    5    5
#>  [7,]    6    6    6
#>  [8,]    4    4    4
#>  [9,]   10   10   10
#> [10,]    2    2    2