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::{FieldInfo, 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", "i32", "f64"])],
19        module_path: module_path!(),
20        description: "Find maximum weight collection of disjoint sets",
21        fields: &[
22            FieldInfo { name: "sets", type_name: "Vec<Vec<usize>>", description: "Collection of sets over a universe" },
23            FieldInfo { name: "weights", type_name: "Vec<W>", description: "Weight for each set" },
24        ],
25    }
26}
27
28/// The Set Packing problem.
29///
30/// Given a collection S of sets, each with a weight, find a maximum weight
31/// subcollection of pairwise disjoint sets.
32///
33/// # Example
34///
35/// ```
36/// use problemreductions::models::set::MaximumSetPacking;
37/// use problemreductions::{Problem, Solver, BruteForce};
38///
39/// // Sets: S0={0,1}, S1={1,2}, S2={2,3}, S3={3,4}
40/// // S0 and S1 overlap, S2 and S3 are disjoint from S0
41/// let problem = MaximumSetPacking::<i32>::new(vec![
42///     vec![0, 1],
43///     vec![1, 2],
44///     vec![2, 3],
45///     vec![3, 4],
46/// ]);
47///
48/// let solver = BruteForce::new();
49/// let solutions = solver.find_all_witnesses(&problem);
50///
51/// // Verify solutions are pairwise disjoint
52/// for sol in solutions {
53///     assert!(problem.evaluate(&sol).is_valid());
54/// }
55/// ```
56#[derive(Debug, Clone, Serialize, Deserialize)]
57pub struct MaximumSetPacking<W = i32> {
58    /// Collection of sets.
59    sets: Vec<Vec<usize>>,
60    /// Weights for each set.
61    weights: Vec<W>,
62}
63
64impl<W: Clone + Default> MaximumSetPacking<W> {
65    /// Create a new Set Packing problem with unit weights.
66    pub fn new(sets: Vec<Vec<usize>>) -> Self
67    where
68        W: From<i32>,
69    {
70        let num_sets = sets.len();
71        let weights = vec![W::from(1); num_sets];
72        Self { sets, weights }
73    }
74
75    /// Create a new Set Packing problem with custom weights.
76    pub fn with_weights(sets: Vec<Vec<usize>>, weights: Vec<W>) -> Self {
77        assert_eq!(sets.len(), weights.len());
78        Self { sets, weights }
79    }
80
81    /// Get the number of sets.
82    pub fn num_sets(&self) -> usize {
83        self.sets.len()
84    }
85
86    /// Get the sets.
87    pub fn sets(&self) -> &[Vec<usize>] {
88        &self.sets
89    }
90
91    /// Get a specific set.
92    pub fn get_set(&self, index: usize) -> Option<&Vec<usize>> {
93        self.sets.get(index)
94    }
95
96    /// Check if two sets overlap.
97    pub fn sets_overlap(&self, i: usize, j: usize) -> bool {
98        if let (Some(set_i), Some(set_j)) = (self.sets.get(i), self.sets.get(j)) {
99            let set_i: HashSet<_> = set_i.iter().collect();
100            set_j.iter().any(|e| set_i.contains(e))
101        } else {
102            false
103        }
104    }
105
106    /// Get all pairs of overlapping sets.
107    pub fn overlapping_pairs(&self) -> Vec<(usize, usize)> {
108        let mut pairs = Vec::new();
109        for i in 0..self.sets.len() {
110            for j in (i + 1)..self.sets.len() {
111                if self.sets_overlap(i, j) {
112                    pairs.push((i, j));
113                }
114            }
115        }
116        pairs
117    }
118
119    /// Get the universe size (one more than the maximum element across all sets).
120    pub fn universe_size(&self) -> usize {
121        self.sets()
122            .iter()
123            .flat_map(|s| s.iter())
124            .max()
125            .map_or(0, |&m| m + 1)
126    }
127
128    /// Get a reference to the weights vector.
129    pub fn weights_ref(&self) -> &Vec<W> {
130        &self.weights
131    }
132
133    /// Check if a configuration is a valid set packing.
134    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
135        is_valid_packing(&self.sets, config)
136    }
137}
138
139impl<W> Problem for MaximumSetPacking<W>
140where
141    W: WeightElement + crate::variant::VariantParam,
142{
143    const NAME: &'static str = "MaximumSetPacking";
144    type Value = Max<W::Sum>;
145
146    fn dims(&self) -> Vec<usize> {
147        vec![2; self.sets.len()]
148    }
149
150    fn evaluate(&self, config: &[usize]) -> Max<W::Sum> {
151        if !is_valid_packing(&self.sets, config) {
152            return Max(None);
153        }
154        let mut total = W::Sum::zero();
155        for (i, &selected) in config.iter().enumerate() {
156            if selected == 1 {
157                total += self.weights[i].to_sum();
158            }
159        }
160        Max(Some(total))
161    }
162
163    fn variant() -> Vec<(&'static str, &'static str)> {
164        crate::variant_params![W]
165    }
166}
167
168crate::declare_variants! {
169    default MaximumSetPacking<One> => "2^num_sets",
170    MaximumSetPacking<i32> => "2^num_sets",
171    MaximumSetPacking<f64> => "2^num_sets",
172}
173
174/// Check if a selection forms a valid set packing (pairwise disjoint).
175fn is_valid_packing(sets: &[Vec<usize>], config: &[usize]) -> bool {
176    let selected_sets: Vec<_> = config
177        .iter()
178        .enumerate()
179        .filter(|(_, &s)| s == 1)
180        .map(|(i, _)| i)
181        .collect();
182
183    // Check all pairs of selected sets are disjoint
184    for i in 0..selected_sets.len() {
185        for j in (i + 1)..selected_sets.len() {
186            let set_i: HashSet<_> = sets[selected_sets[i]].iter().collect();
187            if sets[selected_sets[j]].iter().any(|e| set_i.contains(e)) {
188                return false;
189            }
190        }
191    }
192    true
193}
194
195/// Check if a selection of sets forms a valid set packing.
196#[cfg(test)]
197pub(crate) fn is_set_packing(sets: &[Vec<usize>], selected: &[bool]) -> bool {
198    if selected.len() != sets.len() {
199        return false;
200    }
201
202    let config: Vec<usize> = selected.iter().map(|&b| if b { 1 } else { 0 }).collect();
203    is_valid_packing(sets, &config)
204}
205
206#[cfg(feature = "example-db")]
207pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
208    vec![crate::example_db::specs::ModelExampleSpec {
209        id: "maximum_set_packing_i32",
210        instance: Box::new(MaximumSetPacking::<i32>::new(vec![
211            vec![0, 1],
212            vec![1, 2],
213            vec![2, 3],
214            vec![3, 4],
215        ])),
216        optimal_config: vec![0, 1, 0, 1],
217        optimal_value: serde_json::json!(2),
218    }]
219}
220
221#[cfg(test)]
222#[path = "../../unit_tests/models/set/maximum_set_packing.rs"]
223mod tests;
problemreductions/models/set/maximum_set_packing.rs

problemreductions/models/set/
maximum_set_packing.rs
