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

problemreductions/rules/
minimumsetcovering_ilp.rs
