fastlap

Fast Linear Assignment Problem (LAP) Solver for Python — Powered by Rust

📖 Full documentation: minlee0210.github.io/fastlap

fastlap solves the linear assignment problem — minimum-cost bipartite matching, maximum weight matching (maximize=True), bottleneck assignment (solve_lbap), and ranked $K$-best assignments (solve_lap_kbest) — at high speed from Python. It ships eleven algorithmically distinct solvers behind a single solve_lap() call, with parallel batch solving (3D ndarray batches + n_threads), gating threshold support (cost_limit), optimal dual extraction (solve_lap_duals), weighted costs, and drop-in compatibility layers for SciPy and lap/lapx.

If you work with object tracking (ByteTrack, BoT-SORT, DeepSORT), task scheduling, resource allocation, feature matching, or combinatorial optimisation, fastlap gives you a drop-in Rust accelerator for the core assignment step.

Why fastlap?

Installation

# From source (requires Rust toolchain)
git clone https://github.com/MinLee0210/fastlap.git
cd fastlap
pip install maturin && maturin develop --release

# Or via pip
pip install fastlap

Requirements: Python ≥ 3.9, NumPy ≥ 1.26.

Quick Start

import fastlap

cost_matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
]

total_cost, row_assign, col_assign = fastlap.solve_lap(cost_matrix, algorithm="lapjv")

print(total_cost)      # 15.0
print(row_assign)      # [0, 1, 2]
print(col_assign)      # [0, 1, 2]

solve_lap accepts plain Python lists, NumPy arrays, or SciPy CSR sparse matrices. Unassigned entries return None:

import numpy as np

# Rectangular 2×3 matrix — one column is unassigned
cost, rows, cols = fastlap.solve_lap(
    np.array([[1, 2, 3], [4, 5, 6]], dtype=np.float64), algorithm="lapjv"
)
print(cols)  # [0, 1, None] — column 2 unassigned

Pass maximize=True for maximum-weight matching instead of negating the matrix yourself:

profit = np.array([[1, 9], [9, 1]], dtype=np.float64)
total, rows, cols = fastlap.solve_lap(profit, algorithm="lapjv", maximize=True)
print(total)  # 18.0 — pairs the high-value cells instead of the low-cost ones

Cost Limit / Gating Threshold (Tracking & Data Association)

Reject assignments exceeding a maximum allowable cost (essential for Multi-Object Tracking like ByteTrack):

# Threshold cost at 10.0 — any pair exceeding 10.0 is unassigned (None)
cost, rows, cols = fastlap.solve_lap(cost_matrix, cost_limit=10.0)

Drop-in Compatibility Layers

1. Drop-in for scipy.optimize.linear_sum_assignment

from fastlap.compat import linear_sum_assignment

# Returns (row_ind, col_ind) int64 ndarrays exactly like SciPy
row_ind, col_ind = linear_sum_assignment(cost_matrix)

2. Drop-in for lap.lapjv / lapx.lapjv (ByteTrack / YOLO MOT)

import fastlap.lap as lap

# Matches lap.lapjv signature and return format (opt_cost, x, y)
opt_cost, x, y = lap.lapjv(cost_matrix, extend_cost=True, cost_limit=0.5)

Eleven Algorithms

>>> fastlap.get_supported_algorithms()
['lapjv', 'hungarian', 'lapmod', 'lapjvsp', 'subgradient', 'auction', 'dantzig', 'sinkhorn', 'ssp', 'cost_scaling', 'greedy']

Ranked $K$-Best Assignments (Murty's Algorithm)

Find the top $K$ ranked alternative assignments in increasing order of cost:

# Returns up to k solutions: [(cost_1, rows_1, cols_1), (cost_2, rows_2, cols_2), ...]
top_k_solutions = fastlap.solve_lap_kbest(cost_matrix, k=5)

Useful in Multi-Hypothesis Tracking (MHT), target tracking under ambiguous detections, and structural bioinformatics.

Linear Bottleneck Assignment Problem (LBAP)

Find an assignment that minimises the maximum cost edge ($\min_\pi \max_i C_{i, \pi(i)}$):

bottleneck_cost, rows, cols = fastlap.solve_lbap(cost_matrix)

Also available in parallel via fastlap.solve_lbap_batch(matrices).

Batch Solving (Parallel)

Solve hundreds of independent assignment problems across all CPU cores via Rayon. A batch can be a plain list of matrices, or a single 3D (B, N, M) ndarray, and the worker count is controllable:

import numpy as np
import fastlap

matrices = np.random.rand(500, 50, 50)          # 500 × (50×50), stacked
results = fastlap.solve_lap_batch(matrices, algorithm="lapjv", n_threads=8)

# Each result is (cost, row_assign, col_assign)
costs = [r[0] for r in results]

Optimal Duals (solve_lap_duals)

Beyond the primal assignment, solve_lap_duals returns the optimal dual potentials u (rows) and v (columns): feasible (u[i] + v[j] <= cost[i][j]), tight on every matched pair, with total_cost == sum(u) + sum(v).

cost, rows, cols, u, v = fastlap.solve_lap_duals(cost_matrix, algorithm="lapjv")
# u[i] / v[j] are the shadow prices of row/column resources

Supported for the exact dual-convergent algorithms (lapjv, subgradient, sinkhorn, dantzig); maximization is not supported.

Benchmarks

lapjv is the production default for dense matrices; lapjvsp/lapmod for scipy.sparse input. The other exact solvers (hungarian, dantzig, ssp, cost_scaling, sinkhorn, subgradient) trade throughput for a particular formulation, and auction/greedy are approximate. Measured numbers and a production-readiness breakdown live in the docs.

A repeatable harness (benchmarks/benchmark.py) times every algorithm — best-of-N, with a correctness cross-check against lapjv on every run — across dense/rectangular/sparse-CSR problems, 3D batches, and K-best solves, and can write JSON for regression tracking:

uv run python benchmarks/benchmark.py            # full sweep
uv run python benchmarks/benchmark.py --quick    # small, fast sanity run
uv run python benchmarks/benchmark.py --json out.json

Visualisation & Terminal Demos

uv run python examples/terminal_ui.py heatmap          # ANSI heatmap + assignment
uv run python examples/terminal_ui.py compare          # all algorithms head-to-head
uv run python examples/bipartite_assignment.py         # bipartite graph PNG (needs matplotlib+networkx)
uv run python examples/visualize_assignment.py         # matplotlib heatmap overlay

Weighted Costs

Multiply each entry by a per-element weight during optimization:

cost    = np.array([[1, 2], [3, 4]], dtype=np.float64)
weights = np.array([[1, 0.5], [0.5, 1]], dtype=np.float64)

total, rows, cols = fastlap.solve_lap_weighted(cost, weights, algorithm="lapjv")

The returned total_cost is computed from the original (unweighted) matrix.

Use Cases

• Object tracking — frame-to-frame data association (ByteTrack, BoT-SORT, DeepSORT, SORT)
• Multi-Hypothesis Tracking (MHT) — ranked $K$-best associations via Murty's algorithm
• Task scheduling & LBAP — assign jobs to machines minimising total or bottleneck cost
• Resource allocation — match supply to demand in logistics
• Feature matching — point set registration and bipartite graph matching
• Robotics — multi-robot task allocation

License

MIT — see LICENSE.