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// One variable per input/output list pair and one row per non-boundary vertex.
47// Boundary membership is a union, so list lengths cannot be subtracted from n.
48// Nonempty terminal lists guarantee at least one boundary vertex; each remaining
49// vertex contributes at most one coefficient per pair, including repeated inputs.
50#[reduction(transform = {
51    exact {
52        num_vars = "num_inputs * num_outputs",
53    },
54    upper_bound {
55        max_constraint_magnitude_bits = "1",
56        num_constraints = "num_vertices - 1",
57        num_nonzeros = "num_inputs * num_outputs * (num_vertices - 1)",
58    },
59})]
60impl ReduceTo<ILP<bool>> for MinimumFaultDetectionTestSet {
61    type Result = ReductionMFDTSToILP;
62
63    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
64        fn reachable(adj: &[Vec<usize>], start: usize) -> Vec<bool> {
65            let mut seen = vec![false; adj.len()];
66            let mut queue = VecDeque::new();
67            seen[start] = true;
68            queue.push_back(start);
69
70            while let Some(vertex) = queue.pop_front() {
71                for &next in &adj[vertex] {
72                    if !seen[next] {
73                        seen[next] = true;
74                        queue.push_back(next);
75                    }
76                }
77            }
78
79            seen
80        }
81
82        let mut adj = vec![Vec::new(); self.num_vertices()];
83        let mut rev_adj = vec![Vec::new(); self.num_vertices()];
84        for &(tail, head) in self.arcs() {
85            adj[tail].push(head);
86            rev_adj[head].push(tail);
87        }
88
89        let input_reachability: Vec<Vec<bool>> = self
90            .inputs()
91            .iter()
92            .map(|&input| reachable(&adj, input))
93            .collect();
94        let output_reachability: Vec<Vec<bool>> = self
95            .outputs()
96            .iter()
97            .map(|&output| reachable(&rev_adj, output))
98            .collect();
99
100        let mut boundary = vec![false; self.num_vertices()];
101        for &input in self.inputs() {
102            boundary[input] = true;
103        }
104        for &output in self.outputs() {
105            boundary[output] = true;
106        }
107
108        let num_pairs = self.num_inputs() * self.num_outputs();
109        let internal_vertices: Vec<usize> = (0..self.num_vertices())
110            .filter(|&vertex| !boundary[vertex])
111            .collect();
112
113        let constraints: Vec<LinearConstraint> = internal_vertices
114            .into_iter()
115            .map(|vertex| {
116                let mut terms = Vec::new();
117                for (input_idx, input_cov) in input_reachability.iter().enumerate() {
118                    for (output_idx, output_cov) in output_reachability.iter().enumerate() {
119                        if input_cov[vertex] && output_cov[vertex] {
120                            let pair_idx = input_idx * self.num_outputs() + output_idx;
121                            terms.push((pair_idx, 1));
122                        }
123                    }
124                }
125                LinearConstraint::ge(terms, 1)
126            })
127            .collect();
128
129        let objective = (0..num_pairs).map(|pair_idx| (pair_idx, 1)).collect();
130
131        Ok(ReductionMFDTSToILP {
132            target: ILP::new(num_pairs, constraints, objective, ObjectiveSense::Minimize)
133                .map_err(Self::target_construction)?,
134            num_inputs: self.num_inputs(),
135            num_outputs: self.num_outputs(),
136        })
137    }
138}
139
140#[cfg(feature = "example-db")]
141pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
142    vec![crate::example_db::specs::RuleExampleSpec {
143        id: "minimumfaultdetectiontestset_to_ilp",
144        build: || {
145            let source = MinimumFaultDetectionTestSet::new(
146                7,
147                vec![
148                    (0, 2),
149                    (0, 3),
150                    (1, 3),
151                    (1, 4),
152                    (2, 5),
153                    (3, 5),
154                    (3, 6),
155                    (4, 6),
156                ],
157                vec![0, 1],
158                vec![5, 6],
159            );
160            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
161        },
162    }]
163}
164
165#[cfg(test)]
166#[path = "../unit_tests/rules/minimumfaultdetectiontestset_ilp.rs"]
167mod tests;
problemreductions/rules/minimumfaultdetectiontestset_ilp.rs

problemreductions/rules/
minimumfaultdetectiontestset_ilp.rs
