problemreductions/rules/
threedimensionalmatching_ilp.rs

1//! Reduction from ThreeDimensionalMatching to `ILP<bool>`.
2
3use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
4use crate::models::set::ThreeDimensionalMatching;
5use crate::reduction;
6use crate::rules::traits::{ReduceTo, ReductionResult};
7
8#[derive(Debug, Clone)]
9pub struct ReductionThreeDimensionalMatchingToILP {
10    target: ILP<bool>,
11}
12
13impl ReductionResult for ReductionThreeDimensionalMatchingToILP {
14    type Source = ThreeDimensionalMatching;
15    type Target = ILP<bool>;
16
17    fn target_problem(&self) -> &ILP<bool> {
18        &self.target
19    }
20
21    fn extract_solution(
22        &self,
23        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
24    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
25        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
26
27        Ok(target_solution.iter().map(|&value| value == 1).collect())
28    }
29}
30
31#[reduction(
32    transform = exact {
33        num_vars = "num_triples",
34        num_constraints = "3 * universe_size",
35    },
36    unavailable = {
37        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
38    }
39)]
40impl ReduceTo<ILP<bool>> for ThreeDimensionalMatching {
41    type Result = ReductionThreeDimensionalMatchingToILP;
42
43    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
44        let num_vars = self.num_triples();
45        let mut w_constraints = vec![Vec::new(); self.universe_size()];
46        let mut x_constraints = vec![Vec::new(); self.universe_size()];
47        let mut y_constraints = vec![Vec::new(); self.universe_size()];
48
49        for (triple_index, &(w, x, y)) in self.triples().iter().enumerate() {
50            w_constraints[w].push((triple_index, 1));
51            x_constraints[x].push((triple_index, 1));
52            y_constraints[y].push((triple_index, 1));
53        }
54
55        let mut constraints = Vec::with_capacity(3 * self.universe_size());
56        constraints.extend(
57            w_constraints
58                .into_iter()
59                .map(|terms| LinearConstraint::eq(terms, 1)),
60        );
61        constraints.extend(
62            x_constraints
63                .into_iter()
64                .map(|terms| LinearConstraint::eq(terms, 1)),
65        );
66        constraints.extend(
67            y_constraints
68                .into_iter()
69                .map(|terms| LinearConstraint::eq(terms, 1)),
70        );
71
72        Ok(ReductionThreeDimensionalMatchingToILP {
73            target: ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
74                .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?,
75        })
76    }
77}
78
79#[cfg(feature = "example-db")]
80pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
81    use crate::export::SolutionPair;
82
83    vec![crate::example_db::specs::RuleExampleSpec {
84        id: "threedimensionalmatching_to_ilp",
85        build: || {
86            let source = ThreeDimensionalMatching::new(
87                3,
88                vec![(0, 1, 2), (1, 0, 1), (2, 2, 0), (0, 0, 0), (1, 2, 2)],
89            );
90            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
91                source,
92                SolutionPair {
93                    source_config: serde_json::json!(vec![true, true, true, false, false]),
94                    target_config: serde_json::json!(vec![1, 1, 1, 0, 0]),
95                },
96            )
97        },
98    }]
99}
100
101#[cfg(test)]
102#[path = "../unit_tests/rules/threedimensionalmatching_ilp.rs"]
103mod tests;
problemreductions/rules/threedimensionalmatching_ilp.rs

problemreductions/rules/
threedimensionalmatching_ilp.rs
