Struct coupe::CompleteKarmarkarKarp

pub struct CompleteKarmarkarKarp {
    pub tolerance: f64,
}

Complete Karmarkar-Karp algorithm

Extension of the Karmarkar-Karp number partitioning algorithm that explores all possible solutions until the tolerance constraint is respected.

This algorithm is currently implemented in the bi-partitioning case only.

Example

use coupe::Partition as _;

let weights: [i32; 4] = [3, 5, 3, 9];
let mut partition = [0; 4];

coupe::CompleteKarmarkarKarp { tolerance: 0.1 }
    .partition(&mut partition, weights)?;

Reference

Korf, Richard E., 1998. A complete anytime algorithm for number partitioning. Artificial Intelligence, 106(2):181 – 203. doi:10.1016/S0004-3702(98)00086-1.

Fields

tolerance: f64

Constraint on the normalized imbalance between the two parts.

Trait Implementations

impl Clone for CompleteKarmarkarKarp

fn clone(&self) -> CompleteKarmarkarKarp

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for CompleteKarmarkarKarp

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<W> Partition<W> for CompleteKarmarkarKarpwhere W: IntoIterator, W::Item: CkkWeight,

type Metadata = ()

Diagnostic data returned for a specific run of the algorithm.

type Error = Error

Error details, should the algorithm fail to run.

fn partition( &mut self, part_ids: &mut [usize], weights: W ) -> Result<Self::Metadata, Self::Error>

Partition the given data and output the part ID of each element in part_ids.

impl Copy for CompleteKarmarkarKarp