The package provides one implementation of the **Hungarian algorithm**(*Kuhn-Munkres algorithm*) based on its matrix interpretation. This implementation uses a sparse matrix to keep tracking those marked zeros, so it costs less time and memory than Munkres.jl. Benchmark details can be found here.

```
pkg> add Hungarian
```

Let's say we have 5 workers and 3 tasks with the following cost matrix:

```
weights = [ 24 1 8;
5 7 14;
6 13 20;
12 19 21;
18 25 2]
```

We can solve the assignment problem by:

```
julia> using Hungarian
julia> assignment, cost = hungarian(weights)
([2,1,0,0,3],8)
# worker 1 => task 2 with weights[1,2] = 1
# worker 2 => task 1 with weights[2,1] = 5
# worker 5 => task 3 with weights[5,3] = 2
# the minimal cost is 1 + 5 + 2 = 8
```

Since each worker can perform only one task and each task can be assigned to only one worker, those `0`

s in the `assignment`

mean that no task is assigned to those workers.

When solving a canonical assignment problem, namely, the cost matrix is square, one can directly get the matching via `Hungarian.munkres(x)`

instead of `hungarian(x)`

:

```
julia> using Hungarian
julia> matching = Hungarian.munkres(rand(5,5))
5×5 SparseArrays.SparseMatrixCSC{Int8,Int64} with 7 stored entries:
[1, 1] = 1
[5, 1] = 2
[1, 2] = 2
[2, 3] = 2
[2, 4] = 1
[3, 4] = 2
[4, 5] = 2
# 0 => non-zero
# 1 => zero
# 2 => STAR
julia> Matrix(matching)
5×5 Array{Int8,2}:
1 2 0 0 0
0 0 2 1 0
0 0 0 2 0
0 0 0 0 2
2 0 0 0 0
julia> [findfirst(matching[i,:].==Hungarian.STAR) for i = 1:5]
5-element Array{Int64,1}:
2
3
4
5
1
julia> [findfirst(matching[:,i].==Hungarian.STAR) for i = 1:5]
5-element Array{Int64,1}:
5
1
2
3
4
```

J. Munkres, "Algorithms for the Assignment and Transportation Problems", Journal of the Society for Industrial and Applied Mathematics, 5(1):32–38, 1957 March.

10/21/2016

about 1 month ago

120 commits