Skip to content

fastlap

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

PyPI version Python License: MIT CI

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.

Get started View on GitHub

Why fastlap?

fastlap (Rust) scipy.optimize lap / lapx (C++)
Speed Sub-ms on 100×100 ~ms ~ms
Algorithms 11 (algorithmically distinct) + LBAP + K-Best 1 1
Gating threshold cost_limit=... built-in manual filtering cost_limit
Bottleneck (LBAP) solve_lbap built-in no no
K-Best (Murty) solve_lap_kbest built-in no no
Optimal duals solve_lap_duals (u, v) no no
Batch parallel solve_lap_batch (Rayon, (B,N,M) + n_threads) manual manual
Weighted costs built-in no no
Maximize mode maximize=True manual negation manual negation
Sparse-aware solve LAPMOD & LAPJVsp skip densification densifies densifies
Rectangular matrices yes yes yes
Drop-in compat scipy, lap.lapjv & lapx helpers baseline baseline
Type stubs full fastlap.pyi yes no
Dependencies numpy numpy + scipy numpy

At a glance

  • Eleven algorithms, one API

    LAPJV, Hungarian, LAPMOD, LAPJVsp, Dantzig, Auction, Subgradient, Sinkhorn, SSP, Cost Scaling, and Greedy — all behind solve_lap(algorithm=...).

    Browse algorithms

  • Tracking-ready gating

    cost_limit rejects assignments above (or below, in maximize mode) a threshold — essential for multi-object tracking data association.

    Cost limit

  • Ranked K-best

    Murty's algorithm returns the top-K alternative assignments in increasing-cost order — built for multi-hypothesis tracking.

    K-best assignments

  • Drop-in replacements

    Swap in fastlap for scipy.optimize.linear_sum_assignment or lap.lapjv with a one-line import change.

    Compatibility layers

Quick taste

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]

Continue to Getting Started for installation and a full walkthrough, or jump straight to the API Reference.

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