#search #graph #mathematics #algorithm #assignment


A solver for the generalized assignment problem

2 unstable releases

0.2.0 Aug 6, 2021
0.1.0 Aug 3, 2021

#1251 in Math

MIT license

422 lines


crates.io docs build coverage

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


Add this to your Cargo.toml:

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.


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.


~11K SLoC