lap: Linear Assignment Problem Solver

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]}

💽 Installation

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.10 supports numpy v2.x for Python 3.9-3.13. 🆕}

^{² Windows ARM64 is experimental.}

Other options

Install from GitHub repo (requires C++ compiler):

pip install git+https://github.com/gatagat/lap.git

Build and install (requires C++ compiler):

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

🧪 Usage

import lap
import numpy as np
print(lap.lapjv(np.random.rand(4, 5), extend_cost=True))

More details

`cost, x, y = lap.lapjv(C)`

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)]

License

Released under the 2-clause BSD license, see LICENSE.

Contributors (in alphabetic order):

Benjamin Eysenbach
Léo Duret
Raphael Reme
Ratha Siv
Robert Wen
Steven
Tom White
Tomas Kazmar
Wok

Package profile

lap

Releases

Release table

PyPI Downloads

Dependencies

Details

Project URLs

Dependencies

Package description