Struct sparse_linear_assignment::ksparse::KhoslaSolver [−][src]
pub struct KhoslaSolver<I: UnsignedInt + Integer> { pub nits: u32, // some fields omitted }
Expand description
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), wmax and wmin - maximum and minimum weights in the graph The worst case runtime of the algorithm for sparse k-regular is O(nk(wmax - wmin) / ε) with high probability. For complete bipartite graphs the runtime is O(n2(wmax - wmin) / ε).
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>
[src]
impl<I: UnsignedInt + Integer> AuctionSolver<I, KhoslaSolver<I>> for KhoslaSolver<I>
[src]fn new(
row_capacity: usize,
column_capacity: usize,
arcs_capacity: usize
) -> (Self, AuctionSolution<I>)
[src]
row_capacity: usize,
column_capacity: usize,
arcs_capacity: usize
) -> (Self, AuctionSolution<I>)
fn num_rows(&self) -> I
[src]
fn num_cols(&self) -> I
[src]
fn num_rows_mut(&mut self) -> &mut I
[src]
fn num_cols_mut(&mut self) -> &mut I
[src]
fn prices(&self) -> &Vec<f64>
[src]
fn i_starts_stops(&self) -> &Vec<I>
[src]
fn j_counts(&self) -> &Vec<I>
[src]
fn column_indices(&self) -> &Vec<I>
[src]
fn values(&self) -> &Vec<f64>
[src]
fn prices_mut(&mut self) -> &mut Vec<f64>
[src]
fn i_starts_stops_mut(&mut self) -> &mut Vec<I>
[src]
fn j_counts_mut(&mut self) -> &mut Vec<I>
[src]
fn column_indices_mut(&mut self) -> &mut Vec<I>
[src]
fn values_mut(&mut self) -> &mut Vec<f64>
[src]
fn solve(
&mut self,
solution: &mut AuctionSolution<I>,
maximize: bool,
eps: Option<f64>
) -> Result<(), Error>
[src]
&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>
[src]
fn extend_from_values(
&mut self,
row: I,
columns: &[I],
values: &[f64]
) -> Result<(), Error>
[src]
&mut self,
row: I,
columns: &[I],
values: &[f64]
) -> Result<(), Error>
fn num_of_arcs(&self) -> usize
[src]
fn get_objective(&self, solution: &AuctionSolution<I>) -> f64
[src]
fn get_objective(&self, solution: &AuctionSolution<I>) -> f64
[src]Returns current objective value of assignments. Checks for the sign of the first element to return positive objective. Read more
fn get_toleration(&self, max_abs_cost: f64) -> f64
[src]
fn ecs_satisfied(
&self,
person_to_object: &[I],
eps: f64,
toleration: f64
) -> bool
[src]
fn ecs_satisfied(
&self,
person_to_object: &[I],
eps: f64,
toleration: f64
) -> bool
[src]Checks if current solution is a complete solution that satisfies eps-complementary slackness. Read more
fn init(&mut self, num_rows: I, num_cols: I) -> Result<(), Error>
[src]
fn init_solve(&mut self, solution: &mut AuctionSolution<I>, maximize: bool)
[src]
fn validate_input(&self) -> Result<(), Error>
[src]
impl<I: Clone + UnsignedInt + Integer> Clone for KhoslaSolver<I>
[src]
impl<I: Clone + UnsignedInt + Integer> Clone for KhoslaSolver<I>
[src]fn clone(&self) -> KhoslaSolver<I>
[src]
fn clone(&self) -> KhoslaSolver<I>
[src]Returns a copy of the value. Read more
fn clone_from(&mut self, source: &Self)
1.0.0[src]
fn clone_from(&mut self, source: &Self)
1.0.0[src]Performs copy-assignment from source
. Read more
Auto Trait Implementations
impl<I> RefUnwindSafe for KhoslaSolver<I> where
I: RefUnwindSafe,
I: RefUnwindSafe,
impl<I> Send for KhoslaSolver<I> where
I: Send,
I: Send,
impl<I> Sync for KhoslaSolver<I> where
I: Sync,
I: Sync,
impl<I> Unpin for KhoslaSolver<I> where
I: Unpin,
I: Unpin,
impl<I> UnwindSafe for KhoslaSolver<I> where
I: UnwindSafe,
I: UnwindSafe,
Blanket Implementations
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]pub fn borrow_mut(&mut self) -> &mut T
[src]
pub fn borrow_mut(&mut self) -> &mut T
[src]Mutably borrows from an owned value. Read more
impl<T> Instrument for T
[src]
impl<T> Instrument for T
[src]fn instrument(self, span: Span) -> Instrumented<Self>
[src]
fn instrument(self, span: Span) -> Instrumented<Self>
[src]Instruments this type with the provided Span
, returning an
Instrumented
wrapper. Read more
fn in_current_span(self) -> Instrumented<Self>
[src]
fn in_current_span(self) -> Instrumented<Self>
[src]impl<T> ToOwned for T where
T: Clone,
[src]
impl<T> ToOwned for T where
T: Clone,
[src]type Owned = T
type Owned = T
The resulting type after obtaining ownership.
pub fn to_owned(&self) -> T
[src]
pub fn to_owned(&self) -> T
[src]Creates owned data from borrowed data, usually by cloning. Read more
pub fn clone_into(&self, target: &mut T)
[src]
pub fn clone_into(&self, target: &mut T)
[src]🔬 This is a nightly-only experimental API. (toowned_clone_into
)
recently added
Uses borrowed data to replace owned data, usually by cloning. Read more