Skip to main content

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 sorted np.intp NumPy arrays for square and rectangular (m x n) matrices.
  • Native cost_limit partial assignment: Supports unassigned-slack gating (cost < cost_limit when minimizing, cost > cost_limit when maximizing) so non-beneficial pairs stay unmatched without quadratic padding.
  • Hard edge gating (inf / -inf): Exclude impossible associations with +inf (minimization) or -inf (maximization), raising InfeasibleError if no complete matching exists when cost_limit=None.
  • Rich solver telemetry: solve() returns an immutable AuctionResult with exact total cost and AuctionInfo (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.typed and passes mypy --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) with row_ind in strictly ascending order.
  • solve(cost_matrix, *, maximize=False, cost_limit=None, eps_min=None, eps_factor=5.0, max_iterations=None) -> AuctionResult Same parameters as auction_assign, returning an AuctionResult.
  • 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 when cost_limit is None and a matrix gated with inf (or -inf when maximize=True) has no complete assignment of size min(n_rows, n_cols).
  • ConvergenceError(RuntimeError): Raised when max_iterations is exceeded or IEEE-754 f64 price updates stall; provides .iterations and .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:

  1. In your GitHub repository, go to Settings → Environments and create an environment named release (optionally configure required reviewers or branch/tag protection rules).
  2. 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
  3. 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 via workflow_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)

Source distribution for auction-assign 0.1.1
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)

Table of built distributions (wheels) for auction-assign 0.1.1
File Actions
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 log

Release 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 log

Release 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 log

Release 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 log

Release 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 log

Release 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 log

Security 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.

Select from 6 files

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 log

A 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.

Release history Release notifications | RSS feed

This release

0.1.1 This release

6 release files Full provenance

Anthropic, PBC Visionary sponsor Bloomberg Visionary sponsor Hudson River Trading Visionary sponsor Meta Visionary sponsor NVIDIA Visionary sponsor Microsoft Sustainability sponsor Depot Continuous Integration AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page