problemreductions/models/set/
maximum_set_packing.rs

1//! Set Packing problem implementation.
2//!
3//! The Set Packing problem asks for a maximum weight collection of
4//! pairwise disjoint sets.
5
6use crate::registry::{ConstructionError, CreateSpec, ProblemSchemaEntry, VariantDimension};
7use crate::traits::Problem;
8use crate::types::{Max, One, WeightElement};
9use num_traits::Zero;
10use serde::{Deserialize, Serialize};
11use std::collections::HashSet;
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "MaximumSetPacking",
16        display_name: "Maximum Set Packing",
17        aliases: &[],
18        dimensions: &[VariantDimension::new("weight", "One", &["One", "i64", "f64"])],
19        category: crate::registry::ProblemCategory::Set,
20        module_path: module_path!(),
21        description: "Find maximum weight collection of disjoint sets",
22        fields: MaximumSetPackingCreateSpec::<One>::FIELDS,
23    }
24}
25
26/// The Set Packing problem.
27///
28/// Given a collection S of sets, each with a weight, find a maximum weight
29/// subcollection of pairwise disjoint sets.
30///
31/// # Example
32///
33/// ```
34/// use problemreductions::models::set::MaximumSetPacking;
35/// use problemreductions::{Problem, BruteForce};
36///
37/// // Sets: S0={0,1}, S1={1,2}, S2={2,3}, S3={3,4}
38/// // S0 and S1 overlap, S2 and S3 are disjoint from S0
39/// let problem = MaximumSetPacking::<i64>::new(vec![
40///     vec![0, 1],
41///     vec![1, 2],
42///     vec![2, 3],
43///     vec![3, 4],
44/// ]);
45///
46/// let solver = BruteForce::new();
47/// let solutions = solver.find_all_witnesses(&problem).unwrap();
48///
49/// // Verify solutions are pairwise disjoint
50/// for sol in solutions {
51///     assert!(problem.evaluate(&sol).unwrap().is_valid());
52/// }
53/// ```
54#[derive(Debug, Clone, Serialize)]
55pub struct MaximumSetPacking<W = i64> {
56    /// Collection of sets.
57    sets: Vec<Vec<usize>>,
58    /// Weights for each set.
59    weights: Vec<W>,
60}
61
62#[derive(Deserialize)]
63struct MaximumSetPackingData<W> {
64    sets: Vec<Vec<usize>>,
65    weights: Vec<W>,
66}
67
68impl<'de, W> Deserialize<'de> for MaximumSetPacking<W>
69where
70    W: WeightElement + Deserialize<'de>,
71{
72    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
73    where
74        D: serde::Deserializer<'de>,
75    {
76        let data = MaximumSetPackingData::deserialize(deserializer)?;
77        Self::with_weights(data.sets, data.weights).map_err(serde::de::Error::custom)
78    }
79}
80
81#[derive(Debug, Deserialize, crate::CreateSpec)]
82struct MaximumSetPackingCreateSpec<W> {
83    /// Collection of sets over a universe.
84    subsets: Vec<Vec<usize>>,
85    /// Weight for each set.
86    weights: Vec<W>,
87}
88
89impl<W: WeightElement> TryFrom<MaximumSetPackingCreateSpec<W>> for MaximumSetPacking<W> {
90    type Error = ConstructionError;
91
92    fn try_from(spec: MaximumSetPackingCreateSpec<W>) -> Result<Self, Self::Error> {
93        Self::with_weights(spec.subsets, spec.weights)
94    }
95}
96
97impl<W: Clone + Default> MaximumSetPacking<W> {
98    /// Create a new Set Packing problem with unit weights.
99    pub fn new(sets: Vec<Vec<usize>>) -> Self
100    where
101        W: WeightElement,
102    {
103        let num_sets = sets.len();
104        let weights = vec![W::unit(); num_sets];
105        Self { sets, weights }
106    }
107
108    /// Create a new Set Packing problem with custom weights.
109    pub fn with_weights(sets: Vec<Vec<usize>>, weights: Vec<W>) -> Result<Self, ConstructionError>
110    where
111        W: WeightElement,
112    {
113        if sets.len() != weights.len() {
114            return Err(ConstructionError::Conversion(
115                "weights length must match number of sets".into(),
116            ));
117        }
118        for (index, weight) in weights.iter().enumerate() {
119            weight.validate_element(&format!("set weight at index {index}"))?;
120        }
121        Ok(Self { sets, weights })
122    }
123
124    /// Get the number of sets.
125    pub fn num_sets(&self) -> usize {
126        self.sets.len()
127    }
128
129    /// Get the sets.
130    pub fn sets(&self) -> &[Vec<usize>] {
131        &self.sets
132    }
133
134    /// Get a specific set.
135    pub fn get_set(&self, index: usize) -> Option<&Vec<usize>> {
136        self.sets.get(index)
137    }
138
139    /// Check if two sets overlap.
140    pub fn sets_overlap(&self, i: usize, j: usize) -> bool {
141        if let (Some(set_i), Some(set_j)) = (self.sets.get(i), self.sets.get(j)) {
142            let set_i: HashSet<_> = set_i.iter().collect();
143            set_j.iter().any(|e| set_i.contains(e))
144        } else {
145            false
146        }
147    }
148
149    /// Get all pairs of overlapping sets.
150    pub fn overlapping_pairs(&self) -> Vec<(usize, usize)> {
151        let mut pairs = Vec::new();
152        for i in 0..self.sets.len() {
153            for j in (i + 1)..self.sets.len() {
154                if self.sets_overlap(i, j) {
155                    pairs.push((i, j));
156                }
157            }
158        }
159        pairs
160    }
161
162    /// Get the universe size (one more than the maximum element across all sets).
163    pub fn universe_size(&self) -> usize {
164        self.sets()
165            .iter()
166            .flat_map(|s| s.iter())
167            .max()
168            .map_or(0, |&m| m + 1)
169    }
170
171    /// Get a reference to the weights vector.
172    pub fn weights_ref(&self) -> &Vec<W> {
173        &self.weights
174    }
175
176    /// Check if a configuration is a valid set packing.
177    pub fn is_valid_solution(&self, config: &[bool]) -> bool {
178        is_valid_packing(&self.sets, config)
179    }
180}
181
182impl<W> Problem for MaximumSetPacking<W>
183where
184    W: WeightElement + crate::variant::VariantParam,
185{
186    const NAME: &'static str = "MaximumSetPacking";
187    type Solution = Vec<bool>;
188    type Value = Max<W::Sum>;
189
190    crate::problem_parameters![("num_sets", num_sets), ("universe_size", universe_size),];
191
192    fn evaluate(
193        &self,
194        config: &Self::Solution,
195    ) -> Result<Max<W::Sum>, crate::traits::EvaluationError> {
196        if config.len() != self.sets.len() {
197            return Err(crate::traits::EvaluationError::InvalidConfiguration(
198                "set-selection length does not match the family".into(),
199            ));
200        }
201        Ok({
202            if !is_valid_packing(&self.sets, config) {
203                return Ok(Max(None));
204            }
205            let mut total = W::Sum::zero();
206            for (i, &selected) in config.iter().enumerate() {
207                if selected {
208                    total = W::checked_add_to_sum(
209                        total,
210                        self.weights[i].to_sum(),
211                        "summing selected set-packing weights",
212                    )?;
213                }
214            }
215            Max(Some(total))
216        })
217    }
218
219    fn variant() -> Vec<(&'static str, &'static str)> {
220        crate::variant_params![W]
221    }
222}
223
224impl<W> crate::solvers::BruteForceProblem for MaximumSetPacking<W>
225where
226    W: WeightElement + crate::variant::VariantParam,
227{
228    fn dimensions(&self) -> Vec<usize> {
229        vec![2; self.sets.len()]
230    }
231}
232
233#[derive(Debug, Deserialize, crate::CreateSpec)]
234struct MaximumSetPackingOneCreateSpec {
235    /// Collection of sets over a universe.
236    subsets: Vec<Vec<usize>>,
237}
238impl TryFrom<MaximumSetPackingOneCreateSpec> for MaximumSetPacking<One> {
239    type Error = ConstructionError;
240    fn try_from(spec: MaximumSetPackingOneCreateSpec) -> Result<Self, Self::Error> {
241        let weights = vec![One; spec.subsets.len()];
242        Self::with_weights(spec.subsets, weights)
243    }
244}
245
246crate::declare_variants! {
247    default MaximumSetPacking<One> => "2^num_sets" create MaximumSetPackingOneCreateSpec,
248    MaximumSetPacking<i64> => "2^num_sets" create MaximumSetPackingCreateSpec<i64>,
249    MaximumSetPacking<f64> => "2^num_sets" create MaximumSetPackingCreateSpec<f64>,
250}
251
252crate::register_brute_force! {
253    MaximumSetPacking<One> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
254    MaximumSetPacking<i64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
255    MaximumSetPacking<f64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
256}
257
258/// Check if a selection forms a valid set packing (pairwise disjoint).
259fn is_valid_packing(sets: &[Vec<usize>], config: &[bool]) -> bool {
260    let selected_sets: Vec<_> = config
261        .iter()
262        .enumerate()
263        .filter(|(_, &selected)| selected)
264        .map(|(i, _)| i)
265        .collect();
266
267    // Check all pairs of selected sets are disjoint
268    for i in 0..selected_sets.len() {
269        for j in (i + 1)..selected_sets.len() {
270            let set_i: HashSet<_> = sets[selected_sets[i]].iter().collect();
271            if sets[selected_sets[j]].iter().any(|e| set_i.contains(e)) {
272                return false;
273            }
274        }
275    }
276    true
277}
278
279/// Check if a selection of sets forms a valid set packing.
280#[cfg(test)]
281pub(crate) fn is_set_packing(sets: &[Vec<usize>], selected: &[bool]) -> bool {
282    if selected.len() != sets.len() {
283        return false;
284    }
285
286    is_valid_packing(sets, selected)
287}
288
289#[cfg(feature = "example-db")]
290pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
291    vec![crate::example_db::specs::ModelExampleSpec {
292        id: "maximum_set_packing",
293        instance: Box::new(MaximumSetPacking::<i64>::new(vec![
294            vec![0, 1],
295            vec![1, 2],
296            vec![2, 3],
297            vec![3, 4],
298        ])),
299        optimal_config: serde_json::json!(vec![false, true, false, true]),
300        optimal_value: serde_json::json!(2),
301    }]
302}
303
304#[cfg(test)]
305#[path = "../../unit_tests/models/set/maximum_set_packing.rs"]
306mod tests;
problemreductions/models/set/maximum_set_packing.rs

problemreductions/models/set/
maximum_set_packing.rs
