Oven logo

Oven

lap0.5.12

Published

Linear Assignment Problem solver (LAPJV/LAPMOD).

pip install lap

Package Downloads

Weekly DownloadsMonthly Downloads

Authors

Project URLs

Requires Python

>=3.7

Dependencies

Test Simple Benchmark Test PyPI Build Publish to PyPI

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:

PyPI version Downloads Downloads

pip install lap
Pre-built Wheels 🛞WindowsLinuxmacOS
Python 3.7AMD64x86_64/aarch64x86_64
Python 3.8AMD64x86_64/aarch64x86_64/arm64
Python 3.9-3.13 ¹AMD64/ARM64 ²x86_64/aarch64x86_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.

Copyright (C) 2012-2024, Tomas Kazmar

Contributors (in alphabetic order):

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