lap

Linear Assignment Problem solver (LAPJV/LAPMOD).

lap v0.5.13 1.7M downloads/30d#3,594 on PyPI★ 252

Permissive license BSD-2-Clause Active released 2026-02-23

What it is and what it does

lap is a specialized solver for the linear assignment problem—the task of finding a minimum-cost perfect matching between two sets of items. It implements two algorithms from academic literature: LAPJV (Jonker-Volgenant) for dense cost matrices and LAPMOD (Volgenant-Mordecai) for sparse ones. The package takes a cost matrix as input and returns the total assignment cost plus two index arrays describing which row is assigned to which column and vice versa.

The solver is built from scratch based on published papers and a public-domain Pascal reference implementation. It returns assignment indices rather than a full assignment matrix, keeping the output compact. The package has wheels for Python 3.7–3.14 across Windows, Linux, and macOS, with support for both numpy 1.x and 2.x, making it straightforward to install on most systems.

Use it for:

Object tracking: match detected objects across video frames by minimizing spatial distance cost.
Bipartite graph matching: find optimal pairings in workforce scheduling or resource allocation problems.
Image registration: align keypoints between two images by minimizing coordinate mismatch cost.
Data association: link sensor measurements to tracked targets in multi-object tracking systems.
Auction algorithms: solve procurement or assignment auctions where cost represents bid or preference.
Sequence alignment: match elements between two ordered sequences to minimize dissimilarity.

Worth the install?

AI-flagged interpretation of the facts on this page — verify before relying

Solves the linear assignment problem using the Jonker-Volgenant (LAPJV) or Volgenant-Mordecai (LAPMOD) algorithm, returning optimal row-to-column assignments for dense or sparse cost matrices.

Yes. lap is a focused, well-maintained solver for a specific algorithmic problem with no known vulnerabilities, permissive licensing, and broad platform coverage. Install it if you need to solve linear assignment problems and prefer a specialized implementation over a general-purpose optimizer. The medium install friction is offset by pre-built wheels and active maintenance.

Install

lap on PyPI

pip

pip install lap

uv

uv add lap

poetry

poetry add lap

Installing lap

Before you install

Medium install friction due to compiled C++ components, but pre-built wheels cover modern Python versions (3.7–3.14) across Windows, Linux, and macOS architectures. Repository is actively maintained with recent commits.

License in practice

Released under BSD-2-Clause (permissive), allowing commercial and private use with minimal restrictions—suitable for most projects.

Quickstart

pip install lap

import lap
import numpy as np

cost, x, y = lap.lapjv(np.random.rand(4, 5), extend_cost=True)
print(cost, x, y)

Requires a C++ compiler if building from source; pre-built wheels available for common platforms eliminate this for most users.

Verify before relying

Performance comparison with scipy.optimize.linear_sum_assignment or other solvers on typical problem sizes.
Exact behavior and performance trade-off threshold between LAPJV and LAPMOD for sparse matrices.

Package facts

License	BSD-2-Clause (permissive)
Python support	supports the current Python release (>=3.7)
Install friction	medium — platform-specific wheel
Runtime dependencies	1 — numpy
Maintenance	actively maintained — 172 days since the last release
Last repo commit	2026-02-23
First released	2017-11-13
Downloads	1,749,785/month — #3,594 on PyPI (30-day window, as of 2026-08-14)
Known vulnerabilities	none known (OSV.dev, checked 2026-08-14)

Evidence: lap-0.5.13-cp310-cp310-macosx_10_9_x86_64.whl; lap-0.5.13-cp310-cp310-macosx_11_0_arm64.whl; lap-0.5.13-cp310-cp310-manylinux1_x86_64.manylinux_2_28_x86_64.manylinux_2_5_x86_64.whl; lap-0.5.13-cp310-cp310-manylinux2014_aarch64.manylinux_2_17_aarch64.manylinux_2_28_aarch64.whl; lap-0.5.13-cp310-cp310-musllinux_1_2_aarch64.whl; lap-0.5.13-cp310-cp310-musllinux_1_2_x86_64.whl; lap-0.5.13-cp310-cp310-win_amd64.whl; lap-0.5.13-cp310-cp310-win_arm64.whl; lap-0.5.13-cp311-cp311-macosx_10_9_x86_64.whl; lap-0.5.13-cp311-cp311-macosx_11_0_arm64.whl; lap-0.5.13-cp311-cp311-manylinux1_x86_64.manylinux_2_28_x86_64.manylinux_2_5_x86_64.whl; lap-0.5.13-cp311-cp311-manylinux2014_aarch64.manylinux_2_17_aarch64.manylinux_2_28_aarch64.whl; lap-0.5.13-cp311-cp311-musllinux_1_2_aarch64.whl; lap-0.5.13-cp311-cp311-musllinux_1_2_x86_64.whl; lap-0.5.13-cp311-cp311-win_amd64.whl; lap-0.5.13-cp311-cp311-win_arm64.whl; lap-0.5.13-cp312-cp312-macosx_10_13_x86_64.whl; lap-0.5.13-cp312-cp312-macosx_11_0_arm64.whl; lap-0.5.13-cp312-cp312-manylinux1_x86_64.manylinux_2_28_x86_64.manylinux_2_5_x86_64.whl; lap-0.5.13-cp312-cp312-manylinux2014_aarch64.manylinux_2_17_aarch64.manylinux_2_28_aarch64.whl

Keywords: Linear Assignment, LAPJV, LAPMOD, lap, lapx

Development Status :: 4 - BetaEnvironment :: ConsoleIntended Audience :: DevelopersIntended Audience :: EducationIntended Audience :: Science/ResearchOperating System :: MacOSOperating System :: Microsoft :: WindowsOperating System :: POSIXOperating System :: UnixProgramming Language :: Python :: 3Programming Language :: Python :: 3.10Programming Language :: Python :: 3.11Programming Language :: Python :: 3.12Programming Language :: Python :: 3.13Programming Language :: Python :: 3.14Programming Language :: Python :: 3.7Programming Language :: Python :: 3.8Programming Language :: Python :: 3.9Topic :: EducationTopic :: Education :: TestingTopic :: Scientific/EngineeringTopic :: Scientific/Engineering :: Artificial IntelligenceTopic :: Scientific/Engineering :: Image RecognitionTopic :: Scientific/Engineering :: MathematicsTopic :: Software Development