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_witness(
26            self.target_problem(),
27            target_solution,
28            |value| value.value.is_some(),
29            "target ILP assignment is infeasible",
30        )?;
31
32        Ok(target_solution.iter().map(|&value| value == 1).collect())
33    }
34}
35
36#[crate::aggregate_reduction(ilp_feasibility)]
37impl crate::rules::AggregateReductionResult for ReductionThreeDimensionalMatchingToILP {}
38
39#[reduction(
40    transform = exact {
41        max_constraint_magnitude_bits = "1",
42        num_vars = "num_triples",
43        num_constraints = "3 * universe_size",
44        num_nonzeros = "3 * num_triples",
45    },
46)]
47impl ReduceTo<ILP<bool>> for ThreeDimensionalMatching {
48    type Result = ReductionThreeDimensionalMatchingToILP;
49
50    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
51        let num_vars = self.num_triples();
52        let mut w_constraints = vec![Vec::new(); self.universe_size()];
53        let mut x_constraints = vec![Vec::new(); self.universe_size()];
54        let mut y_constraints = vec![Vec::new(); self.universe_size()];
55
56        for (triple_index, &(w, x, y)) in self.triples().iter().enumerate() {
57            w_constraints[w].push((triple_index, 1));
58            x_constraints[x].push((triple_index, 1));
59            y_constraints[y].push((triple_index, 1));
60        }
61
62        let mut constraints = Vec::with_capacity(3 * self.universe_size());
63        constraints.extend(
64            w_constraints
65                .into_iter()
66                .map(|terms| LinearConstraint::eq(terms, 1)),
67        );
68        constraints.extend(
69            x_constraints
70                .into_iter()
71                .map(|terms| LinearConstraint::eq(terms, 1)),
72        );
73        constraints.extend(
74            y_constraints
75                .into_iter()
76                .map(|terms| LinearConstraint::eq(terms, 1)),
77        );
78
79        Ok(ReductionThreeDimensionalMatchingToILP {
80            target: ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
81                .map_err(<Self as ReduceTo<ILP<bool>>>::target_construction)?,
82        })
83    }
84}
85
86#[cfg(feature = "example-db")]
87pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
88    use crate::export::SolutionPair;
89
90    vec![crate::example_db::specs::RuleExampleSpec {
91        id: "threedimensionalmatching_to_ilp",
92        build: || {
93            let source = ThreeDimensionalMatching::new(
94                3,
95                vec![(0, 1, 2), (1, 0, 1), (2, 2, 0), (0, 0, 0), (1, 2, 2)],
96            );
97            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
98                source,
99                SolutionPair {
100                    source_config: serde_json::json!(vec![true, true, true, false, false]),
101                    target_config: serde_json::json!(vec![1, 1, 1, 0, 0]),
102                },
103            )
104        },
105    }]
106}
107
108#[cfg(test)]
109#[path = "../unit_tests/rules/threedimensionalmatching_ilp.rs"]
110mod tests;
problemreductions/rules/threedimensionalmatching_ilp.rs

problemreductions/rules/
threedimensionalmatching_ilp.rs
