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
use sparse_linear_assignment::{AuctionSolver, KhoslaSolver};
fn main() -> Result<(), Box<dyn std::error::Error>> {
let weights = vec![
vec![10, 6, 14, 1],
vec![17, 18, 16]
];
let expected_cost = 1. + 16.;
let expected_person_to_object = vec![3, 2];
let expected_object_to_person = vec![u32::MAX, u32::MAX, 1, 0];
let max_rows_capacity = 10;
let max_columns_capacity = 10;
let max_arcs_capacity = 100;
let (mut solver, mut solution) = KhoslaSolver::new(
max_rows_capacity, max_columns_capacity, max_arcs_capacity);
let num_rows = weights.len();
let num_cols = weights[0].len();
solver.init(num_rows as u32, num_cols as u32)?;
(0..weights.len() as u32)
.zip(weights.iter())
.for_each(|(i, row_ref)| {
let j_indices = (0..row_ref.len() as u32).collect::<Vec<_>>();
let values = row_ref.iter().map(|v| ((*v) as f64)).collect::<Vec<_>>();
solver.extend_from_values(i, j_indices.as_slice(), values.as_slice()).unwrap();
});
let maximize = false;
solver.solve(&mut solution, maximize, None)?;
assert_eq!(solution.num_unassigned, 0);
assert_eq!(solver.get_objective(&solution), expected_cost);
assert_eq!(solution.person_to_object, expected_person_to_object);
assert_eq!(solution.object_to_person, expected_object_to_person);
Ok(())
}
See tests for more examples.