problemreductions/rules/
minimumhittingset_ilp.rs

1//! Reduction from MinimumHittingSet to ILP (Integer Linear Programming).
2//!
3//! Binary variable x_e per universe element; for each set S,
4//! require Σ_{e∈S} x_e ≥ 1 (set is hit). Minimize Σ x_e.
5
6use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
7use crate::models::set::MinimumHittingSet;
8use crate::reduction;
9use crate::rules::traits::{ReduceTo, ReductionResult};
10
11#[derive(Debug, Clone)]
12pub struct ReductionHSToILP {
13    target: ILP<bool>,
14}
15
16impl ReductionResult for ReductionHSToILP {
17    type Source = MinimumHittingSet;
18    type Target = ILP<bool>;
19
20    fn target_problem(&self) -> &ILP<bool> {
21        &self.target
22    }
23
24    fn extract_solution(
25        &self,
26        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
27    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
28        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
29
30        Ok(target_solution.iter().map(|&value| value == 1).collect())
31    }
32}
33
34#[reduction(transform = {
35    exact {
36        num_vars = "universe_size",
37        num_constraints = "num_sets",
38    },
39    upper_bound {
40        max_constraint_magnitude_bits = "1",
41        num_nonzeros = "universe_size * num_sets",
42    },
43})]
44impl ReduceTo<ILP<bool>> for MinimumHittingSet {
45    type Result = ReductionHSToILP;
46
47    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
48        let num_vars = self.universe_size();
49        let constraints: Vec<LinearConstraint> = self
50            .sets()
51            .iter()
52            .map(|set| {
53                let terms: Vec<(usize, i64)> = set.iter().map(|&e| (e, 1)).collect();
54                LinearConstraint::ge(terms, 1)
55            })
56            .collect();
57        let objective: Vec<(usize, i64)> = (0..num_vars).map(|i| (i, 1)).collect();
58        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
59            .map_err(Self::target_construction)?;
60        Ok(ReductionHSToILP { target })
61    }
62}
63
64#[cfg(feature = "example-db")]
65pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
66    vec![crate::example_db::specs::RuleExampleSpec {
67        id: "minimumhittingset_to_ilp",
68        build: || {
69            let source = MinimumHittingSet::new(4, vec![vec![0, 1], vec![2, 3], vec![1, 2]]);
70            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
71        },
72    }]
73}
74
75#[cfg(test)]
76#[path = "../unit_tests/rules/minimumhittingset_ilp.rs"]
77mod tests;
problemreductions/rules/minimumhittingset_ilp.rs

problemreductions/rules/
minimumhittingset_ilp.rs
