fastlap

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

fastlap solves the linear assignment problem — minimum-cost bipartite matching, or its dual, maximum weight matching via maximize=True — at high speed from Python. It ships six algorithmically distinct solvers (LAPJV, Hungarian, LAPMOD, Dantzig, Auction, Subgradient) behind a single solve_lap() call, with optional parallel batch solving and weighted cost support.

If you work with object tracking, task scheduling, resource allocation, matching algorithms, or combinatorial optimisation, fastlap gives you an drop-in Rust accelerator for the core assignment step.

Why fastlap?

Installation

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

# Or via pip (once published)
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

maximize is also accepted by solve_lap_batch and solve_lap_weighted.

Six Algorithms

Each algorithm is a genuinely different implementation, not a relabeled wrapper around a shared core — they use different data structures and pivoting/search strategies, and (correctness aside) have different practical performance characteristics as a result.

>>> fastlap.get_supported_algorithms()
['lapjv', 'hungarian', 'lapmod', 'subgradient', 'auction', 'dantzig']

Select with the algorithm parameter — all return the same format: (cost, row_assign, col_assign). All six handle rectangular matrices.

lapmod is the only algorithm that actually reads a scipy.sparse.csr_matrix as sparse — the other five densify it first (fine for moderate sizes, wasteful for a large mostly-empty matrix):

import scipy.sparse as sp
import fastlap

# Only some (row, col) pairs are valid candidates — everything else is
# implicitly forbidden (infinite cost), the same convention scipy uses.
sparse_cost = sp.random(5000, 5000, density=0.003, format="csr")
total, rows, cols = fastlap.solve_lap(sparse_cost, algorithm="lapmod")

Batch Solving (Parallel)

Solve hundreds of independent assignment problems across all CPU cores:

import numpy as np
import fastlap

matrices = [np.random.rand(50, 50) for _ in range(500)]
results = fastlap.solve_lap_batch(matrices, algorithm="lapjv")

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

Uses Rayon internally — linear speedup with core count.

Weighted Costs

Multiply each entry by a per-element weight before solving (useful in tracking pipelines where confidence scores gate assignment costs):

import numpy as np
import fastlap

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.

Input Validation

fastlap rejects invalid inputs with clear error messages:

import fastlap, numpy as np

# NaN
fastlap.solve_lap(np.array([[1, float("nan")], [3, 4]]), "lapjv")
# ValueError: Matrix contains NaN at position [0, 1]

# Inf
fastlap.solve_lap(np.array([[1, float("inf")], [3, 4]]), "lapjv")
# ValueError: Matrix contains infinite value at position [0, 1]

# Empty
fastlap.solve_lap(np.array([]), "lapjv")
# ValueError: Matrix must not be empty

Use Cases

• Object tracking — frame-to-frame data association (Hungarian tracker, SORT, DeepSORT)
• Task scheduling — assign jobs to machines minimising total cost
• Resource allocation — match supply to demand in logistics
• Graph matching — bipartite matching in network analysis
• Experimental design — optimal matching in causal inference
• Robotics — multi-robot task allocation

Performance Benchmarks

Run the built-in benchmark yourself:

uv run pytest tests/test_correctness.py -k benchmark -v

Or use the comparison script:

uv run python examples/examples.py

Citation

If you use fastlap in research, please cite:

@software{fastlap2025,
  author       = {Le Duc Minh},
  title        = {fastlap: A High-Performance Python LAP Solver Powered by Rust},
  year         = {2025},
  publisher    = {GitHub},
  url          = {https://github.com/LakoreAI/fastlap},
  note         = {Python-Rust implementation of LAPJV, Hungarian, LAPMOD, Dantzig, Auction, and Subgradient algorithms}
}

FAQ

Contributing

See CONTRIBUTING.md for development setup, testing, and how to add a new algorithm.

License

MIT — see LICENSE.

Contact

Open an issue at github.com/LakoreAI/fastlap/issues.