problemreductions/models/set/
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::graph_types::SimpleGraph;
7use crate::traits::{ConstraintSatisfactionProblem, Problem};
8use crate::types::{EnergyMode, LocalConstraint, LocalSolutionSize, ProblemSize, SolutionSize};
9use serde::{Deserialize, Serialize};
10use std::collections::HashSet;
11
12/// The Set Packing problem.
13///
14/// Given a collection S of sets, each with a weight, find a maximum weight
15/// subcollection of pairwise disjoint sets.
16///
17/// # Example
18///
19/// ```
20/// use problemreductions::models::set::SetPacking;
21/// use problemreductions::{Problem, Solver, BruteForce};
22///
23/// // Sets: S0={0,1}, S1={1,2}, S2={2,3}, S3={3,4}
24/// // S0 and S1 overlap, S2 and S3 are disjoint from S0
25/// let problem = SetPacking::<i32>::new(vec![
26///     vec![0, 1],
27///     vec![1, 2],
28///     vec![2, 3],
29///     vec![3, 4],
30/// ]);
31///
32/// let solver = BruteForce::new();
33/// let solutions = solver.find_best(&problem);
34///
35/// // Verify solutions are pairwise disjoint
36/// for sol in solutions {
37///     assert!(problem.solution_size(&sol).is_valid);
38/// }
39/// ```
40#[derive(Debug, Clone, Serialize, Deserialize)]
41pub struct SetPacking<W = i32> {
42    /// Collection of sets.
43    sets: Vec<Vec<usize>>,
44    /// Weights for each set.
45    weights: Vec<W>,
46}
47
48impl<W: Clone + Default> SetPacking<W> {
49    /// Create a new Set Packing problem with unit weights.
50    pub fn new(sets: Vec<Vec<usize>>) -> Self
51    where
52        W: From<i32>,
53    {
54        let num_sets = sets.len();
55        let weights = vec![W::from(1); num_sets];
56        Self { sets, weights }
57    }
58
59    /// Create a new Set Packing problem with custom weights.
60    pub fn with_weights(sets: Vec<Vec<usize>>, weights: Vec<W>) -> Self {
61        assert_eq!(sets.len(), weights.len());
62        Self { sets, weights }
63    }
64
65    /// Get the number of sets.
66    pub fn num_sets(&self) -> usize {
67        self.sets.len()
68    }
69
70    /// Get the sets.
71    pub fn sets(&self) -> &[Vec<usize>] {
72        &self.sets
73    }
74
75    /// Get a specific set.
76    pub fn get_set(&self, index: usize) -> Option<&Vec<usize>> {
77        self.sets.get(index)
78    }
79
80    /// Check if two sets overlap.
81    pub fn sets_overlap(&self, i: usize, j: usize) -> bool {
82        if let (Some(set_i), Some(set_j)) = (self.sets.get(i), self.sets.get(j)) {
83            let set_i: HashSet<_> = set_i.iter().collect();
84            set_j.iter().any(|e| set_i.contains(e))
85        } else {
86            false
87        }
88    }
89
90    /// Get all pairs of overlapping sets.
91    pub fn overlapping_pairs(&self) -> Vec<(usize, usize)> {
92        let mut pairs = Vec::new();
93        for i in 0..self.sets.len() {
94            for j in (i + 1)..self.sets.len() {
95                if self.sets_overlap(i, j) {
96                    pairs.push((i, j));
97                }
98            }
99        }
100        pairs
101    }
102
103    /// Get a reference to the weights vector.
104    pub fn weights_ref(&self) -> &Vec<W> {
105        &self.weights
106    }
107}
108
109impl<W> Problem for SetPacking<W>
110where
111    W: Clone + Default + PartialOrd + num_traits::Num + num_traits::Zero + std::ops::AddAssign + 'static,
112{
113    const NAME: &'static str = "SetPacking";
114    type GraphType = SimpleGraph;
115    type Weight = W;
116    type Size = W;
117
118    fn num_variables(&self) -> usize {
119        self.sets.len()
120    }
121
122    fn num_flavors(&self) -> usize {
123        2
124    }
125
126    fn problem_size(&self) -> ProblemSize {
127        ProblemSize::new(vec![("num_sets", self.sets.len())])
128    }
129
130    fn energy_mode(&self) -> EnergyMode {
131        EnergyMode::LargerSizeIsBetter // Maximize total weight
132    }
133
134    fn solution_size(&self, config: &[usize]) -> SolutionSize<Self::Size> {
135        let is_valid = is_valid_packing(&self.sets, config);
136        let mut total = W::zero();
137        for (i, &selected) in config.iter().enumerate() {
138            if selected == 1 {
139                total += self.weights[i].clone();
140            }
141        }
142        SolutionSize::new(total, is_valid)
143    }
144}
145
146impl<W> ConstraintSatisfactionProblem for SetPacking<W>
147where
148    W: Clone + Default + PartialOrd + num_traits::Num + num_traits::Zero + std::ops::AddAssign + 'static,
149{
150    fn constraints(&self) -> Vec<LocalConstraint> {
151        // For each pair of overlapping sets, at most one can be selected
152        self.overlapping_pairs()
153            .into_iter()
154            .map(|(i, j)| {
155                LocalConstraint::new(
156                    2,
157                    vec![i, j],
158                    vec![true, true, true, false], // (0,0), (0,1), (1,0) OK; (1,1) invalid
159                )
160            })
161            .collect()
162    }
163
164    fn objectives(&self) -> Vec<LocalSolutionSize<Self::Size>> {
165        self.weights
166            .iter()
167            .enumerate()
168            .map(|(i, w)| LocalSolutionSize::new(2, vec![i], vec![W::zero(), w.clone()]))
169            .collect()
170    }
171
172    fn weights(&self) -> Vec<Self::Size> {
173        self.weights.clone()
174    }
175
176    fn set_weights(&mut self, weights: Vec<Self::Size>) {
177        assert_eq!(weights.len(), self.num_variables());
178        self.weights = weights;
179    }
180
181    fn is_weighted(&self) -> bool {
182        if self.weights.is_empty() {
183            return false;
184        }
185        let first = &self.weights[0];
186        !self.weights.iter().all(|w| w == first)
187    }
188}
189
190/// Check if a selection forms a valid set packing (pairwise disjoint).
191fn is_valid_packing(sets: &[Vec<usize>], config: &[usize]) -> bool {
192    let selected_sets: Vec<_> = config
193        .iter()
194        .enumerate()
195        .filter(|(_, &s)| s == 1)
196        .map(|(i, _)| i)
197        .collect();
198
199    // Check all pairs of selected sets are disjoint
200    for i in 0..selected_sets.len() {
201        for j in (i + 1)..selected_sets.len() {
202            let set_i: HashSet<_> = sets[selected_sets[i]].iter().collect();
203            if sets[selected_sets[j]].iter().any(|e| set_i.contains(e)) {
204                return false;
205            }
206        }
207    }
208    true
209}
210
211/// Check if a selection of sets forms a valid set packing.
212pub fn is_set_packing(sets: &[Vec<usize>], selected: &[bool]) -> bool {
213    if selected.len() != sets.len() {
214        return false;
215    }
216
217    let config: Vec<usize> = selected.iter().map(|&b| if b { 1 } else { 0 }).collect();
218    is_valid_packing(sets, &config)
219}
220
221#[cfg(test)]
222mod tests {
223    use super::*;
224    use crate::solvers::{BruteForce, Solver};
225
226    #[test]
227    fn test_set_packing_creation() {
228        let problem = SetPacking::<i32>::new(vec![vec![0, 1], vec![1, 2], vec![3, 4]]);
229        assert_eq!(problem.num_sets(), 3);
230        assert_eq!(problem.num_variables(), 3);
231    }
232
233    #[test]
234    fn test_set_packing_with_weights() {
235        let problem = SetPacking::with_weights(vec![vec![0, 1], vec![2, 3]], vec![5, 10]);
236        assert_eq!(problem.weights(), vec![5, 10]);
237        assert!(problem.is_weighted());
238    }
239
240    #[test]
241    fn test_sets_overlap() {
242        let problem = SetPacking::<i32>::new(vec![vec![0, 1], vec![1, 2], vec![3, 4]]);
243
244        assert!(problem.sets_overlap(0, 1)); // Share element 1
245        assert!(!problem.sets_overlap(0, 2)); // No overlap
246        assert!(!problem.sets_overlap(1, 2)); // No overlap
247    }
248
249    #[test]
250    fn test_overlapping_pairs() {
251        let problem = SetPacking::<i32>::new(vec![vec![0, 1], vec![1, 2], vec![2, 3]]);
252
253        let pairs = problem.overlapping_pairs();
254        assert_eq!(pairs.len(), 2);
255        assert!(pairs.contains(&(0, 1)));
256        assert!(pairs.contains(&(1, 2)));
257    }
258
259    #[test]
260    fn test_solution_size_valid() {
261        let problem = SetPacking::<i32>::new(vec![vec![0, 1], vec![2, 3], vec![4, 5]]);
262
263        // All disjoint, can select all
264        let sol = problem.solution_size(&[1, 1, 1]);
265        assert!(sol.is_valid);
266        assert_eq!(sol.size, 3);
267
268        // Select none
269        let sol = problem.solution_size(&[0, 0, 0]);
270        assert!(sol.is_valid);
271        assert_eq!(sol.size, 0);
272    }
273
274    #[test]
275    fn test_solution_size_invalid() {
276        let problem = SetPacking::<i32>::new(vec![vec![0, 1], vec![1, 2], vec![3, 4]]);
277
278        // Sets 0 and 1 overlap
279        let sol = problem.solution_size(&[1, 1, 0]);
280        assert!(!sol.is_valid);
281    }
282
283    #[test]
284    fn test_brute_force_chain() {
285        // Chain: {0,1}, {1,2}, {2,3} - can select at most 2 non-adjacent sets
286        let problem = SetPacking::<i32>::new(vec![vec![0, 1], vec![1, 2], vec![2, 3]]);
287        let solver = BruteForce::new();
288
289        let solutions = solver.find_best(&problem);
290        // Max is 2: select {0,1} and {2,3}
291        for sol in &solutions {
292            assert_eq!(sol.iter().sum::<usize>(), 2);
293            assert!(problem.solution_size(sol).is_valid);
294        }
295    }
296
297    #[test]
298    fn test_brute_force_weighted() {
299        // Weighted: single heavy set vs multiple light sets
300        let problem = SetPacking::with_weights(
301            vec![vec![0, 1, 2, 3], vec![0, 1], vec![2, 3]],
302            vec![5, 3, 3],
303        );
304        let solver = BruteForce::new();
305
306        let solutions = solver.find_best(&problem);
307        // Should select sets 1 and 2 (total 6) over set 0 (total 5)
308        assert_eq!(solutions.len(), 1);
309        assert_eq!(solutions[0], vec![0, 1, 1]);
310    }
311
312    #[test]
313    fn test_is_set_packing_function() {
314        let sets = vec![vec![0, 1], vec![1, 2], vec![3, 4]];
315
316        assert!(is_set_packing(&sets, &[true, false, true])); // Disjoint
317        assert!(is_set_packing(&sets, &[false, true, true])); // Disjoint
318        assert!(!is_set_packing(&sets, &[true, true, false])); // Overlap on 1
319        assert!(is_set_packing(&sets, &[false, false, false])); // Empty is valid
320    }
321
322    #[test]
323    fn test_constraints() {
324        let problem = SetPacking::<i32>::new(vec![vec![0, 1], vec![1, 2], vec![3, 4]]);
325        let constraints = problem.constraints();
326        // Only one overlapping pair
327        assert_eq!(constraints.len(), 1);
328    }
329
330    #[test]
331    fn test_energy_mode() {
332        let problem = SetPacking::<i32>::new(vec![vec![0, 1]]);
333        assert!(problem.energy_mode().is_maximization());
334    }
335
336    #[test]
337    fn test_disjoint_sets() {
338        let problem = SetPacking::<i32>::new(vec![vec![0], vec![1], vec![2], vec![3]]);
339        let solver = BruteForce::new();
340
341        let solutions = solver.find_best(&problem);
342        // All sets are disjoint, so select all
343        assert_eq!(solutions.len(), 1);
344        assert_eq!(solutions[0], vec![1, 1, 1, 1]);
345    }
346
347    #[test]
348    fn test_all_overlapping() {
349        // All sets share element 0
350        let problem = SetPacking::<i32>::new(vec![vec![0, 1], vec![0, 2], vec![0, 3]]);
351        let solver = BruteForce::new();
352
353        let solutions = solver.find_best(&problem);
354        // Can only select one set
355        for sol in &solutions {
356            assert_eq!(sol.iter().sum::<usize>(), 1);
357        }
358    }
359
360    #[test]
361    fn test_is_satisfied() {
362        let problem = SetPacking::<i32>::new(vec![vec![0, 1], vec![1, 2], vec![3, 4]]);
363
364        assert!(problem.is_satisfied(&[1, 0, 1])); // Disjoint selection
365        assert!(problem.is_satisfied(&[0, 1, 1])); // Disjoint selection
366        assert!(!problem.is_satisfied(&[1, 1, 0])); // Overlapping selection
367    }
368
369    #[test]
370    fn test_empty_sets() {
371        let problem = SetPacking::<i32>::new(vec![]);
372        let sol = problem.solution_size(&[]);
373        assert!(sol.is_valid);
374        assert_eq!(sol.size, 0);
375    }
376
377    #[test]
378    fn test_get_set() {
379        let problem = SetPacking::<i32>::new(vec![vec![0, 1], vec![2, 3]]);
380        assert_eq!(problem.get_set(0), Some(&vec![0, 1]));
381        assert_eq!(problem.get_set(1), Some(&vec![2, 3]));
382        assert_eq!(problem.get_set(2), None);
383    }
384
385    #[test]
386    fn test_relationship_to_independent_set() {
387        // SetPacking on sets is equivalent to IndependentSet on the intersection graph
388        use crate::models::graph::IndependentSet;
389
390        let sets = vec![vec![0, 1], vec![1, 2], vec![2, 3], vec![3, 4]];
391        let sp_problem = SetPacking::<i32>::new(sets.clone());
392
393        // Build intersection graph
394        let edges = sp_problem.overlapping_pairs();
395        let is_problem = IndependentSet::<i32>::new(sets.len(), edges);
396
397        let solver = BruteForce::new();
398
399        let sp_solutions = solver.find_best(&sp_problem);
400        let is_solutions = solver.find_best(&is_problem);
401
402        // Should have same optimal value
403        let sp_size: usize = sp_solutions[0].iter().sum();
404        let is_size: usize = is_solutions[0].iter().sum();
405        assert_eq!(sp_size, is_size);
406    }
407
408    #[test]
409    fn test_objectives() {
410        let problem = SetPacking::with_weights(vec![vec![0, 1], vec![1, 2]], vec![5, 10]);
411        let objectives = problem.objectives();
412        assert_eq!(objectives.len(), 2);
413    }
414
415    #[test]
416    fn test_set_weights() {
417        let mut problem = SetPacking::<i32>::new(vec![vec![0, 1], vec![1, 2]]);
418        assert!(!problem.is_weighted()); // Initially uniform
419        problem.set_weights(vec![1, 2]);
420        assert!(problem.is_weighted());
421        assert_eq!(problem.weights(), vec![1, 2]);
422    }
423
424    #[test]
425    fn test_is_weighted_empty() {
426        let problem = SetPacking::<i32>::new(vec![]);
427        assert!(!problem.is_weighted());
428    }
429
430    #[test]
431    fn test_is_set_packing_wrong_len() {
432        let sets = vec![vec![0, 1], vec![1, 2]];
433        assert!(!is_set_packing(&sets, &[true])); // Wrong length
434    }
435
436    #[test]
437    fn test_problem_size() {
438        let problem = SetPacking::<i32>::new(vec![vec![0, 1], vec![1, 2], vec![3, 4]]);
439        let size = problem.problem_size();
440        assert_eq!(size.get("num_sets"), Some(3));
441    }
442}
problemreductions/models/set/set_packing.rs

problemreductions/models/set/
set_packing.rs
