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

problemreductions/models/set/
maximum_set_packing.rs
