problemreductions/rules/
minimumfaultdetectiontestset_ilp.rs

1//! Reduction from MinimumFaultDetectionTestSet to ILP.
2//!
3//! Each input-output pair becomes a binary decision variable. For every
4//! internal vertex, the ILP requires at least one selected pair whose coverage
5//! set contains that vertex. Minimizing the sum of the pair variables therefore
6//! recovers the minimum-size covering test set.
7
8use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
9use crate::models::misc::MinimumFaultDetectionTestSet;
10use crate::reduction;
11use crate::rules::traits::{ReduceTo, ReductionResult};
12use std::collections::VecDeque;
13
14/// Result of reducing MinimumFaultDetectionTestSet to `ILP<bool>`.
15#[derive(Debug, Clone)]
16pub struct ReductionMFDTSToILP {
17    target: ILP<bool>,
18    num_inputs: usize,
19    num_outputs: usize,
20}
21
22impl ReductionResult for ReductionMFDTSToILP {
23    type Source = MinimumFaultDetectionTestSet;
24    type Target = ILP<bool>;
25
26    fn target_problem(&self) -> &ILP<bool> {
27        &self.target
28    }
29
30    fn extract_solution(
31        &self,
32        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
33    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
34        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
35
36        Ok((0..self.num_inputs)
37            .map(|input| {
38                (0..self.num_outputs)
39                    .map(|output| target_solution[input * self.num_outputs + output] == 1)
40                    .collect()
41            })
42            .collect())
43    }
44}
45
46#[reduction(
47    transform = exact {
48        num_vars = "num_inputs * num_outputs",
49        num_constraints = "num_vertices - num_inputs - num_outputs",
50    },
51    unavailable = {
52        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
53    }
54)]
55impl ReduceTo<ILP<bool>> for MinimumFaultDetectionTestSet {
56    type Result = ReductionMFDTSToILP;
57
58    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
59        fn reachable(adj: &[Vec<usize>], start: usize) -> Vec<bool> {
60            let mut seen = vec![false; adj.len()];
61            let mut queue = VecDeque::new();
62            seen[start] = true;
63            queue.push_back(start);
64
65            while let Some(vertex) = queue.pop_front() {
66                for &next in &adj[vertex] {
67                    if !seen[next] {
68                        seen[next] = true;
69                        queue.push_back(next);
70                    }
71                }
72            }
73
74            seen
75        }
76
77        let mut adj = vec![Vec::new(); self.num_vertices()];
78        let mut rev_adj = vec![Vec::new(); self.num_vertices()];
79        for &(tail, head) in self.arcs() {
80            adj[tail].push(head);
81            rev_adj[head].push(tail);
82        }
83
84        let input_reachability: Vec<Vec<bool>> = self
85            .inputs()
86            .iter()
87            .map(|&input| reachable(&adj, input))
88            .collect();
89        let output_reachability: Vec<Vec<bool>> = self
90            .outputs()
91            .iter()
92            .map(|&output| reachable(&rev_adj, output))
93            .collect();
94
95        let mut boundary = vec![false; self.num_vertices()];
96        for &input in self.inputs() {
97            boundary[input] = true;
98        }
99        for &output in self.outputs() {
100            boundary[output] = true;
101        }
102
103        let num_pairs = self.num_inputs() * self.num_outputs();
104        let internal_vertices: Vec<usize> = (0..self.num_vertices())
105            .filter(|&vertex| !boundary[vertex])
106            .collect();
107
108        let constraints: Vec<LinearConstraint> = internal_vertices
109            .into_iter()
110            .map(|vertex| {
111                let mut terms = Vec::new();
112                for (input_idx, input_cov) in input_reachability.iter().enumerate() {
113                    for (output_idx, output_cov) in output_reachability.iter().enumerate() {
114                        if input_cov[vertex] && output_cov[vertex] {
115                            let pair_idx = input_idx * self.num_outputs() + output_idx;
116                            terms.push((pair_idx, 1));
117                        }
118                    }
119                }
120                LinearConstraint::ge(terms, 1)
121            })
122            .collect();
123
124        let objective = (0..num_pairs).map(|pair_idx| (pair_idx, 1)).collect();
125
126        Ok(ReductionMFDTSToILP {
127            target: ILP::new(num_pairs, constraints, objective, ObjectiveSense::Minimize)
128                .map_err(Self::target_construction)?,
129            num_inputs: self.num_inputs(),
130            num_outputs: self.num_outputs(),
131        })
132    }
133}
134
135#[cfg(feature = "example-db")]
136pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
137    vec![crate::example_db::specs::RuleExampleSpec {
138        id: "minimumfaultdetectiontestset_to_ilp",
139        build: || {
140            let source = MinimumFaultDetectionTestSet::new(
141                7,
142                vec![
143                    (0, 2),
144                    (0, 3),
145                    (1, 3),
146                    (1, 4),
147                    (2, 5),
148                    (3, 5),
149                    (3, 6),
150                    (4, 6),
151                ],
152                vec![0, 1],
153                vec![5, 6],
154            );
155            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
156        },
157    }]
158}
159
160#[cfg(test)]
161#[path = "../unit_tests/rules/minimumfaultdetectiontestset_ilp.rs"]
162mod tests;
problemreductions/rules/minimumfaultdetectiontestset_ilp.rs

problemreductions/rules/
minimumfaultdetectiontestset_ilp.rs
