converge_optimization/setcover/
mod.rs

1//! Set Cover problem solvers
2//!
3//! The set cover problem: find minimum cost collection of sets
4//! that covers all elements.
5//!
6//! ## Algorithms
7//!
8//! - Greedy: O(n²) approximation with ln(n) guarantee
9//! - Local search: Improve greedy solution
10
11use crate::{Cost, Error, Result, SolverStatus};
12use serde::{Deserialize, Serialize};
13use std::collections::HashSet;
14
15/// A set cover problem instance
16#[derive(Debug, Clone, Serialize, Deserialize)]
17pub struct SetCoverProblem {
18    /// Number of elements to cover
19    pub num_elements: usize,
20    /// Sets: each set is (cost, elements)
21    pub sets: Vec<(Cost, Vec<usize>)>,
22}
23
24impl SetCoverProblem {
25    /// Create a new set cover problem
26    pub fn new(num_elements: usize, sets: Vec<(Cost, Vec<usize>)>) -> Result<Self> {
27        // Validate elements are in range
28        for (_, elements) in &sets {
29            for &e in elements {
30                if e >= num_elements {
31                    return Err(Error::invalid_input(format!(
32                        "element {} out of range [0, {})",
33                        e, num_elements
34                    )));
35                }
36            }
37        }
38        Ok(Self { num_elements, sets })
39    }
40
41    /// Create problem with unit costs
42    pub fn unit_cost(num_elements: usize, sets: Vec<Vec<usize>>) -> Result<Self> {
43        let sets_with_cost = sets.into_iter().map(|s| (1, s)).collect();
44        Self::new(num_elements, sets_with_cost)
45    }
46
47    /// Number of sets
48    pub fn num_sets(&self) -> usize {
49        self.sets.len()
50    }
51}
52
53/// Solution to a set cover problem
54#[derive(Debug, Clone, Serialize, Deserialize)]
55pub struct SetCoverSolution {
56    /// Selected set indices
57    pub selected: Vec<usize>,
58    /// Total cost
59    pub total_cost: Cost,
60    /// Status
61    pub status: SolverStatus,
62}
63
64/// Greedy set cover algorithm
65///
66/// At each step, select the set with best cost-effectiveness
67/// (cost / number of new elements covered).
68pub fn greedy(problem: &SetCoverProblem) -> Result<SetCoverSolution> {
69    let mut uncovered: HashSet<usize> = (0..problem.num_elements).collect();
70    let mut selected = Vec::new();
71    let mut total_cost: Cost = 0;
72
73    while !uncovered.is_empty() {
74        // Find best set (minimum cost per new element)
75        let mut best_set = None;
76        let mut best_ratio = f64::INFINITY;
77
78        for (idx, (cost, elements)) in problem.sets.iter().enumerate() {
79            if selected.contains(&idx) {
80                continue;
81            }
82
83            let new_covered: usize = elements.iter().filter(|e| uncovered.contains(e)).count();
84
85            if new_covered == 0 {
86                continue;
87            }
88
89            let ratio = *cost as f64 / new_covered as f64;
90            if ratio < best_ratio {
91                best_ratio = ratio;
92                best_set = Some(idx);
93            }
94        }
95
96        match best_set {
97            Some(idx) => {
98                let (cost, elements) = &problem.sets[idx];
99                selected.push(idx);
100                total_cost += cost;
101                for &e in elements {
102                    uncovered.remove(&e);
103                }
104            }
105            None => {
106                return Err(Error::infeasible("not all elements can be covered"));
107            }
108        }
109    }
110
111    Ok(SetCoverSolution {
112        selected,
113        total_cost,
114        status: SolverStatus::Feasible, // Greedy is not optimal
115    })
116}
117
118/// Solve set cover using greedy algorithm
119pub fn solve(problem: &SetCoverProblem) -> Result<SetCoverSolution> {
120    greedy(problem)
121}
122
123#[cfg(test)]
124mod tests {
125    use super::*;
126
127    #[test]
128    fn test_simple_cover() {
129        // Elements: {0, 1, 2, 3, 4}
130        // Sets:
131        //   0: {0, 1, 2} cost 1
132        //   1: {2, 3} cost 1
133        //   2: {3, 4} cost 1
134        //   3: {4, 0} cost 1
135        let problem = SetCoverProblem::new(
136            5,
137            vec![
138                (1, vec![0, 1, 2]),
139                (1, vec![2, 3]),
140                (1, vec![3, 4]),
141                (1, vec![4, 0]),
142            ],
143        )
144        .unwrap();
145
146        let solution = solve(&problem).unwrap();
147
148        // Verify all elements covered
149        let mut covered = HashSet::new();
150        for &idx in &solution.selected {
151            for &e in &problem.sets[idx].1 {
152                covered.insert(e);
153            }
154        }
155        assert_eq!(covered.len(), 5);
156    }
157
158    #[test]
159    fn test_unit_cost() {
160        let problem =
161            SetCoverProblem::unit_cost(3, vec![vec![0, 1], vec![1, 2], vec![0, 2]]).unwrap();
162
163        let solution = solve(&problem).unwrap();
164        assert!(solution.total_cost <= 2); // Can be done with 2 sets
165    }
166
167    #[test]
168    fn test_infeasible() {
169        // Element 2 not in any set
170        let problem = SetCoverProblem::new(3, vec![(1, vec![0]), (1, vec![1])]).unwrap();
171
172        let result = solve(&problem);
173        assert!(result.is_err());
174    }
175}
converge_optimization/setcover/mod.rs

converge_optimization/setcover/
mod.rs
