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)]
59pub struct MinimumSetCovering<W = i64> {
60    /// Size of the universe (elements are 0..universe_size).
61    universe_size: usize,
62    /// Collection of sets, each represented as a vector of elements.
63    sets: Vec<Vec<usize>>,
64    /// Weights for each set.
65    weights: Vec<W>,
66}
67
68#[derive(Debug, Deserialize, crate::CreateSpec)]
69struct MinimumSetCoveringCreateSpec {
70    /// Size of the universe U.
71    universe_size: usize,
72    /// Collection of subsets of U.
73    subsets: Vec<Vec<usize>>,
74    /// Weight for each subset.
75    weights: Vec<i64>,
76}
77
78impl TryFrom<MinimumSetCoveringCreateSpec> for MinimumSetCovering<i64> {
79    type Error = crate::registry::ConstructionError;
80
81    fn try_from(spec: MinimumSetCoveringCreateSpec) -> Result<Self, Self::Error> {
82        if spec.subsets.len() != spec.weights.len() {
83            return Err(format!(
84                "weights has {} entries, expected one for each of {} subsets",
85                spec.weights.len(),
86                spec.subsets.len()
87            )
88            .into());
89        }
90        for (set_index, set) in spec.subsets.iter().enumerate() {
91            if let Some(&element) = set.iter().find(|&&element| element >= spec.universe_size) {
92                return Err(format!(
93                    "subsets[{set_index}] contains element {element} outside universe of size {}",
94                    spec.universe_size
95                )
96                .into());
97            }
98        }
99        Ok(Self::with_weights(
100            spec.universe_size,
101            spec.subsets,
102            spec.weights,
103        ))
104    }
105}
106
107impl<W: Clone + Default> MinimumSetCovering<W> {
108    /// Create a new Set Covering problem with unit weights.
109    pub fn new(universe_size: usize, sets: Vec<Vec<usize>>) -> Self
110    where
111        W: WeightElement,
112    {
113        let num_sets = sets.len();
114        let weights = vec![W::unit(); num_sets];
115        Self {
116            universe_size,
117            sets,
118            weights,
119        }
120    }
121
122    /// Create a new Set Covering problem with custom weights.
123    pub fn with_weights(universe_size: usize, sets: Vec<Vec<usize>>, weights: Vec<W>) -> Self {
124        assert_eq!(sets.len(), weights.len());
125        Self {
126            universe_size,
127            sets,
128            weights,
129        }
130    }
131
132    /// Get the universe size.
133    pub fn universe_size(&self) -> usize {
134        self.universe_size
135    }
136
137    /// Get the number of sets.
138    pub fn num_sets(&self) -> usize {
139        self.sets.len()
140    }
141
142    /// Get the sets.
143    pub fn sets(&self) -> &[Vec<usize>] {
144        &self.sets
145    }
146
147    /// Get a specific set.
148    pub fn get_set(&self, index: usize) -> Option<&Vec<usize>> {
149        self.sets.get(index)
150    }
151
152    /// Get a reference to the weights.
153    pub fn weights_ref(&self) -> &[W] {
154        &self.weights
155    }
156
157    /// Check if a configuration is a valid set cover.
158    pub fn is_valid_solution(&self, config: &[bool]) -> bool {
159        let covered = self.covered_elements(config);
160        covered.len() == self.universe_size && (0..self.universe_size).all(|e| covered.contains(&e))
161    }
162
163    /// Check which elements are covered by selected sets.
164    pub fn covered_elements(&self, config: &[bool]) -> HashSet<usize> {
165        let mut covered = HashSet::new();
166        for (i, &selected) in config.iter().enumerate() {
167            if selected {
168                if let Some(set) = self.sets.get(i) {
169                    covered.extend(set.iter().copied());
170                }
171            }
172        }
173        covered
174    }
175}
176
177impl<W> Problem for MinimumSetCovering<W>
178where
179    W: WeightElement + crate::variant::VariantParam,
180{
181    const NAME: &'static str = "MinimumSetCovering";
182    type Solution = Vec<bool>;
183    type Value = Min<W::Sum>;
184
185    crate::problem_parameters![("num_sets", num_sets), ("universe_size", universe_size),];
186
187    fn evaluate(
188        &self,
189        config: &Self::Solution,
190    ) -> Result<Min<W::Sum>, crate::traits::EvaluationError> {
191        if config.len() != self.sets.len() {
192            return Err(crate::traits::EvaluationError::InvalidConfiguration(
193                "set-selection length does not match the family".into(),
194            ));
195        }
196        Ok({
197            let covered = self.covered_elements(config);
198            let is_valid = covered.len() == self.universe_size
199                && (0..self.universe_size).all(|e| covered.contains(&e));
200            if !is_valid {
201                return Ok(Min(None));
202            }
203            let mut total = W::Sum::zero();
204            for (i, &selected) in config.iter().enumerate() {
205                if selected {
206                    total = W::checked_add_to_sum(
207                        total,
208                        self.weights[i].to_sum(),
209                        "summing selected set-cover weights",
210                    )?;
211                }
212            }
213            Min(Some(total))
214        })
215    }
216
217    fn variant() -> Vec<(&'static str, &'static str)> {
218        crate::variant_params![W]
219    }
220}
221
222impl<W> crate::solvers::BruteForceProblem for MinimumSetCovering<W>
223where
224    W: WeightElement + crate::variant::VariantParam,
225{
226    fn dimensions(&self) -> Vec<usize> {
227        vec![2; self.sets.len()]
228    }
229}
230
231crate::declare_variants! {
232    default MinimumSetCovering<i64> => "2^num_sets" create MinimumSetCoveringCreateSpec,
233}
234
235crate::register_brute_force! {
236    MinimumSetCovering<i64> decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
237}
238
239/// Check if a selection of sets forms a valid set cover.
240#[cfg(test)]
241pub(crate) fn is_set_cover(universe_size: usize, sets: &[Vec<usize>], selected: &[bool]) -> bool {
242    if selected.len() != sets.len() {
243        return false;
244    }
245
246    let mut covered = HashSet::new();
247    for (i, &sel) in selected.iter().enumerate() {
248        if sel {
249            covered.extend(sets[i].iter().copied());
250        }
251    }
252
253    (0..universe_size).all(|e| covered.contains(&e))
254}
255
256#[cfg(feature = "example-db")]
257pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
258    vec![crate::example_db::specs::ModelExampleSpec {
259        id: "minimum_set_covering",
260        instance: Box::new(MinimumSetCovering::<i64>::new(
261            5,
262            vec![vec![0, 1, 2], vec![1, 3], vec![2, 3, 4]],
263        )),
264        optimal_config: serde_json::json!(vec![true, false, true]),
265        optimal_value: serde_json::json!(2),
266    }]
267}
268
269#[cfg(test)]
270#[path = "../../unit_tests/models/set/minimum_set_covering.rs"]
271mod tests;
problemreductions/models/set/minimum_set_covering.rs

problemreductions/models/set/
minimum_set_covering.rs
