Struct KhoslaSolver

pub struct KhoslaSolver<I: UnsignedInt + Integer> {
    pub nits: u32,
    /* private fields */
}

Solver for weighted perfect matching problem (also known as linear assignment problem) with tighter runtime complexity bound for k-left regular sparse bipartite graphs. It finds ε-optimal assignment of N people -> M objects (N <= M), by having people ‘bid’ for objects sequentially

The algorithm is presented in the article.

We denote n = max(N, M), w_max and w_min - maximum and minimum weights in the graph The worst case runtime of the algorithm for sparse k-regular is O(nk(w_max - w_min) / ε) with high probability. For complete bipartite graphs the runtime is O(n²(w_max - w_min) / ε).

If there is no perfect matching the algorithm finds good matching in finite number of steps.

Example

use sparse_linear_assignment::{AuctionSolver, KhoslaSolver};

fn main() -> Result<(), Box<dyn std::error::Error>> {
   // 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 expected_cost = 1. + 16.;
   let expected_person_to_object = 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 expected_object_to_person = 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 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);

   // init solver and CSR storage before populating weights for the next problem instance
   let num_rows = weights.len();
   let num_cols = weights[0].len();
   solver.init(num_rows as u32, num_cols 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())
       .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();
   });
   // 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
   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(())
}

Fields

nits: u32

Trait Implementations

impl<I: UnsignedInt + Integer> AuctionSolver<I, KhoslaSolver<I>> for KhoslaSolver<I>

fn new( row_capacity: usize, column_capacity: usize, arcs_capacity: usize, ) -> (Self, AuctionSolution<I>)

fn num_rows(&self) -> I

fn num_cols(&self) -> I

fn num_rows_mut(&mut self) -> &mut I

fn num_cols_mut(&mut self) -> &mut I

fn prices(&self) -> &Vec<f64>

fn i_starts_stops(&self) -> &Vec<I>

fn j_counts(&self) -> &Vec<I>

fn column_indices(&self) -> &Vec<I>

fn values(&self) -> &Vec<f64>

fn prices_mut(&mut self) -> &mut Vec<f64>

fn i_starts_stops_mut(&mut self) -> &mut Vec<I>

fn j_counts_mut(&mut self) -> &mut Vec<I>

fn column_indices_mut(&mut self) -> &mut Vec<I>

fn values_mut(&mut self) -> &mut Vec<f64>

fn solve( &mut self, solution: &mut AuctionSolution<I>, maximize: bool, eps: Option<f64>, ) -> Result<(), Error>

fn add_value(&mut self, row: I, column: I, value: f64) -> Result<(), Error>

fn extend_from_values( &mut self, row: I, columns: &[I], values: &[f64], ) -> Result<(), Error>

fn num_of_arcs(&self) -> usize

fn get_objective(&self, solution: &AuctionSolution<I>) -> f64

Returns current objective value of assignments. Checks for the sign of the first element to return positive objective.

fn get_toleration(&self, max_abs_cost: f64) -> f64

fn ecs_satisfied( &self, person_to_object: &[I], eps: f64, toleration: f64, ) -> bool

Checks if current solution is a complete solution that satisfies eps-complementary slackness.

fn init(&mut self, num_rows: I, num_cols: I) -> Result<(), Error>

fn init_solve(&mut self, solution: &mut AuctionSolution<I>, maximize: bool)

fn validate_input(&self) -> Result<(), Error>

impl<I: Clone + UnsignedInt + Integer> Clone for KhoslaSolver<I>

fn clone(&self) -> KhoslaSolver<I>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.