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(transform = {
47    exact {
48        num_vars = "num_sets",
49        num_constraints = "universe_size",
50    },
51    upper_bound {
52        max_constraint_magnitude_bits = "1",
53        num_nonzeros = "num_sets * universe_size",
54    },
55})]
56impl ReduceTo<ILP<bool>> for MinimumSetCovering<i64> {
57    type Result = ReductionSCToILP;
58
59    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
60        let num_vars = self.num_sets();
61
62        // Constraints: For each element e, sum_{j: e in set_j} x_j >= 1
63        // This ensures each element is covered by at least one selected set
64        let constraints: Vec<LinearConstraint> = (0..self.universe_size())
65            .map(|element| {
66                // Find all sets containing this element
67                let terms: Vec<(usize, i64)> = self
68                    .sets()
69                    .iter()
70                    .enumerate()
71                    .filter(|(_, set)| set.contains(&element))
72                    .map(|(j, _)| (j, 1))
73                    .collect();
74
75                LinearConstraint::ge(terms, 1)
76            })
77            .collect();
78
79        // Objective: minimize sum of w_i * x_i (weighted sum of selected sets)
80        let objective: Vec<(usize, i64)> = self
81            .weights_ref()
82            .iter()
83            .enumerate()
84            .map(|(set, &weight)| (set, weight))
85            .collect();
86
87        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
88            .map_err(Self::target_construction)?;
89
90        Ok(ReductionSCToILP { target })
91    }
92}
93
94#[cfg(feature = "example-db")]
95pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
96    vec![crate::example_db::specs::RuleExampleSpec {
97        id: "minimumsetcovering_to_ilp",
98        build: || {
99            let source = MinimumSetCovering::new(
100                8,
101                vec![
102                    vec![0, 1, 2],
103                    vec![2, 3, 4],
104                    vec![4, 5, 6],
105                    vec![6, 7, 0],
106                    vec![1, 3, 5],
107                    vec![0, 4, 7],
108                ],
109            );
110            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
111        },
112    }]
113}
114
115#[cfg(test)]
116#[path = "../unit_tests/rules/minimumsetcovering_ilp.rs"]
117mod tests;
problemreductions/rules/minimumsetcovering_ilp.rs

problemreductions/rules/
minimumsetcovering_ilp.rs
