lap is a linear assignment
problem solver using
Jonker-Volgenant algorithm for dense LAPJV¹ or sparse LAPMOD² matrices. Both
algorithms are implemented from scratch based solely on the papers¹˒² and the
public domain Pascal implementation provided by A. Volgenant³. The LAPMOD
implementation seems to be faster than the LAPJV implementation for matrices
with a side of more than ~5000 and with less than 50% finite coefficients.
¹ R. Jonker and A. Volgenant, "A Shortest Augmenting Path Algorithm for
Dense and Sparse Linear Assignment Problems", Computing 38, 325-340 (1987)
² A. Volgenant, "Linear and Semi-Assignment Problems: A Core
Oriented Approach", Computer Ops Res. 23, 917-932 (1996)
³
http://www.assignmentproblems.com/LAPJV.htm |
[archive.org]
Install from PyPI:
pip install lap
| Pre-built Wheels 🛞 | Windows ✅ | Linux ✅ | macOS ✅ |
|---|---|---|---|
| Python 3.7 | AMD64 | x86_64/aarch64 | x86_64 |
| Python 3.8 | AMD64 | x86_64/aarch64 | x86_64/arm64 |
| Python 3.9-3.13 ¹ | AMD64/ARM64 ² | x86_64/aarch64 | x86_64/arm64 |
¹ v0.5.12 supports both numpy 1.x and 2.x for Python 3.8-3.13. 🆕
² Windows ARM64 is experimental.
Other options
pip install git+https://github.com/gatagat/lap.git
git clone https://github.com/gatagat/lap.git
cd lap
pip install "setuptools>=67.8.0"
pip install wheel build
python -m build --wheel
cd dist
import lap
import numpy as np
print(lap.lapjv(np.random.rand(4, 5), extend_cost=True))
More details
The function lapjv(C) returns the assignment cost cost and two arrays x
and y. If cost matrix C has shape NxM, then x is a size-N array
specifying to which column each row is assigned, and y is a size-M array
specifying to which row each column is assigned. For example, an output of x = [1, 0] indicates that row 0 is assigned to column 1 and row 1 is assigned to
column 0. Similarly, an output of x = [2, 1, 0] indicates that row 0 is
assigned to column 2, row 1 is assigned to column 1, and row 2 is assigned to
column 0.
Note that this function does not return the assignment matrix (as done by
scipy's
linear_sum_assignment
and lapsolver's solve dense). The
assignment matrix can be constructed from x as follows: A = np.zeros((N, M)) for i in range(N): A[i, x[i]] = 1
Equivalently, we could construct the assignment matrix from y:
A = np.zeros((N, M))
for j in range(M):
A[y[j], j] = 1
Finally, note that the outputs are redundant: we can construct x from y,
and vise versa:
x = [np.where(y == i)[0][0] for i in range(N)]
y = [np.where(x == j)[0][0] for j in range(M)]
Released under the 2-clause BSD license, see LICENSE.
Copyright (C) 2012-2025, Tomas Kazmar
Contributors (in alphabetic order):
- Benjamin Eysenbach
- Léo Duret
- Pieter Lenaerts
- Raphael Reme
- Ratha Siv
- Robert Wen
- Steven
- Tom White
- Tomas Kazmar
- Wok