problemreductions/models/set/
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::graph_types::SimpleGraph;
7use crate::traits::{ConstraintSatisfactionProblem, Problem};
8use crate::types::{EnergyMode, LocalConstraint, LocalSolutionSize, ProblemSize, SolutionSize};
9use serde::{Deserialize, Serialize};
10use std::collections::HashSet;
11
12/// The Set Covering problem.
13///
14/// Given a universe U of elements and a collection S of subsets of U,
15/// each with a weight, find a minimum weight subcollection of S
16/// that covers all elements in U.
17///
18/// # Example
19///
20/// ```
21/// use problemreductions::models::set::SetCovering;
22/// use problemreductions::{Problem, Solver, BruteForce};
23///
24/// // Universe: {0, 1, 2, 3}
25/// // Sets: S0={0,1}, S1={1,2}, S2={2,3}, S3={0,3}
26/// let problem = SetCovering::<i32>::new(
27///     4, // universe size
28///     vec![
29///         vec![0, 1],
30///         vec![1, 2],
31///         vec![2, 3],
32///         vec![0, 3],
33///     ],
34/// );
35///
36/// let solver = BruteForce::new();
37/// let solutions = solver.find_best(&problem);
38///
39/// // Verify solutions cover all elements
40/// for sol in solutions {
41///     assert!(problem.solution_size(&sol).is_valid);
42/// }
43/// ```
44#[derive(Debug, Clone, Serialize, Deserialize)]
45pub struct SetCovering<W = i32> {
46    /// Size of the universe (elements are 0..universe_size).
47    universe_size: usize,
48    /// Collection of sets, each represented as a vector of elements.
49    sets: Vec<Vec<usize>>,
50    /// Weights for each set.
51    weights: Vec<W>,
52}
53
54impl<W: Clone + Default> SetCovering<W> {
55    /// Create a new Set Covering problem with unit weights.
56    pub fn new(universe_size: usize, sets: Vec<Vec<usize>>) -> Self
57    where
58        W: From<i32>,
59    {
60        let num_sets = sets.len();
61        let weights = vec![W::from(1); num_sets];
62        Self {
63            universe_size,
64            sets,
65            weights,
66        }
67    }
68
69    /// Create a new Set Covering problem with custom weights.
70    pub fn with_weights(universe_size: usize, sets: Vec<Vec<usize>>, weights: Vec<W>) -> Self {
71        assert_eq!(sets.len(), weights.len());
72        Self {
73            universe_size,
74            sets,
75            weights,
76        }
77    }
78
79    /// Get the universe size.
80    pub fn universe_size(&self) -> usize {
81        self.universe_size
82    }
83
84    /// Get the number of sets.
85    pub fn num_sets(&self) -> usize {
86        self.sets.len()
87    }
88
89    /// Get the sets.
90    pub fn sets(&self) -> &[Vec<usize>] {
91        &self.sets
92    }
93
94    /// Get a specific set.
95    pub fn get_set(&self, index: usize) -> Option<&Vec<usize>> {
96        self.sets.get(index)
97    }
98
99    /// Check which elements are covered by selected sets.
100    pub fn covered_elements(&self, config: &[usize]) -> HashSet<usize> {
101        let mut covered = HashSet::new();
102        for (i, &selected) in config.iter().enumerate() {
103            if selected == 1 {
104                if let Some(set) = self.sets.get(i) {
105                    covered.extend(set.iter().copied());
106                }
107            }
108        }
109        covered
110    }
111}
112
113impl<W> Problem for SetCovering<W>
114where
115    W: Clone + Default + PartialOrd + num_traits::Num + num_traits::Zero + std::ops::AddAssign + 'static,
116{
117    const NAME: &'static str = "SetCovering";
118    type GraphType = SimpleGraph;
119    type Weight = W;
120    type Size = W;
121
122    fn num_variables(&self) -> usize {
123        self.sets.len()
124    }
125
126    fn num_flavors(&self) -> usize {
127        2
128    }
129
130    fn problem_size(&self) -> ProblemSize {
131        ProblemSize::new(vec![
132            ("universe_size", self.universe_size),
133            ("num_sets", self.sets.len()),
134        ])
135    }
136
137    fn energy_mode(&self) -> EnergyMode {
138        EnergyMode::SmallerSizeIsBetter // Minimize total weight
139    }
140
141    fn solution_size(&self, config: &[usize]) -> SolutionSize<Self::Size> {
142        let covered = self.covered_elements(config);
143        let is_valid = covered.len() == self.universe_size
144            && (0..self.universe_size).all(|e| covered.contains(&e));
145
146        let mut total = W::zero();
147        for (i, &selected) in config.iter().enumerate() {
148            if selected == 1 {
149                total += self.weights[i].clone();
150            }
151        }
152        SolutionSize::new(total, is_valid)
153    }
154}
155
156impl<W> ConstraintSatisfactionProblem for SetCovering<W>
157where
158    W: Clone + Default + PartialOrd + num_traits::Num + num_traits::Zero + std::ops::AddAssign + 'static,
159{
160    fn constraints(&self) -> Vec<LocalConstraint> {
161        // For each element, at least one set containing it must be selected
162        (0..self.universe_size)
163            .map(|element| {
164                // Find all sets containing this element
165                let containing_sets: Vec<usize> = self
166                    .sets
167                    .iter()
168                    .enumerate()
169                    .filter(|(_, set)| set.contains(&element))
170                    .map(|(i, _)| i)
171                    .collect();
172
173                // Create constraint: at least one must be selected
174                let num_vars = containing_sets.len();
175                let num_configs = 2usize.pow(num_vars as u32);
176
177                // All configs are valid except all-zeros
178                let mut spec = vec![true; num_configs];
179                spec[0] = false; // (0, 0, ..., 0) is invalid
180
181                LocalConstraint::new(2, containing_sets, spec)
182            })
183            .collect()
184    }
185
186    fn objectives(&self) -> Vec<LocalSolutionSize<Self::Size>> {
187        self.weights
188            .iter()
189            .enumerate()
190            .map(|(i, w)| LocalSolutionSize::new(2, vec![i], vec![W::zero(), w.clone()]))
191            .collect()
192    }
193
194    fn weights(&self) -> Vec<Self::Size> {
195        self.weights.clone()
196    }
197
198    fn set_weights(&mut self, weights: Vec<Self::Size>) {
199        assert_eq!(weights.len(), self.num_variables());
200        self.weights = weights;
201    }
202
203    fn is_weighted(&self) -> bool {
204        if self.weights.is_empty() {
205            return false;
206        }
207        let first = &self.weights[0];
208        !self.weights.iter().all(|w| w == first)
209    }
210}
211
212/// Check if a selection of sets forms a valid set cover.
213pub fn is_set_cover(universe_size: usize, sets: &[Vec<usize>], selected: &[bool]) -> bool {
214    if selected.len() != sets.len() {
215        return false;
216    }
217
218    let mut covered = HashSet::new();
219    for (i, &sel) in selected.iter().enumerate() {
220        if sel {
221            covered.extend(sets[i].iter().copied());
222        }
223    }
224
225    (0..universe_size).all(|e| covered.contains(&e))
226}
227
228#[cfg(test)]
229mod tests {
230    use super::*;
231    use crate::solvers::{BruteForce, Solver};
232
233    #[test]
234    fn test_set_covering_creation() {
235        let problem = SetCovering::<i32>::new(4, vec![vec![0, 1], vec![1, 2], vec![2, 3]]);
236        assert_eq!(problem.universe_size(), 4);
237        assert_eq!(problem.num_sets(), 3);
238        assert_eq!(problem.num_variables(), 3);
239    }
240
241    #[test]
242    fn test_set_covering_with_weights() {
243        let problem = SetCovering::with_weights(3, vec![vec![0, 1], vec![1, 2]], vec![5, 10]);
244        assert_eq!(problem.weights(), vec![5, 10]);
245        assert!(problem.is_weighted());
246    }
247
248    #[test]
249    fn test_covered_elements() {
250        let problem = SetCovering::<i32>::new(4, vec![vec![0, 1], vec![1, 2], vec![2, 3]]);
251
252        let covered = problem.covered_elements(&[1, 0, 0]);
253        assert!(covered.contains(&0));
254        assert!(covered.contains(&1));
255        assert!(!covered.contains(&2));
256
257        let covered = problem.covered_elements(&[1, 0, 1]);
258        assert!(covered.contains(&0));
259        assert!(covered.contains(&1));
260        assert!(covered.contains(&2));
261        assert!(covered.contains(&3));
262    }
263
264    #[test]
265    fn test_solution_size_valid() {
266        let problem = SetCovering::<i32>::new(4, vec![vec![0, 1], vec![1, 2], vec![2, 3]]);
267
268        // Select first and third sets: covers {0,1} ∪ {2,3} = {0,1,2,3}
269        let sol = problem.solution_size(&[1, 0, 1]);
270        assert!(sol.is_valid);
271        assert_eq!(sol.size, 2);
272
273        // Select all sets
274        let sol = problem.solution_size(&[1, 1, 1]);
275        assert!(sol.is_valid);
276        assert_eq!(sol.size, 3);
277    }
278
279    #[test]
280    fn test_solution_size_invalid() {
281        let problem = SetCovering::<i32>::new(4, vec![vec![0, 1], vec![1, 2], vec![2, 3]]);
282
283        // Select only first set: missing 2, 3
284        let sol = problem.solution_size(&[1, 0, 0]);
285        assert!(!sol.is_valid);
286
287        // Select none
288        let sol = problem.solution_size(&[0, 0, 0]);
289        assert!(!sol.is_valid);
290    }
291
292    #[test]
293    fn test_brute_force_simple() {
294        // Universe {0,1,2}, sets: {0,1}, {1,2}, {0,2}
295        // Minimum cover: any 2 sets work
296        let problem = SetCovering::<i32>::new(3, vec![vec![0, 1], vec![1, 2], vec![0, 2]]);
297        let solver = BruteForce::new();
298
299        let solutions = solver.find_best(&problem);
300        for sol in &solutions {
301            assert_eq!(sol.iter().sum::<usize>(), 2);
302            assert!(problem.solution_size(sol).is_valid);
303        }
304    }
305
306    #[test]
307    fn test_brute_force_weighted() {
308        // Prefer lighter sets
309        let problem =
310            SetCovering::with_weights(3, vec![vec![0, 1, 2], vec![0, 1], vec![2]], vec![10, 3, 3]);
311        let solver = BruteForce::new();
312
313        let solutions = solver.find_best(&problem);
314        // Should select sets 1 and 2 (total 6) instead of set 0 (total 10)
315        assert_eq!(solutions.len(), 1);
316        assert_eq!(solutions[0], vec![0, 1, 1]);
317    }
318
319    #[test]
320    fn test_is_set_cover_function() {
321        let sets = vec![vec![0, 1], vec![1, 2], vec![2, 3]];
322
323        assert!(is_set_cover(4, &sets, &[true, false, true]));
324        assert!(is_set_cover(4, &sets, &[true, true, true]));
325        assert!(!is_set_cover(4, &sets, &[true, false, false]));
326        assert!(!is_set_cover(4, &sets, &[false, false, false]));
327    }
328
329    #[test]
330    fn test_get_set() {
331        let problem = SetCovering::<i32>::new(4, vec![vec![0, 1], vec![2, 3]]);
332        assert_eq!(problem.get_set(0), Some(&vec![0, 1]));
333        assert_eq!(problem.get_set(1), Some(&vec![2, 3]));
334        assert_eq!(problem.get_set(2), None);
335    }
336
337    #[test]
338    fn test_energy_mode() {
339        let problem = SetCovering::<i32>::new(2, vec![vec![0, 1]]);
340        assert!(problem.energy_mode().is_minimization());
341    }
342
343    #[test]
344    fn test_constraints() {
345        let problem = SetCovering::<i32>::new(3, vec![vec![0, 1], vec![1, 2]]);
346        let constraints = problem.constraints();
347        // One constraint per element
348        assert_eq!(constraints.len(), 3);
349    }
350
351    #[test]
352    fn test_single_set_covers_all() {
353        let problem = SetCovering::<i32>::new(3, vec![vec![0, 1, 2], vec![0], vec![1], vec![2]]);
354        let solver = BruteForce::new();
355
356        let solutions = solver.find_best(&problem);
357        // First set alone covers everything
358        assert_eq!(solutions.len(), 1);
359        assert_eq!(solutions[0], vec![1, 0, 0, 0]);
360    }
361
362    #[test]
363    fn test_overlapping_sets() {
364        // All sets overlap on element 1
365        let problem = SetCovering::<i32>::new(3, vec![vec![0, 1], vec![1, 2], vec![1]]);
366        let solver = BruteForce::new();
367
368        let solutions = solver.find_best(&problem);
369        // Minimum is selecting first two sets
370        for sol in &solutions {
371            assert_eq!(sol.iter().sum::<usize>(), 2);
372        }
373    }
374
375    #[test]
376    fn test_is_satisfied() {
377        let problem = SetCovering::<i32>::new(3, vec![vec![0, 1], vec![1, 2]]);
378
379        assert!(problem.is_satisfied(&[1, 1, 0])); // Note: 3 vars needed
380        assert!(!problem.is_satisfied(&[1, 0]));
381    }
382
383    #[test]
384    fn test_empty_universe() {
385        let problem = SetCovering::<i32>::new(0, vec![]);
386        let sol = problem.solution_size(&[]);
387        assert!(sol.is_valid); // Empty universe is trivially covered
388        assert_eq!(sol.size, 0);
389    }
390
391    #[test]
392    fn test_objectives() {
393        let problem = SetCovering::with_weights(3, vec![vec![0, 1], vec![1, 2]], vec![5, 10]);
394        let objectives = problem.objectives();
395        assert_eq!(objectives.len(), 2);
396    }
397
398    #[test]
399    fn test_set_weights() {
400        let mut problem = SetCovering::<i32>::new(3, vec![vec![0, 1], vec![1, 2]]);
401        assert!(!problem.is_weighted()); // Initially uniform
402        problem.set_weights(vec![1, 2]);
403        assert!(problem.is_weighted());
404        assert_eq!(problem.weights(), vec![1, 2]);
405    }
406
407    #[test]
408    fn test_is_weighted_empty() {
409        let problem = SetCovering::<i32>::new(0, vec![]);
410        assert!(!problem.is_weighted());
411    }
412
413    #[test]
414    fn test_is_set_cover_wrong_len() {
415        let sets = vec![vec![0, 1], vec![1, 2]];
416        assert!(!is_set_cover(3, &sets, &[true])); // Wrong length
417    }
418
419    #[test]
420    fn test_problem_size() {
421        let problem = SetCovering::<i32>::new(5, vec![vec![0, 1], vec![1, 2], vec![3, 4]]);
422        let size = problem.problem_size();
423        assert_eq!(size.get("universe_size"), Some(5));
424        assert_eq!(size.get("num_sets"), Some(3));
425    }
426}
problemreductions/models/set/set_covering.rs

problemreductions/models/set/
set_covering.rs
