Sparse linear assignment
Solvers for weighted perfect matching problem (linear assignment) for bipartite graphs. Both solvers use variants of auction algorithm and implemented in Rust.
- KhoslaSolver is best suited for asymmetric k-regular sparse graphs. The algorithm is presented in this paper. It stops in finite number of iterations.
- ForwardAuctionSolver works better for symmetric assignment problems. It uses ε-scaling to speedup the auction algorithm. The implementation is based on sslap. When there is no perfect matching it enters in endless loop and stops after
max_iterations number of iterations.
Usage
```rust
use sparselinearassignment::{AuctionSolver, KhoslaSolver};
fn main() -> Result<(), Box> {
// We have 2 people and 4 objects
// weights between person i and objects j
let weights = vec![
// person 0 can connect with all objects
vec![10, 6, 14, 1],
// person 1 can connect with first 3 objects
vec![17, 18, 16]
];
let expectedcost = 1. + 16.;
let expectedpersontoobject = vec![3, 2];
// u32::MAX value is used to indicate that the corresponding object is not assigned.
// If there is no perfect matching unassigned people in person_to_object will be marked by
// u32::MAX too
let expectedobjecttoperson = vec![u32::MAX, u32::MAX, 1, 0];
// Create KhoslaSolver and AuctionSolution instances with expected capacity of rows,
// columns and arcs. We can reuse them in case there is a need to solve multiple assignment
// problems.
let maxrowscapacity = 10;
let maxcolumnscapacity = 10;
let maxarcscapacity = 100;
let (mut solver, mut solution) = KhoslaSolver::new(
maxrowscapacity, maxcolumnscapacity, maxarcs_capacity);
// init solver and CSR storage before populating weights for the next problem instance
let numrows = weights.len();
let numcols = weights[0].len();
solver.init(numrows as u32, numcols as u32)?;
// populate weights into CSR storage and init the solver
// row indices are expected to be nondecreasing
(0..weights.len() as u32)
.zip(weights.iter())
.foreach(|(i, rowref)| {
let jindices = (0..rowref.len() as u32).collect::>();
let values = rowref.iter().map(|v| ((*v) as f64)).collect::>();
solver.extendfromvalues(i, jindices.asslice(), values.asslice()).unwrap();
});
// solve the problem instance. We want to minimize the cost of the assignment.
let maximize = false;
solver.solve(&mut solution, maximize, None)?;
// We found perfect matching and all people are assigned
asserteq!(solution.numunassigned, 0);
asserteq!(solver.getobjective(&solution), expectedcost);
asserteq!(solution.persontoobject, expectedpersontoobject);
asserteq!(solution.objecttoperson, expectedobjectto_person);
Ok(())
}
```
See tests for more examples.