problemreductions/models/misc/
sum_of_squares_partition.rs

1//! Sum of Squares Partition problem implementation.
2//!
3//! Given a finite set of positive integers and K groups, find a partition
4//! into K groups that minimizes the sum of squared group sums.
5//! NP-hard in the strong sense (Garey & Johnson, SP19).
6
7use crate::registry::{FieldInfo, ProblemSchemaEntry};
8use crate::traits::Problem;
9use crate::types::Min;
10use serde::de::Error;
11use serde::{Deserialize, Deserializer, Serialize};
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "SumOfSquaresPartition",
16        display_name: "Sum of Squares Partition",
17        aliases: &[],
18        dimensions: &[],
19        category: crate::registry::ProblemCategory::Misc,
20        module_path: module_path!(),
21        description: "Partition positive integers into K groups minimizing the sum of squared group sums",
22        fields: &[
23            FieldInfo { name: "sizes", type_name: "Vec<i64>", description: "Positive integer size s(a) for each element a in A" },
24            FieldInfo { name: "num_groups", type_name: "usize", description: "Number of groups K in the partition" },
25        ],
26    }
27}
28
29/// The Sum of Squares Partition problem (Garey & Johnson SP19).
30///
31/// Given a finite set `A` with sizes `s(a) ∈ Z⁺` for each `a ∈ A`
32/// and a positive integer `K ≤ |A|` (number of groups), find a
33/// partition of `A` into `K` disjoint sets `A_1, ..., A_K` that
34/// minimizes:
35///
36/// `∑_{i=1}^{K} (∑_{a ∈ A_i} s(a))²`
37///
38/// # Representation
39///
40/// Each element has a variable in `{0, ..., K-1}` representing its
41/// group assignment. The value is the sum of squared group sums.
42///
43/// # Example
44///
45/// ```
46/// use problemreductions::models::misc::SumOfSquaresPartition;
47/// use problemreductions::{Problem, BruteForce};
48///
49/// // 6 elements with sizes [5, 3, 8, 2, 7, 1], K=3 groups
50/// let problem = SumOfSquaresPartition::new(vec![5, 3, 8, 2, 7, 1], 3);
51/// let solver = BruteForce::new();
52/// let solution = solver.solve(&problem).unwrap();
53/// assert!(solution.is_some());
54/// ```
55#[derive(Debug, Clone, Serialize)]
56pub struct SumOfSquaresPartition {
57    /// Positive integer sizes for each element.
58    sizes: Vec<i64>,
59    /// Number of groups K.
60    num_groups: usize,
61}
62
63impl SumOfSquaresPartition {
64    fn validate_inputs(
65        sizes: &[i64],
66        num_groups: usize,
67    ) -> Result<(), crate::registry::ConstructionError> {
68        if sizes.iter().any(|&size| size <= 0) {
69            return Err("All sizes must be positive (> 0)".to_string().into());
70        }
71        if num_groups == 0 {
72            return Err("Number of groups must be positive".to_string().into());
73        }
74        if num_groups > sizes.len() {
75            return Err("Number of groups must not exceed number of elements"
76                .to_string()
77                .into());
78        }
79        Ok(())
80    }
81
82    /// Create a new SumOfSquaresPartition instance, returning validation errors.
83    pub fn try_new(
84        sizes: Vec<i64>,
85        num_groups: usize,
86    ) -> Result<Self, crate::registry::ConstructionError> {
87        Self::validate_inputs(&sizes, num_groups)?;
88        Ok(Self { sizes, num_groups })
89    }
90
91    /// Create a new SumOfSquaresPartition instance.
92    ///
93    /// # Panics
94    ///
95    /// Panics if any size is not positive (must be > 0), if `num_groups` is 0,
96    /// or if `num_groups` exceeds the number of elements.
97    pub fn new(sizes: Vec<i64>, num_groups: usize) -> Self {
98        Self::try_new(sizes, num_groups).unwrap_or_else(|message| panic!("{message}"))
99    }
100
101    /// Returns the element sizes.
102    pub fn sizes(&self) -> &[i64] {
103        &self.sizes
104    }
105
106    /// Returns the number of groups K.
107    pub fn num_groups(&self) -> usize {
108        self.num_groups
109    }
110
111    /// Returns the number of elements |A|.
112    pub fn num_elements(&self) -> usize {
113        self.sizes.len()
114    }
115
116    /// Compute the sum of squared group sums for a given configuration.
117    ///
118    /// Returns `None` if the configuration is invalid (wrong length or
119    /// out-of-range group index), or if arithmetic overflows `i64`.
120    pub fn sum_of_squares(
121        &self,
122        config: &[usize],
123    ) -> Result<Option<i64>, crate::traits::EvaluationError> {
124        if config.len() != self.sizes.len() {
125            return Ok(None);
126        }
127        let mut group_sums = vec![0_i64; self.num_groups];
128        for (i, &g) in config.iter().enumerate() {
129            if g >= self.num_groups {
130                return Ok(None);
131            }
132            group_sums[g] = group_sums[g].checked_add(self.sizes[i]).ok_or_else(|| {
133                crate::traits::EvaluationError::IntegerOverflow(
134                    "summing a sum-of-squares partition group".into(),
135                )
136            })?;
137        }
138        let total = group_sums.into_iter().try_fold(0_i64, |total, group_sum| {
139            let square = group_sum.checked_mul(group_sum).ok_or_else(|| {
140                crate::traits::EvaluationError::IntegerOverflow(
141                    "squaring a partition group sum".into(),
142                )
143            })?;
144            total.checked_add(square).ok_or_else(|| {
145                crate::traits::EvaluationError::IntegerOverflow(
146                    "summing squared partition group sums".into(),
147                )
148            })
149        })?;
150        Ok(Some(total))
151    }
152}
153
154#[derive(Deserialize)]
155struct SumOfSquaresPartitionData {
156    sizes: Vec<i64>,
157    num_groups: usize,
158}
159
160impl<'de> Deserialize<'de> for SumOfSquaresPartition {
161    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
162    where
163        D: Deserializer<'de>,
164    {
165        let data = SumOfSquaresPartitionData::deserialize(deserializer)?;
166        Self::try_new(data.sizes, data.num_groups).map_err(D::Error::custom)
167    }
168}
169
170impl Problem for SumOfSquaresPartition {
171    const NAME: &'static str = "SumOfSquaresPartition";
172    type Solution = Vec<usize>;
173    type Value = Min<i64>;
174
175    crate::problem_parameters![("num_elements", num_elements), ("num_groups", num_groups),];
176
177    fn variant() -> Vec<(&'static str, &'static str)> {
178        crate::variant_params![]
179    }
180
181    fn evaluate(
182        &self,
183        config: &Self::Solution,
184    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
185        if config.len() != self.sizes.len() {
186            return Err(crate::traits::EvaluationError::InvalidConfiguration(
187                "group assignment length does not match the elements".into(),
188            ));
189        }
190        if config.iter().any(|&group| group >= self.num_groups) {
191            return Err(crate::traits::EvaluationError::InvalidConfiguration(
192                "group assignment contains an out-of-range group".into(),
193            ));
194        }
195        Ok(Min(self.sum_of_squares(config)?))
196    }
197}
198
199impl crate::solvers::BruteForceProblem for SumOfSquaresPartition {
200    fn dimensions(&self) -> Vec<usize> {
201        vec![self.num_groups; self.sizes.len()]
202    }
203}
204
205crate::declare_variants! {
206    default SumOfSquaresPartition => "num_groups^num_elements",
207}
208
209crate::register_brute_force! {
210    SumOfSquaresPartition,
211}
212
213#[cfg(feature = "example-db")]
214pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
215    vec![crate::example_db::specs::ModelExampleSpec {
216        id: "sum_of_squares_partition",
217        // sizes=[5,3,8,2,7,1], K=3
218        // Optimal: groups {8},{2,7},{5,3,1} -> sums 8,9,9 -> 64+81+81=226
219        instance: Box::new(SumOfSquaresPartition::new(vec![5, 3, 8, 2, 7, 1], 3)),
220        optimal_config: serde_json::json!(vec![2, 2, 0, 1, 1, 0]),
221        optimal_value: serde_json::json!(226),
222    }]
223}
224
225#[cfg(test)]
226#[path = "../../unit_tests/models/misc/sum_of_squares_partition.rs"]
227mod tests;
problemreductions/models/misc/sum_of_squares_partition.rs

problemreductions/models/misc/
sum_of_squares_partition.rs
