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(
35    transform = exact {
36        num_vars = "universe_size",
37        num_constraints = "num_sets",
38    },
39    unavailable = {
40        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
41    }
42)]
43impl ReduceTo<ILP<bool>> for MinimumHittingSet {
44    type Result = ReductionHSToILP;
45
46    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
47        let num_vars = self.universe_size();
48        let constraints: Vec<LinearConstraint> = self
49            .sets()
50            .iter()
51            .map(|set| {
52                let terms: Vec<(usize, i64)> = set.iter().map(|&e| (e, 1)).collect();
53                LinearConstraint::ge(terms, 1)
54            })
55            .collect();
56        let objective: Vec<(usize, i64)> = (0..num_vars).map(|i| (i, 1)).collect();
57        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
58            .map_err(Self::target_construction)?;
59        Ok(ReductionHSToILP { target })
60    }
61}
62
63#[cfg(feature = "example-db")]
64pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
65    vec![crate::example_db::specs::RuleExampleSpec {
66        id: "minimumhittingset_to_ilp",
67        build: || {
68            let source = MinimumHittingSet::new(4, vec![vec![0, 1], vec![2, 3], vec![1, 2]]);
69            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
70        },
71    }]
72}
73
74#[cfg(test)]
75#[path = "../unit_tests/rules/minimumhittingset_ilp.rs"]
76mod tests;
problemreductions/rules/minimumhittingset_ilp.rs

problemreductions/rules/
minimumhittingset_ilp.rs
