Struct SumOfSquaresPartition 

pub struct SumOfSquaresPartition { /* private fields */ }

The Sum of Squares Partition problem (Garey & Johnson SP19).

Given a finite set A with sizes s(a) ∈ Z⁺ for each a ∈ A and a positive integer K ≤ |A| (number of groups), find a partition of A into K disjoint sets A_1, ..., A_K that minimizes:

∑_{i=1}^{K} (∑_{a ∈ A_i} s(a))²

Representation

Each element has a variable in {0, ..., K-1} representing its group assignment. The value is the sum of squared group sums.

Example

use problemreductions::models::misc::SumOfSquaresPartition;
use problemreductions::{Problem, Solver, BruteForce};

// 6 elements with sizes [5, 3, 8, 2, 7, 1], K=3 groups
let problem = SumOfSquaresPartition::new(vec![5, 3, 8, 2, 7, 1], 3);
let solver = BruteForce::new();
let solution = solver.find_witness(&problem);
assert!(solution.is_some());

Implementations

impl SumOfSquaresPartition

pub fn try_new(sizes: Vec<i64>, num_groups: usize) -> Result<Self, String>

Create a new SumOfSquaresPartition instance, returning validation errors.

pub fn new(sizes: Vec<i64>, num_groups: usize) -> Self

Create a new SumOfSquaresPartition instance.

Panics

Panics if any size is not positive (must be > 0), if num_groups is 0, or if num_groups exceeds the number of elements.

pub fn sizes(&self) -> &[i64]

Returns the element sizes.

pub fn num_groups(&self) -> usize

Returns the number of groups K.

pub fn num_elements(&self) -> usize

Returns the number of elements |A|.

pub fn sum_of_squares(&self, config: &[usize]) -> Option<i64>

Compute the sum of squared group sums for a given configuration.

Returns None if the configuration is invalid (wrong length or out-of-range group index), or if arithmetic overflows i64.

Trait Implementations

impl Clone for SumOfSquaresPartition

fn clone(&self) -> SumOfSquaresPartition

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for SumOfSquaresPartition

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

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for SumOfSquaresPartition

fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>

where D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Problem for SumOfSquaresPartition

const NAME: &'static str = "SumOfSquaresPartition"

Base name of this problem type (e.g., “MaximumIndependentSet”).

type Value = Min<i64>

The evaluation value type.

fn variant() -> Vec<(&'static str, &'static str)>

Returns variant attributes derived from type parameters.

fn dims(&self) -> Vec<usize>

Configuration space dimensions. Each entry is the cardinality of that variable.

fn evaluate(&self, config: &[usize]) -> Min<i64>

Evaluate the problem on a configuration.

fn num_variables(&self) -> usize

Number of variables (derived from dims).

fn problem_type() -> ProblemType

Look up this problem’s catalog entry.

impl ReduceTo<ILP> for SumOfSquaresPartition

type Result = ReductionSSPToILP

The reduction result type.

fn reduce_to(&self) -> Self::Result

Reduce this problem to the target problem type.

impl Serialize for SumOfSquaresPartition

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl DeclaredVariant for SumOfSquaresPartition