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(crate::registry::ConstructionError::length_mismatch(
115                "weights",
116                weights.len(),
117                sets.len(),
118            ));
119        }
120        for (index, weight) in weights.iter().enumerate() {
121            weight.validate_element(&format!("set weight at index {index}"))?;
122        }
123        Ok(Self { sets, weights })
124    }
125
126    /// Get the number of sets.
127    pub fn num_sets(&self) -> usize {
128        self.sets.len()
129    }
130
131    /// Get the sets.
132    pub fn sets(&self) -> &[Vec<usize>] {
133        &self.sets
134    }
135
136    /// Get a specific set.
137    pub fn get_set(&self, index: usize) -> Option<&Vec<usize>> {
138        self.sets.get(index)
139    }
140
141    /// Check if two sets overlap.
142    pub fn sets_overlap(&self, i: usize, j: usize) -> bool {
143        if let (Some(set_i), Some(set_j)) = (self.sets.get(i), self.sets.get(j)) {
144            let set_i: HashSet<_> = set_i.iter().collect();
145            set_j.iter().any(|e| set_i.contains(e))
146        } else {
147            false
148        }
149    }
150
151    /// Get all pairs of overlapping sets.
152    pub fn overlapping_pairs(&self) -> Vec<(usize, usize)> {
153        let mut pairs = Vec::new();
154        for i in 0..self.sets.len() {
155            for j in (i + 1)..self.sets.len() {
156                if self.sets_overlap(i, j) {
157                    pairs.push((i, j));
158                }
159            }
160        }
161        pairs
162    }
163
164    /// Get the universe size (one more than the maximum element across all sets).
165    pub fn universe_size(&self) -> usize {
166        self.sets()
167            .iter()
168            .flat_map(|s| s.iter())
169            .max()
170            .map_or(0, |&m| m + 1)
171    }
172
173    /// Get a reference to the weights vector.
174    pub fn weights_ref(&self) -> &Vec<W> {
175        &self.weights
176    }
177
178    /// Check if a configuration is a valid set packing.
179    pub fn is_valid_solution(&self, config: &[bool]) -> bool {
180        is_valid_packing(&self.sets, config)
181    }
182}
183
184impl<W> Problem for MaximumSetPacking<W>
185where
186    W: WeightElement + crate::variant::VariantParam,
187{
188    const NAME: &'static str = "MaximumSetPacking";
189    type Solution = Vec<bool>;
190    type Value = Max<W::Sum>;
191
192    crate::problem_parameters![("num_sets", num_sets), ("universe_size", universe_size),];
193
194    fn evaluate(
195        &self,
196        config: &Self::Solution,
197    ) -> Result<Max<W::Sum>, crate::traits::EvaluationError> {
198        if config.len() != self.sets.len() {
199            return Err(crate::traits::EvaluationError::InvalidConfiguration(
200                "set-selection length does not match the family".into(),
201            ));
202        }
203        Ok({
204            if !is_valid_packing(&self.sets, config) {
205                return Ok(Max(None));
206            }
207            let mut total = W::Sum::zero();
208            for (i, &selected) in config.iter().enumerate() {
209                if selected {
210                    total = W::checked_add_to_sum(
211                        total,
212                        self.weights[i].to_sum(),
213                        "summing selected set-packing weights",
214                    )?;
215                }
216            }
217            Max(Some(total))
218        })
219    }
220
221    fn variant() -> Vec<(&'static str, &'static str)> {
222        crate::variant_params![W]
223    }
224}
225
226impl<W> crate::solvers::BruteForceProblem for MaximumSetPacking<W>
227where
228    W: WeightElement + crate::variant::VariantParam,
229{
230    fn dimensions(&self) -> Vec<usize> {
231        vec![2; self.sets.len()]
232    }
233}
234
235#[derive(Debug, Deserialize, crate::CreateSpec)]
236struct MaximumSetPackingOneCreateSpec {
237    /// Collection of sets over a universe.
238    subsets: Vec<Vec<usize>>,
239}
240impl TryFrom<MaximumSetPackingOneCreateSpec> for MaximumSetPacking<One> {
241    type Error = ConstructionError;
242    fn try_from(spec: MaximumSetPackingOneCreateSpec) -> Result<Self, Self::Error> {
243        let weights = vec![One; spec.subsets.len()];
244        Self::with_weights(spec.subsets, weights)
245    }
246}
247
248crate::declare_variants! {
249    default MaximumSetPacking<One> => "2^num_sets" create MaximumSetPackingOneCreateSpec,
250    MaximumSetPacking<i64> => "2^num_sets" create MaximumSetPackingCreateSpec<i64>,
251    MaximumSetPacking<f64> => "2^num_sets" create MaximumSetPackingCreateSpec<f64>,
252}
253
254crate::register_brute_force! {
255    MaximumSetPacking<One> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
256    MaximumSetPacking<i64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
257    MaximumSetPacking<f64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
258}
259
260/// Check if a selection forms a valid set packing (pairwise disjoint).
261fn is_valid_packing(sets: &[Vec<usize>], config: &[bool]) -> bool {
262    let selected_sets: Vec<_> = config
263        .iter()
264        .enumerate()
265        .filter(|(_, &selected)| selected)
266        .map(|(i, _)| i)
267        .collect();
268
269    // Check all pairs of selected sets are disjoint
270    for i in 0..selected_sets.len() {
271        for j in (i + 1)..selected_sets.len() {
272            let set_i: HashSet<_> = sets[selected_sets[i]].iter().collect();
273            if sets[selected_sets[j]].iter().any(|e| set_i.contains(e)) {
274                return false;
275            }
276        }
277    }
278    true
279}
280
281/// Check if a selection of sets forms a valid set packing.
282#[cfg(test)]
283pub(crate) fn is_set_packing(sets: &[Vec<usize>], selected: &[bool]) -> bool {
284    if selected.len() != sets.len() {
285        return false;
286    }
287
288    is_valid_packing(sets, selected)
289}
290
291#[cfg(feature = "example-db")]
292pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
293    vec![crate::example_db::specs::ModelExampleSpec {
294        id: "maximum_set_packing",
295        instance: Box::new(MaximumSetPacking::<i64>::new(vec![
296            vec![0, 1],
297            vec![1, 2],
298            vec![2, 3],
299            vec![3, 4],
300        ])),
301        optimal_config: serde_json::json!(vec![false, true, false, true]),
302        optimal_value: serde_json::json!(2),
303    }]
304}
305
306#[cfg(test)]
307#[path = "../../unit_tests/models/set/maximum_set_packing.rs"]
308mod tests;
problemreductions/models/set/maximum_set_packing.rs

problemreductions/models/set/
maximum_set_packing.rs
