SSLAP
This library provides implementations for solvers for Super Sparse Linear Assignment Problems.
An assignment problem is one where a one-to-one assignment has to be made between two sets, where each assignment has an associated cost.
In super sparse assignment problems, typically less than 1% of all feasible assignments are allowed.
This library provides a Cython implementation of the Auction Algorithm [1], which is well suited for super sparse problems. It is one in which people in one set 'bid' for objects in the other set, driving up their prices in order to find an optimal assignment.
Also provided is an implementation of the Hopcroft-Karp Algorithm [2] for finding a maximum matching in a bipartite graph. This is used by the Auction solver to check that a given problem has a valid solution.
Installation
Tested on Windows (Python 3.8):
pip install sslap
Tested on Linux (Python 3.7):
pip install git+https://github.com/OllieBoyne/sslap.git
Usage
- For usage of the Auction Algorithm, view
examples/test_auction.py - For usage of Hopcroft-Karp, view
examples/test_feasibility.py
Benchmarking
The algorithm is best suited for large and sparse problems, where it outperforms scipy.optimize.linear_sum_assignment.
See below for some timed comparisons of the runtime for problems of varying density (% of valid entries in the matrix) and matrix size.
Notes
- A matrix passed into from_matrix requires positive values only, and -1 indicates invalid values.
- If the matrix is sufficiently large (experiments show N > 120k), auction_solve may crash unexpectedly. To avoid this, pass in the argument
cardinality_check=Falseto auction_solve
[1] Bertsekas, D. A Distributed Algorithm for the Assignment Problem (1979)
[2] Hopcroft J. Karp, R. An n^(5/2) algorithm for maximum matchings in bipartite graphs (1973)
1 maintainer
Release files for sslap 0.2.5
For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.
Source distribution (sdist)
| File | Size | Uploaded | |
|---|---|---|---|
| sslap-0.2.5.tar.gz | 277.2 kB | Details |
Built distribution (wheel)
| File | Interpreter | ABI | Platform | Reset |
|---|---|---|---|---|
| sslap-0.2.5-cp38-cp38-win_amd64.whl | CPython 3.8 | CPython 3.8 | Windows x86-64 | Details |
Total release size: 616.2 kB
Release files / sslap-0.2.5.tar.gz
| Download URL | sslap-0.2.5.tar.gz |
|---|---|
| Size | 277.2 kB |
| Tags | Source |
|
SHA-256 checksum How to use checksums |
1ea37f44f0b5d4735791d940bc025735eb6e6f761fb0c58a5f3e7f58e71d95ba
|
|
BLAKE2b-256 checksum How to use checksums |
8cc44d9689ef4d66baca32f44cb7142ccddc62c01e7fd7d6e093022e8b7ab1a9
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/3.3.0 pkginfo/1.6.1 requests/2.25.1 setuptools/51.1.0 requests-toolbelt/0.9.1 tqdm/4.55.0 CPython/3.8.5
|
Release files / sslap-0.2.5-cp38-cp38-win_amd64.whl
| Download URL | sslap-0.2.5-cp38-cp38-win_amd64.whl |
|---|---|
| Size | 339.0 kB |
| Tags | CPython 3.8 Windows x86-64 |
|
SHA-256 checksum How to use checksums |
f82019c2611dbd190ef5ef079a187c8b8021e7aea9a6a6f411f9b156681a13c7
|
|
BLAKE2b-256 checksum How to use checksums |
11cfba59685b899ae7c72782efaace1eca2c12d390c58292fd00cae45d2fdf9f
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/3.3.0 pkginfo/1.6.1 requests/2.25.1 setuptools/51.1.0 requests-toolbelt/0.9.1 tqdm/4.55.0 CPython/3.8.5
|
