## LapSolve.jl

Linear Assignment Problem solver via the Kuhn-Munkres algorithm
Author francescoalemanno
Popularity
2 Stars
Updated Last
3 Months Ago
Started In
March 2020

# LapSolve

Linear Assignment Problem solver via the Kuhn-Munkres algorithm, original Kernel functions come from the excellent Hungarian.jl, this package adds a solver for stiff problems, which are LAP problems with too many blocking costs where an optimal fully assigned solution is impossible, but an optimal partial assignment may be possible. This solver has been modified to be completely non-copying and non-mutating, for saving as much memory as possible (this modification has also been sent upstream #15, although in some cases Hungarian.jl will still copy).

### Example

```julia> using LapSolve

julia> M=rand(1:100,3,3)
3×3 Array{Int64,2}:
66  83  92
17  92  65
30  84  18

julia> solve_lap(M)
([2, 1, 3], 118)```

### Example for Stiff Problem

```julia> using LapSolve

julia> M=rand([1,2,Inf],5,5)
5×5 Array{Float64,2}:
Inf    Inf      1.0    1.0    1.0
Inf    Inf    Inf    Inf    Inf
2.0    1.0  Inf      1.0    2.0
Inf      2.0    1.0    2.0  Inf
2.0    2.0    2.0  Inf      1.0

julia> solve_stiff_lap(M)
6-element Array{Tuple{Int64,Int64},1}:
(1, 4)        ← row 1 is assigned to column 4
(2, -1)       ← -1 for missing assignment, row 2 is assigned to nothing
(3, 2)
(4, 3)
(5, 5)
(-1, 1)       ← column 1 is assigned to nothing```

### Used By Packages

No packages found.