#assignment #search #graph #search-algorithms #algorithm

gap_solver

A solver for the generalized assignment problem

2 unstable releases

0.2.0 Aug 6, 2021
0.1.0 Aug 3, 2021

#1517 in Math

MIT license

22KB
422 lines

gap_solver

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

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