Hungarian
The package provides one implementation of the Hungarian algorithm(KuhnMunkres 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.
Installation
pkg> add Hungarian
Quick start
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.
If a jobworker assignment is not possible, use the special missing
value to indicate which pairs are disallowed:
julia> using Hungarian
julia> weights = [missing 1 1; 1 0 1; 1 1 0]
3×3 Matrix{Union{Missing, Int64}}:
missing 1 1
1 0 1
1 1 0
julia> assignment, cost = hungarian(weights)
([2, 1, 3], 2)
NOTE: This package does not support Inf
weights. All Inf
s are converted to prevfloat(typemax(T))
before running the munkres algorithm.
Usage
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 9 stored entries:
1 2 ⋅ ⋅ ⋅
⋅ ⋅ 1 ⋅ 2
2 ⋅ ⋅ ⋅ ⋅
1 ⋅ 2 ⋅ ⋅
⋅ ⋅ ⋅ 2 1
# 0 => nonzero
# 1 => zero
# 2 => STAR
julia> Matrix(matching)
5×5 Matrix{Int8}:
1 2 0 0 0
0 0 1 0 2
2 0 0 0 0
1 0 2 0 0
0 0 0 2 1
julia> [findfirst(matching[i,:].==Hungarian.STAR) for i = 1:5]
5element Vector{Int64}:
2
5
1
3
4
julia> [findfirst(matching[:,i].==Hungarian.STAR) for i = 1:5]
5element Vector{Int64}:
3
1
4
5
2
If a jobworker assignment is not possible, use the special missing
value to indicate which pairs are disallowed:
julia> using Hungarian
julia> weights = [missing 1 1; 1 0 1; 1 1 0]
3×3 Matrix{Union{Missing, Int64}}:
missing 1 1
1 0 1
1 1 0
julia> matching = Hungarian.munkres(weights)
3×3 SparseArrays.SparseMatrixCSC{Int8, Int64} with 6 stored entries:
⋅ 2 1
2 1 ⋅
1 ⋅ 2
References

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