problemreductions/rules/
minimumsetcovering_ilp.rs

1//! Reduction from MinimumSetCovering to ILP (Integer Linear Programming).
2//!
3//! The Set Covering problem can be formulated as a binary ILP:
4//! - Variables: One binary variable per set (0 = not selected, 1 = selected)
5//! - Constraints: For each element e: sum_{j: e in set_j} x_j >= 1 (element must be covered)
6//! - Objective: Minimize the sum of weights of selected sets
7
8use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
9use crate::models::set::MinimumSetCovering;
10use crate::reduction;
11use crate::rules::traits::{ReduceTo, ReductionResult};
12
13/// Result of reducing MinimumSetCovering to ILP.
14///
15/// This reduction creates a binary ILP where:
16/// - Each set corresponds to a binary variable
17/// - Element coverage constraints ensure each element is covered by at least one selected set
18/// - The objective minimizes the total weight of selected sets
19#[derive(Debug, Clone)]
20pub struct ReductionSCToILP {
21    target: ILP<bool>,
22}
23
24impl ReductionResult for ReductionSCToILP {
25    type Source = MinimumSetCovering<i64>;
26    type Target = ILP<bool>;
27
28    fn target_problem(&self) -> &ILP<bool> {
29        &self.target
30    }
31
32    /// Extract solution from ILP back to MinimumSetCovering.
33    ///
34    /// Since the mapping is 1:1 (each set maps to one binary variable),
35    /// the solution extraction is simply copying the configuration.
36    fn extract_solution(
37        &self,
38        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
39    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
40        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
41
42        Ok(target_solution.iter().map(|&value| value == 1).collect())
43    }
44}
45
46#[reduction(
47    transform = exact {
48        num_vars = "num_sets",
49        num_constraints = "universe_size",
50    },
51    unavailable = {
52        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
53    }
54)]
55impl ReduceTo<ILP<bool>> for MinimumSetCovering<i64> {
56    type Result = ReductionSCToILP;
57
58    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
59        let num_vars = self.num_sets();
60
61        // Constraints: For each element e, sum_{j: e in set_j} x_j >= 1
62        // This ensures each element is covered by at least one selected set
63        let constraints: Vec<LinearConstraint> = (0..self.universe_size())
64            .map(|element| {
65                // Find all sets containing this element
66                let terms: Vec<(usize, i64)> = self
67                    .sets()
68                    .iter()
69                    .enumerate()
70                    .filter(|(_, set)| set.contains(&element))
71                    .map(|(j, _)| (j, 1))
72                    .collect();
73
74                LinearConstraint::ge(terms, 1)
75            })
76            .collect();
77
78        // Objective: minimize sum of w_i * x_i (weighted sum of selected sets)
79        let objective: Vec<(usize, i64)> = self
80            .weights_ref()
81            .iter()
82            .enumerate()
83            .map(|(set, &weight)| (set, weight))
84            .collect();
85
86        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
87            .map_err(Self::target_construction)?;
88
89        Ok(ReductionSCToILP { target })
90    }
91}
92
93#[cfg(feature = "example-db")]
94pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
95    vec![crate::example_db::specs::RuleExampleSpec {
96        id: "minimumsetcovering_to_ilp",
97        build: || {
98            let source = MinimumSetCovering::new(
99                8,
100                vec![
101                    vec![0, 1, 2],
102                    vec![2, 3, 4],
103                    vec![4, 5, 6],
104                    vec![6, 7, 0],
105                    vec![1, 3, 5],
106                    vec![0, 4, 7],
107                ],
108            );
109            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
110        },
111    }]
112}
113
114#[cfg(test)]
115#[path = "../unit_tests/rules/minimumsetcovering_ilp.rs"]
116mod tests;
problemreductions/rules/minimumsetcovering_ilp.rs

problemreductions/rules/
minimumsetcovering_ilp.rs
