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

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.0
File Size Uploaded Provenance Actions
auction_assign-0.1.0.tar.gz 132.0 kB With provenance Details for auction_assign-0.1.0.tar.gz

Built distributions (wheels)

Table of built distributions (wheels) for auction-assign 0.1.0
File Actions
auction_assign-0.1.0-cp310-abi3-win_amd64.whl CPython 3.10 abi3 Windows x86-64 Details for auction_assign-0.1.0-cp310-abi3-win_amd64.whl
auction_assign-0.1.0-cp310-abi3-manylinux_2_28_x86_64.whl CPython 3.10 abi3 Linux glibc 2.28+ x86-64 Details for auction_assign-0.1.0-cp310-abi3-manylinux_2_28_x86_64.whl
auction_assign-0.1.0-cp310-abi3-manylinux_2_28_aarch64.whl CPython 3.10 abi3 Linux glibc 2.28+ ARM64 Details for auction_assign-0.1.0-cp310-abi3-manylinux_2_28_aarch64.whl
auction_assign-0.1.0-cp310-abi3-macosx_11_0_arm64.whl CPython 3.10 abi3 macOS 11.0+ ARM64 Details for auction_assign-0.1.0-cp310-abi3-macosx_11_0_arm64.whl
auction_assign-0.1.0-cp310-abi3-macosx_10_12_x86_64.whl CPython 3.10 abi3 macOS 10.12+ x86-64 Details for auction_assign-0.1.0-cp310-abi3-macosx_10_12_x86_64.whl

Total release size: 1.6 MB

Release files / auction_assign-0.1.0.tar.gz

Download URL auction_assign-0.1.0.tar.gz
Size 132.0 kB
Tags Source
SHA-256 checksum
How to use checksums
cebc45a9ff5e538ecb9bb1ed95d6d0200a13c8b7df25b649c0cf634a2fb4d0cd
BLAKE2b-256 checksum
How to use checksums
54db347e36cad6da3329959c3cd6174191a13f91843b26220bb36dab9e342f3f
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.0-cp310-abi3-win_amd64.whl

Download URL auction_assign-0.1.0-cp310-abi3-win_amd64.whl
Size 192.4 kB
Tags CPython 3.10 Windows x86-64 abi3
SHA-256 checksum
How to use checksums
dab19d735952b7024fa701f19d893f77c2d7dc8b0e840c529977f2a19e844b49
BLAKE2b-256 checksum
How to use checksums
2526efc6928db23f80c4e71d94bfdaf30dcc72d0559bb382b32265c2d18f9fe3
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.0-cp310-abi3-manylinux_2_28_x86_64.whl

Download URL auction_assign-0.1.0-cp310-abi3-manylinux_2_28_x86_64.whl
Size 342.6 kB
Tags CPython 3.10 Linux glibc 2.28+ x86-64 abi3
SHA-256 checksum
How to use checksums
203f4a0bbd359e343560100d5efa96416f33a5b7e473358698fd8c082bbad955
BLAKE2b-256 checksum
How to use checksums
78d33635085183e8f7614c90b4fd933a902cbe13ebe54bd28e4b59833a2233dd
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.0-cp310-abi3-manylinux_2_28_aarch64.whl

Download URL auction_assign-0.1.0-cp310-abi3-manylinux_2_28_aarch64.whl
Size 332.2 kB
Tags CPython 3.10 Linux glibc 2.28+ ARM64 abi3
SHA-256 checksum
How to use checksums
6007d34b24aea1cb14f8e895f8c1ff1c0e09f6578362c866c8470da30d3cab9f
BLAKE2b-256 checksum
How to use checksums
d006a6f51e690c844a441ab9e10357cff350fcf4d973e706c91d75101b9bd4be
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.0-cp310-abi3-macosx_11_0_arm64.whl

Download URL auction_assign-0.1.0-cp310-abi3-macosx_11_0_arm64.whl
Size 298.5 kB
Tags CPython 3.10 abi3 macOS 11.0+ ARM64
SHA-256 checksum
How to use checksums
66a2d5ead1cfba21e6847ea0cc304d67ff0ec78a61e6f62ff2ca89bb17358110
BLAKE2b-256 checksum
How to use checksums
c4b6e2f754f641e77e6fd2628b2e8a23c76c3152d13730d4da39750e1d511e21
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.0-cp310-abi3-macosx_10_12_x86_64.whl

Download URL auction_assign-0.1.0-cp310-abi3-macosx_10_12_x86_64.whl
Size 300.7 kB
Tags CPython 3.10 abi3 macOS 10.12+ x86-64
SHA-256 checksum
How to use checksums
432a8bfb9bdedc60443ce6b3b9d3a5de6c384716f6018b2172ace8b187e4b87a
BLAKE2b-256 checksum
How to use checksums
e93b12d9d143b9b77c79a3219528443ef7fdf2dccf531095c5f73384e89b9298
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.0

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