R: solve_LSAP {clue}

 

Solve Linear Sum Assignment Problem

Package: 

clue

Version: 

0.3-47

Description

Solve the linear sum assignment problem using the Hungarian method.

Usage

solve_LSAP(x, maximum = FALSE)

Arguments

x

a matrix with nonnegative entries and at least as many columns as rows.

maximum

a logical indicating whether to minimize of maximize the sum of assigned costs.

> install.packages("clue")
> library("clue")

Examples

x <- matrix(c(5, 1, 4, 3, 5, 2, 2, 4, 4), nrow = 3)

solve_LSAP(x) solve_LSAP(x, maximum = TRUE)

## To get the optimal value (for now):
y <- solve_LSAP(x) sum(x[cbind(seq_along(y), y)])


 A sample matching example:

 x <- matrix(c(13,7,4,18,30,44,13,28,23,33,55,43,13,19,22,8,4,18,39,2,3,7,29,17,23,17,14,28,40,54,3,38,33,43,65,53,28,22,19,33,45,59,2,43,38,48,70,58,19,13,10,24,36,50,7,34,29,39,61,49,4,2,5,9,21,35,22,19,14,24,46,34,16,10,7,21,33,47,10,31,26,36,58,46,19,25,28,14,2,12,45,4,9,1,23,11,32,38,41,27,15,1,58,17,22,12,10,2,80,74,71,85,97,111,54,95,90,100,122,110,4,2,5,9,21,35,22,19,14,24,46,34,36,30,27,41,53,67,10,51,46,56,78,66), ncol=12);

y <- matrix(c(1.5,1.4,0.8,0.7,0.2,2.2,0.0,0.4,0.9,1.3,2.8,2.0,0.3,0.2,0.4,0.5,1.4,1.0,1.2,1.6,0.3,0.1,1.6,0.8,1.2,1.1,0.5,0.4,0.5,1.9,0.3,0.7,0.6,1.0,2.5,1.7,1.6,1.5,0.9,0.8,0.1,2.3,0.1,0.3,1.0,1.4,2.9,2.1,1.3,1.2,0.6,0.5,0.4,2.0,0.2,0.6,0.7,1.1,2.6,1.8,1.7,1.6,1.0,0.9,0.0,2.4,0.2,0.2,1.1,1.5,3.0,2.2,1.2,1.1,0.5,0.4,0.5,1.9,0.3,0.7,0.6,1.0,2.5,1.7,0.3,0.4,1.0,1.1,2.0,0.4,1.8,2.2,0.9,0.5,1.0,0.2,0.2,0.3,0.9,1.0,1.9,0.5,1.7,2.1,0.8,0.4,1.1,0.3,3.9,3.8,3.2,3.1,2.2,4.6,2.4,2.0,3.3,3.7,5.2,4.4,1.1,1.0,0.4,0.3,0.6,1.8,0.4,0.8,0.5,0.9,2.4,1.6,1.1,1.0,0.4,0.3,0.6,1.8,0.4,0.8,0.5,0.9,2.4,1.6), ncol=12);

solve_LSAP(x+y*10);