2 unstable releases
0.2.0 | Aug 6, 2021 |
---|---|
0.1.0 | Aug 3, 2021 |
#1517 in Math
22KB
422 lines
gap_solver
This crate provides an interface for specifying a generalized assignment problem, and an algorithm for finding the maximum assignment.
This code actually allows for further generalization, allowing multiple agents to perform a single task (regulated by a task budget).
Usage
Add this to your Cargo.toml
:
[dependencies]
gap_solver = "0.2.0"
Now, you can use the gap_solver
API:
use gap_solver::{solve, GapSpec};
Refer to the Rust docs for code examples.
Features
The implementation is a simple depth-first search algorithm. Therefore, it does not work well for very large problems.
The depth-first search expands most promising nodes first. True maximum assignment is guaranteed when algorithm is allowed to complete. Otherwise, the assignment printed last may be used as a best guess.
Running the code
Solving your assignment problem is easy. Just specify your assignment problem (refer to main.rs
for an example), then run it. An example problem specification is given, to make clear what syntax is expected.
Dependencies
~555KB
~11K SLoC