dagabo98 / sslap Goto Github PK

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.

Tested on Windows (Python 3.8):

pip install sslap

Tested on Linux (Python 3.7):

pip install git+https://github.com/DAGABO98/sslap.git

• For usage of the Auction Algorithm, view examples/test_auction.py
• For usage of Hopcroft-Karp, view examples/test_feasibility.py

• 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=False to 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)