Linear Assignment Problem solver using Jonker-Volgenant algorithm
This project is the rewrite of pyLAPJV which supports Python 3 and updates the core code. The performance is twice as high as the original thanks to the optimization of the augmenting row reduction phase using Intel AVX intrinsics. It is a native Python 3 module and does not work with Python 2.x, stick to pyLAPJV otherwise.
Linear assignment problem is the bijection between two sets with equal cardinality which optimizes the sum of the individual mapping costs taken from the fixed cost matrix. It naturally arises e.g. when we want to fit t-SNE results into a rectangular regular grid. See this awesome notebook for the details about why LAP matters: CloudToGrid.
Jonker-Volgenant algorithm is described in the paper:
R. Jonker and A. Volgenant, "A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems," Computing, vol. 38, pp. 325-340, 1987.
The C++ source of the algorithm comes from http://www.magiclogic.com/assignment.html It has been reworked and partially optimized with OpenMP 4.0 SIMD.
pip3 install lapjv
Tested on Linux and macOS.
Refer to test.py for the complete code.
from lapjv import lapjv row_ind, col_ind, _ = lapjv(cost_matrix)