Skip to main content

Linear sum assignment problem solver using Jonker-Volgenant algorithm.

Project description

Build Status PyPI

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 AVX2 intrinsics. It is a native Python 3 module and does not work with Python 2.x, stick to pyLAPJV otherwise.

Blog post

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.

This paper is not publicly available though a brief description exists on JV is faster in than the Hungarian algorithm in practice, though the complexity is the same - O(n3).

The C++ source of the algorithm comes from It has been reworked and partially optimized with OpenMP 4.0 SIMD.


pip3 install lapjv

Tested on Linux and macOS.


Refer to for the complete code.

from lapjv import lapjv
row_ind, col_ind, _ = lapjv(cost_matrix)

The assignment matrix by row is row_ind: the value at n-th place is the assigned column index to the n-th row. col_ind is the reverse of row_ind: mapping from columns to row indexes.

Note: a bijection is only possible for sets with equal cardinality. If you need to map A vectors to B vectors, derive the square symmetric (A+B) x (A+B) matrix: take the first A rows and columns from A and the remaining [A..A+B] rows and columns from B. Set the A->A and B->B costs to some maximum distance value, big enough so that you don't see assignment errors.

Illegal instruction

This error appears if your CPU does not support the AVX2 instruction set. We do not ship builds for different CPUs so you need to build the package yourself:

pip3 install git+


NAN-s in the cost matrix lead to completely undefined result. It is the caller's responsibility to check them.


MIT Licensed,see LICENSE

Project details

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

lapjv-1.3.22.tar.gz (10.7 kB view hashes)

Uploaded source

Built Distributions

lapjv-1.3.22-cp310-cp310-win_amd64.whl (22.7 kB view hashes)

Uploaded cp310

lapjv-1.3.22-cp39-cp39-win_amd64.whl (22.7 kB view hashes)

Uploaded cp39

lapjv-1.3.22-cp38-cp38-win_amd64.whl (22.9 kB view hashes)

Uploaded cp38

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Huawei Huawei PSF Sponsor Microsoft Microsoft PSF Sponsor NVIDIA NVIDIA PSF Sponsor Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page