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

problemreductions/models/set/
comparative_containment.rs
