---
id: lap
version: "0.5.13"
license: BSD-2-Clause
license_treatment: permissive
maintenance: active
---

# lap — Linear Assignment Problem solver (LAPJV/LAPMOD).

License: permissive · Maintenance: active · Downloads: 1.7M/mo

## 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 above — 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

pip install lap
uv add lap
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_current
- Install friction: medium
- Maintenance: active
- Downloads: 1.7M/month (top 5,000 on PyPI)
- Known vulnerabilities: none known

## Tags

linear assignment problem solver, optimal matching algorithm, LAPJV LAPMOD implementation, cost matrix assignment, bipartite matching optimization, Hungarian algorithm alternative, assignment cost minimization, optimization, graph-algorithms, numerical-computing

[View on SkillFed](https://skillfed.io/packages/lap) · [View on PyPI](https://pypi.org/project/lap/)