Linear Assignment Problem Solvers · 𝕏

🆕 What's new

^{- 2026/10/19: v0.11.0rc1 added the Rust and hybrid solvers: lapjvr, lapjvh, lapjvr_batch, and lapjvh_batch.}
^{- 2026/09/07: v0.10.0rc1 added Python 3.15 support and lapmod_batch. It improved type hints, stability, and performance.}
^{- 2025/10/31: v0.9.0 improved stability and performance across all solvers.}
^{- 2025/10/27: v0.8.0 added lapjvx_batch, lapjvxa_batch, lapjvs_batch, lapjvsa_batch and lapjvsa.}
^{- 2025/10/21: v0.7.0 added lapjvs.}
^{- 2025/10/16: v0.6.0 added lapjvx, lapjvxa, and lapjvc.}
^{- See GitHub releases for all release notes.}

Linear Assignment Problem Solvers · 𝕏

Single ✓ Batch ✓ Square ✓ Rectangular ✓

lapx started as a project to maintain Tomas Kazmar's lap, a Jonker-Volgenant solver package. It now provides additional solver functions. See the usage section for all available functions.

Read the algorithm background

lapx provides linear assignment problem solvers for dense (LAPJV ¹) and sparse (LAPMOD ²) matrices. The original lapjv and lapmod implementations come from Tomas Kazmar's lap project, based on papers ¹˒² and A. Volgenant's public domain Pascal implementation ³.

^{¹ 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:

python -m pip install lapx

Published wheels cover Python 3.9–3.15 on most platforms and architectures. See the package files for details. musllinux ARMv7 wheels include all pre-existing solvers but omit lapjvr, lapjvh, lapjvr_batch, and lapjvh_batch because native Rust build tools are unavailable.

🛠️ Other installation options

Python 3.7 and 3.8 (source builds only):

Python 3.7 and 3.8 no longer receive prebuilt wheels or automated testing. Source installation remains available with compatible build dependencies and the required C++ and current Rust toolchains:

python -m pip install --no-binary=lapx lapx

Install from GitHub (requires C++ and current Rust toolchains):

python -m pip install git+https://github.com/rathaROG/lapx.git

Build and install (requires C++ and current Rust toolchains):

git clone https://github.com/rathaROG/lapx.git
cd lapx
python -m pip install .
cd ..

Run examples outside the checkout so Python loads the installed package.

🆕 lapjvr and lapjvh families

Source builds include both families by default. Set LAPX_BUILD_RUST=0 to build only the other solvers without a Rust toolchain.

See the R/H API and build guide and the paper and reproducibility materials.

⚡ Extra performance

Since v0.9.1, lapx enables safe base optimizations by default. For source builds, environment variables control these optimizations and optional compiler flags. The optional flags might improve performance:

LAPX_BASEOPTS=0 disables the base optimization flags that LAPX adds and link-time optimization (LTO). Other compiler defaults may still apply. This switch is available since v0.9.2.

LAPX_FASTMATH=1 enables fast-math. This option may change numerical results and the treatment of NaN or infinity. R/H retains strict floating-point rules.

LAPX_NATIVE=1 enables CPU-specific tuning for GCC/Clang and Rust. Do not distribute these builds.

LAPX_LTO=0 disables LTO, including inherited LTO defaults.

The build enables LTO by default when the compiler and linker support it. LAPX_BASEOPTS=0 does not guarantee an unoptimized or debug build. Fast-math and native tuning are independent options. Both options are disabled by default. Keep both options disabled for portable release wheels.

See setup.py for more details.

🧪 Usage

Install the package as lapx and use import lap.

Show additional notes

Do not install both lap and lapx at the same time. Both packages provide the import name lap. The package that you install last replaces the other package's files.

If you only need lapjv and lapmod, the original lap is sufficient. Choose lapx for additional fixes, batch processing, output formats, and solvers. It also improves stability and performance.

ℹ️ Cost values

The caller must check cost values for lapjv, lapjvx, lapjvxa, lapjvs, lapjvsa, lapjvr, lapjvh, and their batch variants. These solvers omit this check to reduce overhead for repeated calls. Before you call these solvers, prepare costs without NaN (not a number) or negative infinity. Results with these values are undefined. Positive infinity (np.inf) can represent a forbidden assignment.

lapjvc treats NaN and either infinity as forbidden assignments. lapmod checks its sparse arrays. Stored costs must be finite, non-negative, and less than lap.LARGE.

With return_cost=True (the default), the solvers sum total costs in float64 from the original costs, even when they solve in float32. Set return_cost=False when you need only assignments. This skips the total-cost calculation.

Cost limits and filtering after solving

lapjv, lapjvx, lapjvxa, lapjvr, and lapjvh accept cost_limit. The JVX and R/H batch solvers support it too. The value must be finite or positive infinity. The default np.inf applies no finite cost limit. With a finite limit, the solver considers leaving items unmatched during optimization. Unmatched rows and columns each incur half the limit during optimization; returned totals exclude those penalties. JV/JVX solvers expand each nonempty (N, M) problem to shape (N+M, N+M), which requires more memory and can slow the solve. R/H handles finite limits without square padding.

Some workflows, such as object tracking, apply a cost threshold after solving. For this approach, leave cost_limit=np.inf. Then remove assignment pairs whose costs exceed the threshold. Filtering after the solve can produce different assignments from using cost_limit. It removes pairs without solving again, so it cannot replace discarded matches.

Terms used in the examples

A cost matrix contains the cost of each possible assignment from a row to a column.
A mapping array gives the assigned index for each row or column.
An assignment pair contains a row index and its assigned column index.
B is the batch size. N and M are the matrix dimensions. K is the number of assignment pairs.
A dtype is an array's data type, such as float32 or float64.
The global interpreter lock (GIL) limits concurrent execution of Python code within one interpreter.

🅰️ Single-matrix Solvers 📄

1. The original function `lapjv`

lapjv supports square and rectangular cost matrices. It returns optimal assignments as mapping arrays x (size N) and y (size M). If return_cost=True, it also returns the total cost. See the API documentation for details.

import lap
import numpy as np

cost = np.random.rand(100, 150)
total, x, y = lap.lapjv(cost, extend_cost=True)
valid = x >= 0
pairs = np.column_stack((np.arange(len(x))[valid], x[valid]))

lapjv returns (total, x, y) by default, or (x, y) with return_cost=False. For a cost matrix cost with shape (N, M), x has N entries and y has M entries. x[i] gives the assigned column for row i. y[j] gives the assigned row for column j. Unmatched entries are -1.

For example, x = [1, 0] means row 0 uses column 1 and row 1 uses column 0. The example above converts mapping arrays to pairs; use lapjvx for aligned row and column indices, as in SciPy. See the original lapjv documentation at gatagat/lap.

Show lapjvx

2. The new function `lapjvx`

lapjvx uses the same algorithm as lapjv. It returns aligned row and column indices, as in SciPy's linear_sum_assignment. See the API documentation for details.

import lap
import numpy as np

cost = np.random.rand(100, 150)
total, rows, cols = lap.lapjvx(cost, extend_cost=True)
pairs = np.column_stack((rows, cols))

See the object tracking benchmark to compare lapjvx with other solvers.

Show lapjvxa

3. The new function `lapjvxa`

lapjvxa provides the same solver behavior as lapjvx. It returns assignment pairs with shape (K, 2). The caller does not need to convert the output. The pair format also suits tracking workflows that apply a cost threshold after solving, as described in Cost values. See the API documentation for details.

import lap
import numpy as np

cost = np.random.rand(100, 150)
total, pairs = lap.lapjvxa(cost, extend_cost=True)

Show lapjvc

4. The new function `lapjvc`

lapjvc extends Christoph Heindl's py-lapsolver. It returns the same output format as lapjvx and SciPy's linear_sum_assignment. See the API documentation for details.

import lap
import numpy as np

cost = np.random.rand(100, 150)
total, rows, cols = lap.lapjvc(cost)
pairs = np.column_stack((rows, cols))

Show lapjvs

5. The new function `lapjvs`

lapjvs extends Vadim Markovtsev's lapjv. Its scalar kernel does not require AVX2 instructions. It supports square and rectangular cost matrices. It can return either of these output formats:

Aligned index arrays, as in SciPy's linear_sum_assignment.
Mapping arrays x and y, as in lapjv.

See the wrapper documentation for details.

import lap
import numpy as np

cost = np.random.rand(100, 150)
total, rows, cols = lap.lapjvs(cost, jvx_like=True)
pairs = np.column_stack((rows, cols))

Show lapjvsa

6. The new function `lapjvsa`

lapjvsa provides the same solver behavior as lapjvs. It returns assignment pairs with shape (K, 2). The caller does not need to convert the output. See the wrapper documentation for details.

import lap
import numpy as np

cost = np.random.rand(100, 150)
total, pairs = lap.lapjvsa(cost)

Show lapmod

7. The original function `lapmod`

See the wrapper documentation for details.

import lap
import numpy as np

n = 3
cc = np.array([3.0, 1.0, 1.0, 4.0, 2.0, 1.0])  # Costs grouped by row
ii = np.array([0, 2, 4, 6])  # Row offsets into cc
kk = np.array([0, 1, 0, 2, 1, 2])  # Column indices for each cost
total, x, y = lap.lapmod(n, cc, ii, kk)

8. Rust and hybrid functions `lapjvr` and `lapjvh`

R/H were about 3–10× faster than SciPy across benchmarks; see benchmark.md.

lapjvr and lapjvh share a Rust Jonker-Volgenant implementation. For square problems with infinite cost_limit, lapjvh uses C++ completion. Both return aligned row and column indices, like lapjvx; use output="pairs" for the pair layout of lapjvxa.

import lap
import numpy as np

cost = np.random.rand(100, 150)
total, rows, cols = lap.lapjvr(cost, extend_cost=True)
total, pairs = lap.lapjvh(cost, extend_cost=True, output="pairs")

Both support rectangular inputs (extend_cost=True), finite cost_limit, and precision="native", "float32", or "float64". Rectangular and finite-limit problems are solved without square padding. See the API guide for full signatures, return types, and precision rules.

If you don't need the other LAPX solvers, you can use the dedicated laprust (Rust, from lapjvr) or lapcpp (C++) package instead; each provides the same options through lapjv and lapjv_batch. The paper (repository) describes this solver and compares it with the other LAPX solvers and SciPy.

🅱️ Batch Solvers 🗂️

All batch solvers use the same n_threads rules:

0 (the default) or None selects the CPU count from os.cpu_count(), capped by the batch size. If the CPU count is unavailable, the solver uses one worker.
1 or a negative value runs sequentially.
Positive values select the worker count. The number of workers cannot exceed the batch size.
Explicit positive values are not capped by the detected CPU count.
Empty and single-item batches do not create a thread pool.

1. The new function `lapjvx_batch`

lapjvx_batch runs lapjvx on a batch of cost matrices with shape (B, N, M). See the wrapper documentation for details.

import lap
import numpy as np

batch_costs = np.random.rand(500, 100, 150)  # (B, N, M)
totals, rows, cols = lap.lapjvx_batch(batch_costs, extend_cost=True, n_threads=2)
print(f"total costs = {totals.sum()}")
pairs_7 = np.column_stack((rows[7], cols[7]))  # (K_b, 2)
print(f"pairs_7.shape = {pairs_7.shape}")

Show lapjvxa_batch

2. The new function `lapjvxa_batch`

lapjvxa_batch runs lapjvxa on a batch of cost matrices with shape (B, N, M). See the wrapper documentation for details.

import lap
import numpy as np

batch_costs = np.random.rand(500, 100, 150)  # (B, N, M)
totals, pairs = lap.lapjvxa_batch(batch_costs, extend_cost=True, n_threads=2)
print(f"total costs = {totals.sum()}")
print(f"pairs[7].shape = {pairs[7].shape}")

Show lapjvs_batch

3. The new function `lapjvs_batch`

lapjvs_batch runs lapjvs on a batch of cost matrices with shape (B, N, M). See the wrapper documentation for details.

import lap
import numpy as np

batch_costs = np.random.rand(500, 100, 150)  # (B, N, M)
totals, rows, cols = lap.lapjvs_batch(batch_costs, extend_cost=True, n_threads=2)
print(f"total costs = {totals.sum()}")
pairs_7 = np.column_stack((rows[7], cols[7]))  # (K_b, 2)
print(f"pairs_7.shape = {pairs_7.shape}")

Show lapjvsa_batch

4. The new function `lapjvsa_batch`

lapjvsa_batch runs lapjvsa on a batch of cost matrices with shape (B, N, M). See the wrapper documentation for details.

import lap
import numpy as np

batch_costs = np.random.rand(500, 100, 150)  # (B, N, M)
totals, pairs = lap.lapjvsa_batch(batch_costs, extend_cost=True, n_threads=2)
print(f"total costs = {totals.sum()}")
print(f"pairs[7].shape = {pairs[7].shape}")

Show lapmod_batch

5. The new function `lapmod_batch`

lapmod_batch solves a sequence of sparse (n, cc, ii, kk) problems. It uses the same inputs and checks as lapmod. Each problem must be square. Problem sizes and numbers of stored entries can differ.

Results keep the input order. For problem b, x_list[b] maps rows to columns and y_list[b] maps columns to rows. Both lists contain the same int32 arrays as the single solver.

import lap
import numpy as np

problems = [
    (2, np.array([1.0, 4.0, 3.0, 2.0]),
     np.array([0, 2, 4]), np.array([0, 1, 0, 1])),
    (3, np.array([4.0, 1.0, 3.0]),
     np.array([0, 1, 2, 3]), np.array([2, 0, 1])),
]
totals, x_list, y_list = lap.lapmod_batch(problems, n_threads=2)
print(totals)  # [3. 8.]
print(x_list[1])  # [2 0 1]

# Skip total-cost calculation when only the mappings are needed.
x_list, y_list = lap.lapmod_batch(problems, return_cost=False, n_threads=2)

With the default fast=True, the native solver releases the GIL. Independent problems can then run concurrently. Python code that checks inputs and calculates total costs can limit speedup. With fast=False, the Python solver's performance depends largely on the GIL. fp_version selects the native path-search version, as in lapmod.

Do not change input arrays while the solver runs. If a problem raises an exception, the caller receives it after the thread pool stops.

See the wrapper documentation for the full signature and return types.

6. `lapjvr_batch` and `lapjvh_batch`

lapjvr_batch and lapjvh_batch run their single-matrix solvers on a batch of cost matrices with shape (B, N, M). Results keep the input order and use the same output and precision options as the single-matrix calls.

import lap
import numpy as np

batch_costs = np.random.rand(500, 100, 150)  # (B, N, M)
totals, rows, cols = lap.lapjvr_batch(batch_costs, extend_cost=True, n_threads=2)
totals, pairs = lap.lapjvh_batch(batch_costs, extend_cost=True, output="pairs", n_threads=2)

The n_threads rules above apply; automatic mode may run small workloads serially. See the batch API guide for return types and native worker details.

🏆 Benchmark and Test

See the benchmark guide for commands, repeat controls, timing methods, and historical results.

See the solver test guide and the build and packaging guide to run the checks.

Name		Name	Last commit message	Last commit date
.github		.github
benchmarks		benchmarks
lap		lap
src		src
tests		tests
.gitignore		.gitignore
LICENSE		LICENSE
MANIFEST.in		MANIFEST.in
NOTICE		NOTICE
README.md		README.md
benchmark.md		benchmark.md
pyproject.toml		pyproject.toml
setup.py		setup.py

Navigation Menu

Repository navigation

About

Repository files navigation

Linear Assignment Problem Solvers · 𝕏

💽 Installation

Install from PyPI:

Python 3.7 and 3.8 (source builds only):

Install from GitHub (requires C++ and current Rust toolchains):

Build and install (requires C++ and current Rust toolchains):

🧪 Usage

ℹ️ Cost values

🅰️ Single-matrix Solvers 📄

1. The original function `lapjv`

2. The new function `lapjvx`

3. The new function `lapjvxa`

4. The new function `lapjvc`

5. The new function `lapjvs`

6. The new function `lapjvsa`

7. The original function `lapmod`

8. Rust and hybrid functions `lapjvr` and `lapjvh`

🅱️ Batch Solvers 🗂️

1. The new function `lapjvx_batch`

2. The new function `lapjvxa_batch`

3. The new function `lapjvs_batch`

4. The new function `lapjvsa_batch`

5. The new function `lapmod_batch`

6. `lapjvr_batch` and `lapjvh_batch`

🏆 Benchmark and Test

📝 License

About

Releases

Packages

Used by

Contributors

Languages

Latest commit

History

Folders and files

Repository files navigation

Linear Assignment Problem Solvers · 𝕏

💽 Installation

Install from PyPI:

Python 3.7 and 3.8 (source builds only):

Install from GitHub (requires C++ and current Rust toolchains):

Build and install (requires C++ and current Rust toolchains):

🧪 Usage

ℹ️ Cost values

🅰️ Single-matrix Solvers 📄

1. The original function lapjv

2. The new function lapjvx

3. The new function lapjvxa

4. The new function lapjvc

5. The new function lapjvs

6. The new function lapjvsa

7. The original function lapmod

8. Rust and hybrid functions lapjvr and lapjvh

🅱️ Batch Solvers 🗂️

1. The new function lapjvx_batch

2. The new function lapjvxa_batch

3. The new function lapjvs_batch

4. The new function lapjvsa_batch

5. The new function lapmod_batch

6. lapjvr_batch and lapjvh_batch

🏆 Benchmark and Test

📝 License

About

Topics

Resources

Stars

Watchers

Forks

Releases

Packages

Used by

Contributors

Languages

1. The original function `lapjv`

2. The new function `lapjvx`

3. The new function `lapjvxa`

4. The new function `lapjvc`

5. The new function `lapjvs`

6. The new function `lapjvsa`

7. The original function `lapmod`

8. Rust and hybrid functions `lapjvr` and `lapjvh`

1. The new function `lapjvx_batch`

2. The new function `lapjvxa_batch`

3. The new function `lapjvs_batch`

4. The new function `lapjvsa_batch`

5. The new function `lapmod_batch`

6. `lapjvr_batch` and `lapjvh_batch`