auction-assign
Fast Bertsekas epsilon-scaling forward-reverse auction algorithm for dense linear sum assignment in Rust with Python bindings.
Features
- Drop-in replacement for
scipy.optimize.linear_sum_assignment:auction_assign(cost_matrix)returns(row_ind, col_ind)as sortednp.intpNumPy arrays for square and rectangular (m x n) matrices. - Native
cost_limitpartial assignment: Supports unassigned-slack gating (cost < cost_limitwhen minimizing,cost > cost_limitwhen maximizing) so non-beneficial pairs stay unmatched without quadratic padding. - Hard edge gating (
inf/-inf): Exclude impossible associations with+inf(minimization) or-inf(maximization), raisingInfeasibleErrorif no complete matching exists whencost_limit=None. - Rich solver telemetry:
solve()returns an immutableAuctionResultwith exact totalcostandAuctionInfo(iterations,scaling_rounds,final_eps,row_prices,col_prices). - Releases the GIL: Core Rust computation runs without holding the Python GIL, scaling across threads with
ThreadPoolExecutor. - Typed Python API: Includes
py.typedand passesmypy --strict.
Installation
Requires Python 3.10+ and NumPy 1.24+.
uv add auction-assign
Or with pip:
pip install auction-assign
Quickstart
Drop-in linear_sum_assignment usage
import numpy as np
from auction_assign import auction_assign
cost_matrix = np.array(
[
[4.0, 1.0, 3.0],
[2.0, 0.0, 5.0],
[3.0, 2.0, 2.0],
]
)
row_ind, col_ind = auction_assign(cost_matrix)
total_cost = float(cost_matrix[row_ind, col_ind].sum())
print(row_ind, col_ind, total_cost)
# [0 1 2] [1 0 2] 5.0
Track-to-track fusion with gating, cost_limit, and diagnostics
In multi-target tracking and sensor fusion, impossible associations are masked with np.inf and associations worse than a gate threshold cost_limit should remain unassigned rather than forcing bad matches:
import numpy as np
from auction_assign import ConvergenceError, InfeasibleError, solve
# Pairwise track-to-measurement association costs (3 tracks x 4 measurements).
# np.inf forbids impossible pairs; track 2 has no pair below cost_limit=10.0.
costs = np.array(
[
[1.2, 8.5, np.inf, 9.0],
[np.inf, 2.4, 3.1, np.inf],
[12.0, 15.0, np.inf, 18.0],
]
)
try:
result = solve(costs, cost_limit=10.0)
except InfeasibleError as exc:
raise RuntimeError("No complete gated assignment exists") from exc
except ConvergenceError as exc:
raise RuntimeError(
f"Solver stopped at iteration {exc.iterations} (eps={exc.final_eps:.3e})"
) from exc
print("Matched tracks:", result.row_ind) # [0 1]
print("Matched meas: ", result.col_ind) # [0 1]
print(f"Total cost: {result.cost:.2f}") # 3.60
print("Iterations: ", result.info.iterations)
print("Scaling rounds:", result.info.scaling_rounds)
print("Final epsilon: ", result.info.final_eps)
For maximization problems (e.g., log-likelihood or affinity scores), pass maximize=True, use -np.inf to forbid pairs, and set cost_limit as a strict lower bound (score > cost_limit):
import numpy as np
from auction_assign import solve
scores = np.array(
[
[10.0, -np.inf, 1.0],
[-np.inf, 4.0, -2.0],
]
)
res = solve(scores, maximize=True, cost_limit=0.0)
print(res.row_ind, res.col_ind, res.cost)
# [0 1] [0 1] 14.0
API Reference
auction_assign(cost_matrix, *, maximize=False, cost_limit=None, eps_min=None, eps_factor=5.0, max_iterations=None) -> tuple[NDArray[np.intp], NDArray[np.intp]]Solves the 2D linear sum assignment problem and returns(row_ind, col_ind)withrow_indin strictly ascending order.solve(cost_matrix, *, maximize=False, cost_limit=None, eps_min=None, eps_factor=5.0, max_iterations=None) -> AuctionResultSame parameters asauction_assign, returning anAuctionResult.AuctionResult(frozen dataclass):row_ind,col_ind,cost: float,info: AuctionInfo.AuctionInfo(frozen dataclass):iterations: int,scaling_rounds: int,final_eps: float,row_prices: NDArray[np.float64],col_prices: NDArray[np.float64].InfeasibleError(ValueError): Raised whencost_limit is Noneand a matrix gated withinf(or-infwhenmaximize=True) has no complete assignment of sizemin(n_rows, n_cols).ConvergenceError(RuntimeError): Raised whenmax_iterationsis exceeded or IEEE-754f64price updates stall; provides.iterationsand.final_eps.
Note: Pairs with cost == cost_limit are excluded (strict < cost_limit when minimizing, strict > cost_limit when maximizing). NaN, -inf during minimization, and +inf during maximization raise ValueError.
Benchmarks
Compare auction_assign against scipy.optimize.linear_sum_assignment on dense random matrices (N = 20, 50, 100, 250, 500, plus 50x200) and feasible sparse-gated track-fusion matrices (90% inf entries, with a 1e15 sentinel for SciPy):
# Full benchmark table with median/min timings and optimality gap checks
uv run python benchmarks/bench_assign.py
# Fast verification run (fewer warmup/repeat iterations)
uv run python benchmarks/bench_assign.py --quick
Both modes verify solution optimality against SciPy for every benchmark case (PASS/FAIL).
Local Development
# Create/sync virtualenv and build the Rust extension
uv sync
# Run Python test suite
uv run pytest -v
# Run Rust checks and unit tests
cargo fmt --check
cargo clippy --all-targets -- -D warnings
cargo test
# Run Python lint, format check, and strict type checking
uv run ruff check .
uv run ruff format --check python tests benchmarks
uv run mypy python tests benchmarks
# Build wheel and sdist into dist/
uv build
Releasing (PyPI Trusted Publishing)
Releases are automated by .github/workflows/release.yml using PyPI OIDC Trusted Publishing (id-token: write with pypa/gh-action-pypi-publish@release/v1), so no long-lived PyPI API tokens are stored in repository secrets.
One-time repository and PyPI setup:
- In your GitHub repository, go to Settings → Environments and create an environment named
release(optionally configure required reviewers or branch/tag protection rules). - On PyPI, go to Your Account → Publishing (or your project's Publishing settings) and add a GitHub Trusted Publisher with:
- Owner:
dcollison - Repository name:
auction-assign - Workflow name:
release.yml - Environment name:
release
- Owner:
- Tag a release matching
v*and push it to GitHub:git tag v0.1.0 git push origin v0.1.0
You can also test wheel builds and smoke tests without publishing by triggering the Release workflow manually viaworkflow_dispatch.
License
MIT — see LICENSE.
Metadata
Release files for auction-assign 0.1.1
For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.
Source distribution (sdist)
| File | Size | Uploaded | Provenance | Actions |
|---|---|---|---|---|
| auction_assign-0.1.1.tar.gz | 134.5 kB | With provenance | Details for auction_assign-0.1.1.tar.gz |
Built distributions (wheels)
| File | Actions Reset | |||
|---|---|---|---|---|
| auction_assign-0.1.1-cp310-abi3-win_amd64.whl | CPython 3.10 | abi3 | Windows x86-64 | Details for auction_assign-0.1.1-cp310-abi3-win_amd64.whl |
| auction_assign-0.1.1-cp310-abi3-manylinux_2_28_x86_64.whl | CPython 3.10 | abi3 | Linux glibc 2.28+ x86-64 | Details for auction_assign-0.1.1-cp310-abi3-manylinux_2_28_x86_64.whl |
| auction_assign-0.1.1-cp310-abi3-manylinux_2_28_aarch64.whl | CPython 3.10 | abi3 | Linux glibc 2.28+ ARM64 | Details for auction_assign-0.1.1-cp310-abi3-manylinux_2_28_aarch64.whl |
| auction_assign-0.1.1-cp310-abi3-macosx_11_0_arm64.whl | CPython 3.10 | abi3 | macOS 11.0+ ARM64 | Details for auction_assign-0.1.1-cp310-abi3-macosx_11_0_arm64.whl |
| auction_assign-0.1.1-cp310-abi3-macosx_10_12_x86_64.whl | CPython 3.10 | abi3 | macOS 10.12+ x86-64 | Details for auction_assign-0.1.1-cp310-abi3-macosx_10_12_x86_64.whl |
Total release size: 1.6 MB
Release files / auction_assign-0.1.1.tar.gz
| Download URL | auction_assign-0.1.1.tar.gz |
|---|---|
| Size | 134.5 kB |
| Tags | Source |
|
SHA-256 checksum How to use checksums |
4aa2e8351481db83d3a5a00a05451f5c678708b1ca770d849f88a28ce6d9754a
|
|
BLAKE2b-256 checksum How to use checksums |
e7ba6c4d6c1629add41a05352e8ad11ec84071c06384fd798ee571d48e123e0b
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/7.0.0 CPython/3.13.16
|
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Nov 18, 2026.
Transparency logRelease files / auction_assign-0.1.1-cp310-abi3-win_amd64.whl
| Download URL | auction_assign-0.1.1-cp310-abi3-win_amd64.whl |
|---|---|
| Size | 199.4 kB |
| Tags | CPython 3.10 Windows x86-64 abi3 |
|
SHA-256 checksum How to use checksums |
a0b4f5323a016d5a0d0c626fb6a42ae10384d72c81ba48d5ed355673aded33c3
|
|
BLAKE2b-256 checksum How to use checksums |
d89e988e3d7581d0cf83867ea878f0286156751a42930a2c78a22ead27a190cc
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/7.0.0 CPython/3.13.16
|
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Nov 18, 2026.
Transparency logRelease files / auction_assign-0.1.1-cp310-abi3-manylinux_2_28_x86_64.whl
| Download URL | auction_assign-0.1.1-cp310-abi3-manylinux_2_28_x86_64.whl |
|---|---|
| Size | 324.1 kB |
| Tags | CPython 3.10 Linux glibc 2.28+ x86-64 abi3 |
|
SHA-256 checksum How to use checksums |
ee949d18cd470d549aafc3740c5891e9ff397daf23fcc95fffe3bf938b3b530a
|
|
BLAKE2b-256 checksum How to use checksums |
42d90a62a6f25cbdfa486824acb57b6515755a2a24b70531ce93c6b77933586c
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/7.0.0 CPython/3.13.16
|
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Nov 18, 2026.
Transparency logRelease files / auction_assign-0.1.1-cp310-abi3-manylinux_2_28_aarch64.whl
| Download URL | auction_assign-0.1.1-cp310-abi3-manylinux_2_28_aarch64.whl |
|---|---|
| Size | 321.6 kB |
| Tags | CPython 3.10 Linux glibc 2.28+ ARM64 abi3 |
|
SHA-256 checksum How to use checksums |
0c6caac237a02e2d4b61b6ce8f4bc0e8b6a9dd379128bcf1733eff056a925c64
|
|
BLAKE2b-256 checksum How to use checksums |
7bba53f5556c4a617fe22180441197bead874c6087b810b31b1fea02e3763fec
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/7.0.0 CPython/3.13.16
|
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Nov 18, 2026.
Transparency logRelease files / auction_assign-0.1.1-cp310-abi3-macosx_11_0_arm64.whl
| Download URL | auction_assign-0.1.1-cp310-abi3-macosx_11_0_arm64.whl |
|---|---|
| Size | 292.3 kB |
| Tags | CPython 3.10 abi3 macOS 11.0+ ARM64 |
|
SHA-256 checksum How to use checksums |
fa3cfff4e09ee13cedbe4ca92082a6bacbcf669042f76704ebbdc2087f9a165d
|
|
BLAKE2b-256 checksum How to use checksums |
678f7045414d557738c1d7c4e9291f5843dc7e060ddcc6049f46e5631aaf9fda
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/7.0.0 CPython/3.13.16
|
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Nov 18, 2026.
Transparency logRelease files / auction_assign-0.1.1-cp310-abi3-macosx_10_12_x86_64.whl
| Download URL | auction_assign-0.1.1-cp310-abi3-macosx_10_12_x86_64.whl |
|---|---|
| Size | 297.6 kB |
| Tags | CPython 3.10 abi3 macOS 10.12+ x86-64 |
|
SHA-256 checksum How to use checksums |
3613eae451bdf5acb075c60d3a334dae822aa1b7ffd345953a25c76e6a78e436
|
|
BLAKE2b-256 checksum How to use checksums |
95e7ac6f457c5a0466a1673cc9564c7d6eed248edd1be0288125da720f3f2664
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/7.0.0 CPython/3.13.16
|
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Nov 18, 2026.
Transparency logSecurity for auction-assign 0.1.1
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
Full provenance
All 6 files in this release have been uploaded with provenance metadata.
Attestation for auction_assign-0.1.1.tar.gz
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Nov 18, 2026.
Transparency logA note on package security
PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.
To learn more about protecting yourself from malicious actors, visit our package security documentation.