problemreductions/models/set/
minimum_set_covering.rs

1//! Set Covering problem implementation.
2//!
3//! The Set Covering problem asks for a minimum weight collection of sets
4//! that covers all elements in the universe.
5
6use crate::registry::{CreateSpec, ProblemSchemaEntry, VariantDimension};
7use crate::traits::Problem;
8use crate::types::{Min, WeightElement};
9use num_traits::Zero;
10use serde::{Deserialize, Serialize};
11use std::collections::HashSet;
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "MinimumSetCovering",
16        display_name: "Minimum Set Covering",
17        aliases: &[],
18        dimensions: &[VariantDimension::new("weight", "i64", &["i64"])],
19        category: crate::registry::ProblemCategory::Set,
20        module_path: module_path!(),
21        description: "Find minimum weight collection covering the universe",
22        fields: MinimumSetCoveringCreateSpec::FIELDS,
23    }
24}
25
26/// The Set Covering problem.
27///
28/// Given a universe U of elements and a collection S of subsets of U,
29/// each with a weight, find a minimum weight subcollection of S
30/// that covers all elements in U.
31///
32/// # Example
33///
34/// ```
35/// use problemreductions::models::set::MinimumSetCovering;
36/// use problemreductions::{Problem, BruteForce};
37///
38/// // Universe: {0, 1, 2, 3}
39/// // Sets: S0={0,1}, S1={1,2}, S2={2,3}, S3={0,3}
40/// let problem = MinimumSetCovering::<i64>::new(
41///     4, // universe size
42///     vec![
43///         vec![0, 1],
44///         vec![1, 2],
45///         vec![2, 3],
46///         vec![0, 3],
47///     ],
48/// );
49///
50/// let solver = BruteForce::new();
51/// let solutions = solver.find_all_witnesses(&problem).unwrap();
52///
53/// // Verify solutions cover all elements
54/// for sol in solutions {
55///     assert!(problem.evaluate(&sol).unwrap().is_valid());
56/// }
57/// ```
58#[derive(Debug, Clone, Serialize, Deserialize)]
59#[serde(try_from = "MinimumSetCoveringData<W>")]
60#[serde(bound(deserialize = "W: Clone + Default + Deserialize<'de>"))]
61pub struct MinimumSetCovering<W = i64> {
62    /// Size of the universe (elements are 0..universe_size).
63    universe_size: usize,
64    /// Collection of sets, each represented as a vector of elements.
65    sets: Vec<Vec<usize>>,
66    /// Weights for each set.
67    weights: Vec<W>,
68}
69
70#[derive(Deserialize)]
71struct MinimumSetCoveringData<W> {
72    universe_size: usize,
73    sets: Vec<Vec<usize>>,
74    weights: Vec<W>,
75}
76
77impl<W> TryFrom<MinimumSetCoveringData<W>> for MinimumSetCovering<W>
78where
79    W: Clone + Default,
80{
81    type Error = crate::registry::ConstructionError;
82
83    fn try_from(data: MinimumSetCoveringData<W>) -> Result<Self, Self::Error> {
84        Self::try_with_weights(data.universe_size, data.sets, data.weights)
85    }
86}
87
88#[derive(Debug, Deserialize, crate::CreateSpec)]
89struct MinimumSetCoveringCreateSpec {
90    /// Size of the universe U.
91    universe_size: usize,
92    /// Collection of subsets of U.
93    subsets: Vec<Vec<usize>>,
94    /// Weight for each subset.
95    weights: Vec<i64>,
96}
97
98impl TryFrom<MinimumSetCoveringCreateSpec> for MinimumSetCovering<i64> {
99    type Error = crate::registry::ConstructionError;
100
101    fn try_from(spec: MinimumSetCoveringCreateSpec) -> Result<Self, Self::Error> {
102        Self::try_with_weights(spec.universe_size, spec.subsets, spec.weights)
103    }
104}
105
106impl<W: Clone + Default> MinimumSetCovering<W> {
107    /// Create a new Set Covering problem with unit weights.
108    pub fn new(universe_size: usize, sets: Vec<Vec<usize>>) -> Self
109    where
110        W: WeightElement,
111    {
112        let weights = vec![W::unit(); sets.len()];
113        Self::with_weights(universe_size, sets, weights)
114    }
115
116    /// Create a new Set Covering problem with custom weights.
117    pub fn with_weights(universe_size: usize, sets: Vec<Vec<usize>>, weights: Vec<W>) -> Self {
118        Self::try_with_weights(universe_size, sets, weights)
119            .unwrap_or_else(|error| panic!("{error}"))
120    }
121
122    fn try_with_weights(
123        universe_size: usize,
124        sets: Vec<Vec<usize>>,
125        weights: Vec<W>,
126    ) -> Result<Self, crate::registry::ConstructionError> {
127        if sets.len() != weights.len() {
128            return Err(format!(
129                "weights has {} entries, expected one for each of {} subsets",
130                weights.len(),
131                sets.len()
132            )
133            .into());
134        }
135        for (index, set) in sets.iter().enumerate() {
136            if let Some(element) = set.iter().find(|&&element| element >= universe_size) {
137                return Err(format!("set {index} contains element {element} outside universe of size {universe_size}").into());
138            }
139        }
140        Ok(Self {
141            universe_size,
142            sets,
143            weights,
144        })
145    }
146
147    /// Get the universe size.
148    pub fn universe_size(&self) -> usize {
149        self.universe_size
150    }
151
152    /// Get the number of sets.
153    pub fn num_sets(&self) -> usize {
154        self.sets.len()
155    }
156
157    /// Get the sets.
158    pub fn sets(&self) -> &[Vec<usize>] {
159        &self.sets
160    }
161
162    /// Get a specific set.
163    pub fn get_set(&self, index: usize) -> Option<&Vec<usize>> {
164        self.sets.get(index)
165    }
166
167    /// Get a reference to the weights.
168    pub fn weights_ref(&self) -> &[W] {
169        &self.weights
170    }
171
172    /// Check if a configuration is a valid set cover.
173    pub fn is_valid_solution(&self, config: &[bool]) -> bool {
174        let covered = self.covered_elements(config);
175        covered.len() == self.universe_size && (0..self.universe_size).all(|e| covered.contains(&e))
176    }
177
178    /// Check which elements are covered by selected sets.
179    pub fn covered_elements(&self, config: &[bool]) -> HashSet<usize> {
180        let mut covered = HashSet::new();
181        for (i, &selected) in config.iter().enumerate() {
182            if selected {
183                if let Some(set) = self.sets.get(i) {
184                    covered.extend(set.iter().copied());
185                }
186            }
187        }
188        covered
189    }
190}
191
192impl<W> Problem for MinimumSetCovering<W>
193where
194    W: WeightElement + crate::variant::VariantParam,
195{
196    const NAME: &'static str = "MinimumSetCovering";
197    type Solution = Vec<bool>;
198    type Value = Min<W::Sum>;
199
200    crate::problem_parameters![("num_sets", num_sets), ("universe_size", universe_size),];
201
202    fn evaluate(
203        &self,
204        config: &Self::Solution,
205    ) -> Result<Min<W::Sum>, crate::traits::EvaluationError> {
206        if config.len() != self.sets.len() {
207            return Err(crate::traits::EvaluationError::InvalidConfiguration(
208                "set-selection length does not match the family".into(),
209            ));
210        }
211        Ok({
212            let covered = self.covered_elements(config);
213            let is_valid = covered.len() == self.universe_size
214                && (0..self.universe_size).all(|e| covered.contains(&e));
215            if !is_valid {
216                return Ok(Min(None));
217            }
218            let mut total = W::Sum::zero();
219            for (i, &selected) in config.iter().enumerate() {
220                if selected {
221                    total = W::checked_add_to_sum(
222                        total,
223                        self.weights[i].to_sum(),
224                        "summing selected set-cover weights",
225                    )?;
226                }
227            }
228            Min(Some(total))
229        })
230    }
231
232    fn variant() -> Vec<(&'static str, &'static str)> {
233        crate::variant_params![W]
234    }
235}
236
237impl<W> crate::solvers::BruteForceProblem for MinimumSetCovering<W>
238where
239    W: WeightElement + crate::variant::VariantParam,
240{
241    fn dimensions(&self) -> Vec<usize> {
242        vec![2; self.sets.len()]
243    }
244}
245
246crate::declare_variants! {
247    default MinimumSetCovering<i64> => "2^num_sets" create MinimumSetCoveringCreateSpec,
248}
249
250crate::register_brute_force! {
251    MinimumSetCovering<i64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
252}
253
254/// Check if a selection of sets forms a valid set cover.
255#[cfg(test)]
256pub(crate) fn is_set_cover(universe_size: usize, sets: &[Vec<usize>], selected: &[bool]) -> bool {
257    if selected.len() != sets.len() {
258        return false;
259    }
260
261    let mut covered = HashSet::new();
262    for (i, &sel) in selected.iter().enumerate() {
263        if sel {
264            covered.extend(sets[i].iter().copied());
265        }
266    }
267
268    (0..universe_size).all(|e| covered.contains(&e))
269}
270
271#[cfg(feature = "example-db")]
272pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
273    vec![crate::example_db::specs::ModelExampleSpec {
274        id: "minimum_set_covering",
275        instance: Box::new(MinimumSetCovering::<i64>::new(
276            5,
277            vec![vec![0, 1, 2], vec![1, 3], vec![2, 3, 4]],
278        )),
279        optimal_config: serde_json::json!(vec![true, false, true]),
280        optimal_value: serde_json::json!(2),
281    }]
282}
283
284#[cfg(test)]
285#[path = "../../unit_tests/models/set/minimum_set_covering.rs"]
286mod tests;
problemreductions/models/set/minimum_set_covering.rs

problemreductions/models/set/
minimum_set_covering.rs
