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(&self, target_solution: &[usize]) -> Vec<usize> {
25        target_solution.to_vec()
26    }
27}
28
29#[reduction(
30    overhead = {
31        num_vars = "universe_size",
32        num_constraints = "num_sets",
33    }
34)]
35impl ReduceTo<ILP<bool>> for MinimumHittingSet {
36    type Result = ReductionHSToILP;
37
38    fn reduce_to(&self) -> Self::Result {
39        let num_vars = self.universe_size();
40        let constraints: Vec<LinearConstraint> = self
41            .sets()
42            .iter()
43            .map(|set| {
44                let terms: Vec<(usize, f64)> = set.iter().map(|&e| (e, 1.0)).collect();
45                LinearConstraint::ge(terms, 1.0)
46            })
47            .collect();
48        let objective: Vec<(usize, f64)> = (0..num_vars).map(|i| (i, 1.0)).collect();
49        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize);
50        ReductionHSToILP { target }
51    }
52}
53
54#[cfg(feature = "example-db")]
55pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
56    vec![crate::example_db::specs::RuleExampleSpec {
57        id: "minimumhittingset_to_ilp",
58        build: || {
59            let source = MinimumHittingSet::new(4, vec![vec![0, 1], vec![2, 3], vec![1, 2]]);
60            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
61        },
62    }]
63}
64
65#[cfg(test)]
66#[path = "../unit_tests/rules/minimumhittingset_ilp.rs"]
67mod tests;
problemreductions/rules/minimumhittingset_ilp.rs

problemreductions/rules/
minimumhittingset_ilp.rs
