py-lapsolver

py-lapsolver implements a Linear sum Assignment Problem (LAP) solver for dense matrices based on shortest path augmentation in Python. In practice, it solves 5000x5000 problems in around 3 seconds.

Install

pip install [--pre] lapsolver 

Windows binary wheels are provided for Python 3.5/3.6. Source wheels otherwise.

Install from source

Clone this repository

git clone --recursive https://github.com/cheind/py-lapsolver.git

Then build the project and exectute tests

python setup.py develop
python setup.py test

Executing the tests requires pytest and optionally pytest-benchmark for generating benchmarks.

Usage

importnumpyasnpfromlapsolverimportsolve_densecosts=np.array([
[6, 9, 1],
[10, 3, 2],
[8, 7, 4.]
], dtype=np.float32) rids, cids=solve_dense(costs)
forr,cinzip(rids, cids):
print(r,c) # Row/column pairings"""0 21 12 0"""

You may also want to mark certain pairings impossible

# Matrix with non-allowed pairingscosts=np.array([
[5, 9, np.nan],
[10, np.nan, 2],
[8, 7, 4.]]
)
rids, cids=solve_dense(costs)
forr,cinzip(rids, cids):
print(r,c) # Row/column pairings"""0 01 22 1"""

Benchmarks

Comparisons below are generated by scripts in ./lapsolver/benchmarks.

Currently, the following solvers are tested

• lapjv - https://github.com/gatagat/lap
• munkres - http://software.clapper.org/munkres/
• ortools - https://github.com/google/or-tools **
• scipy - https://github.com/scipy/scipy/tree/master/scipy
• lapsolver - this project

**reduced performance due to costly dense matrix to graph conversion. If you know a better way, please let me know.

Please note that the x-axis is scaled logarithmically. Missing bars indicate excessive runtime or errors in returned result.

Additional Benchmarks

Berhane performs an in depth analysis of Python3 linear assignment problem solver at https://github.com/berhane/LAP-solvers

References

py-lapsolver heavily relies on code published by @jaehyunp at https://github.com/jaehyunp/