problemreductions/models/set/
comparative_containment.rs

1//! Comparative Containment problem implementation.
2//!
3//! Given two weighted families of sets over a common universe, determine
4//! whether there exists a subset of the universe whose containment weight
5//! in the first family is at least its containment weight in the second.
6
7use crate::registry::{FieldInfo, ProblemSchemaEntry, ProblemSizeFieldEntry, VariantDimension};
8use crate::traits::Problem;
9use crate::types::{One, WeightElement};
10use num_traits::Zero;
11use serde::{Deserialize, Serialize};
12
13inventory::submit! {
14    ProblemSizeFieldEntry {
15        name: "ComparativeContainment",
16        fields: &["universe_size", "num_r_sets", "num_s_sets"],
17    }
18}
19
20inventory::submit! {
21    ProblemSchemaEntry {
22        name: "ComparativeContainment",
23        display_name: "Comparative Containment",
24        aliases: &[],
25        dimensions: &[VariantDimension::new("weight", "i32", &["One", "i32", "f64"])],
26        module_path: module_path!(),
27        description: "Compare containment-weight sums for two set families over a shared universe",
28        fields: &[
29            FieldInfo { name: "universe_size", type_name: "usize", description: "Size of the universe X" },
30            FieldInfo { name: "r_sets", type_name: "Vec<Vec<usize>>", description: "First set family R over X" },
31            FieldInfo { name: "s_sets", type_name: "Vec<Vec<usize>>", description: "Second set family S over X" },
32            FieldInfo { name: "r_weights", type_name: "Vec<W>", description: "Positive weights for sets in R" },
33            FieldInfo { name: "s_weights", type_name: "Vec<W>", description: "Positive weights for sets in S" },
34        ],
35    }
36}
37
38/// Comparative Containment.
39///
40/// Given a universe `X`, two set families `R` and `S`, and positive weights
41/// on those sets, determine whether there exists a subset `Y ⊆ X` such that
42/// the total weight of `R`-sets containing `Y` is at least the total weight
43/// of `S`-sets containing `Y`.
44#[derive(Debug, Clone, Serialize, Deserialize)]
45pub struct ComparativeContainment<W = i32> {
46    universe_size: usize,
47    r_sets: Vec<Vec<usize>>,
48    s_sets: Vec<Vec<usize>>,
49    r_weights: Vec<W>,
50    s_weights: Vec<W>,
51}
52
53impl<W: WeightElement> ComparativeContainment<W> {
54    /// Create a new instance with unit weights.
55    pub fn new(universe_size: usize, r_sets: Vec<Vec<usize>>, s_sets: Vec<Vec<usize>>) -> Self
56    where
57        W: From<i32>,
58    {
59        let r_weights = vec![W::from(1); r_sets.len()];
60        let s_weights = vec![W::from(1); s_sets.len()];
61        Self::with_weights(universe_size, r_sets, s_sets, r_weights, s_weights)
62    }
63
64    /// Create a new instance with explicit weights.
65    pub fn with_weights(
66        universe_size: usize,
67        r_sets: Vec<Vec<usize>>,
68        s_sets: Vec<Vec<usize>>,
69        r_weights: Vec<W>,
70        s_weights: Vec<W>,
71    ) -> Self {
72        assert_eq!(
73            r_sets.len(),
74            r_weights.len(),
75            "number of R sets and R weights must match"
76        );
77        assert_eq!(
78            s_sets.len(),
79            s_weights.len(),
80            "number of S sets and S weights must match"
81        );
82        validate_set_family("R", universe_size, &r_sets);
83        validate_set_family("S", universe_size, &s_sets);
84        validate_weight_family("R", &r_weights);
85        validate_weight_family("S", &s_weights);
86        Self {
87            universe_size,
88            r_sets,
89            s_sets,
90            r_weights,
91            s_weights,
92        }
93    }
94
95    /// Get the size of the universe.
96    pub fn universe_size(&self) -> usize {
97        self.universe_size
98    }
99
100    /// Get the number of sets in the R family.
101    pub fn num_r_sets(&self) -> usize {
102        self.r_sets.len()
103    }
104
105    /// Get the number of sets in the S family.
106    pub fn num_s_sets(&self) -> usize {
107        self.s_sets.len()
108    }
109
110    /// Get the R family.
111    pub fn r_sets(&self) -> &[Vec<usize>] {
112        &self.r_sets
113    }
114
115    /// Get the S family.
116    pub fn s_sets(&self) -> &[Vec<usize>] {
117        &self.s_sets
118    }
119
120    /// Get the R-family weights.
121    pub fn r_weights(&self) -> &[W] {
122        &self.r_weights
123    }
124
125    /// Get the S-family weights.
126    pub fn s_weights(&self) -> &[W] {
127        &self.s_weights
128    }
129
130    /// Check whether the subset selected by `config` is contained in `set`.
131    pub fn contains_selected_subset(&self, config: &[usize], set: &[usize]) -> bool {
132        self.valid_config(config) && contains_selected_subset_unchecked(config, set)
133    }
134
135    fn valid_config(&self, config: &[usize]) -> bool {
136        config.len() == self.universe_size && config.iter().all(|&value| value <= 1)
137    }
138}
139
140impl<W> ComparativeContainment<W>
141where
142    W: WeightElement,
143{
144    /// Total R-family weight for sets containing the selected subset.
145    pub fn r_weight_sum(&self, config: &[usize]) -> Option<W::Sum> {
146        self.sum_containing_weights(config, &self.r_sets, &self.r_weights)
147    }
148
149    /// Total S-family weight for sets containing the selected subset.
150    pub fn s_weight_sum(&self, config: &[usize]) -> Option<W::Sum> {
151        self.sum_containing_weights(config, &self.s_sets, &self.s_weights)
152    }
153
154    /// Check if a configuration is a satisfying solution.
155    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
156        match (self.r_weight_sum(config), self.s_weight_sum(config)) {
157            (Some(r_total), Some(s_total)) => r_total >= s_total,
158            _ => false,
159        }
160    }
161
162    fn sum_containing_weights(
163        &self,
164        config: &[usize],
165        sets: &[Vec<usize>],
166        weights: &[W],
167    ) -> Option<W::Sum> {
168        if !self.valid_config(config) {
169            return None;
170        }
171
172        let mut total = W::Sum::zero();
173        for (set, weight) in sets.iter().zip(weights.iter()) {
174            if contains_selected_subset_unchecked(config, set) {
175                total += weight.to_sum();
176            }
177        }
178        Some(total)
179    }
180}
181
182impl<W> Problem for ComparativeContainment<W>
183where
184    W: WeightElement + crate::variant::VariantParam,
185{
186    const NAME: &'static str = "ComparativeContainment";
187    type Value = crate::types::Or;
188
189    fn dims(&self) -> Vec<usize> {
190        vec![2; self.universe_size]
191    }
192
193    fn evaluate(&self, config: &[usize]) -> crate::types::Or {
194        crate::types::Or(self.is_valid_solution(config))
195    }
196
197    fn variant() -> Vec<(&'static str, &'static str)> {
198        crate::variant_params![W]
199    }
200}
201
202crate::declare_variants! {
203    ComparativeContainment<One> => "2^universe_size",
204    default ComparativeContainment<i32> => "2^universe_size",
205    ComparativeContainment<f64> => "2^universe_size",
206}
207
208fn validate_set_family(label: &str, universe_size: usize, sets: &[Vec<usize>]) {
209    for (set_index, set) in sets.iter().enumerate() {
210        for &element in set {
211            assert!(
212                element < universe_size,
213                "{label} set {set_index} contains element {element} outside universe of size {universe_size}"
214            );
215        }
216    }
217}
218
219fn validate_weight_family<W: WeightElement>(label: &str, weights: &[W]) {
220    for (index, weight) in weights.iter().enumerate() {
221        let sum = weight.to_sum();
222        assert!(
223            sum.partial_cmp(&W::Sum::zero()) == Some(std::cmp::Ordering::Greater),
224            "{label} weights must be finite and positive; weight at index {index} is not"
225        );
226    }
227}
228
229fn contains_selected_subset_unchecked(config: &[usize], set: &[usize]) -> bool {
230    config
231        .iter()
232        .enumerate()
233        .all(|(element, &selected)| selected == 0 || set.contains(&element))
234}
235
236#[cfg(feature = "example-db")]
237pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
238    vec![crate::example_db::specs::ModelExampleSpec {
239        id: "comparative_containment_i32",
240        instance: Box::new(ComparativeContainment::with_weights(
241            4,
242            vec![vec![0, 1, 2, 3], vec![0, 1]],
243            vec![vec![0, 1, 2, 3], vec![2, 3]],
244            vec![2, 5],
245            vec![3, 6],
246        )),
247        optimal_config: vec![0, 1, 0, 0],
248        optimal_value: serde_json::json!(true),
249    }]
250}
251
252#[cfg(test)]
253#[path = "../../unit_tests/models/set/comparative_containment.rs"]
254mod tests;
problemreductions/models/set/comparative_containment.rs

problemreductions/models/set/
comparative_containment.rs
