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(&self, target_solution: &[usize]) -> Vec<usize> {
22        target_solution.to_vec()
23    }
24}
25
26#[reduction(
27    overhead = {
28        num_vars = "num_triples",
29        num_constraints = "3 * universe_size",
30    }
31)]
32impl ReduceTo<ILP<bool>> for ThreeDimensionalMatching {
33    type Result = ReductionThreeDimensionalMatchingToILP;
34
35    fn reduce_to(&self) -> Self::Result {
36        let num_vars = self.num_triples();
37        let mut w_constraints = vec![Vec::new(); self.universe_size()];
38        let mut x_constraints = vec![Vec::new(); self.universe_size()];
39        let mut y_constraints = vec![Vec::new(); self.universe_size()];
40
41        for (triple_index, &(w, x, y)) in self.triples().iter().enumerate() {
42            w_constraints[w].push((triple_index, 1.0));
43            x_constraints[x].push((triple_index, 1.0));
44            y_constraints[y].push((triple_index, 1.0));
45        }
46
47        let mut constraints = Vec::with_capacity(3 * self.universe_size());
48        constraints.extend(
49            w_constraints
50                .into_iter()
51                .map(|terms| LinearConstraint::eq(terms, 1.0)),
52        );
53        constraints.extend(
54            x_constraints
55                .into_iter()
56                .map(|terms| LinearConstraint::eq(terms, 1.0)),
57        );
58        constraints.extend(
59            y_constraints
60                .into_iter()
61                .map(|terms| LinearConstraint::eq(terms, 1.0)),
62        );
63
64        ReductionThreeDimensionalMatchingToILP {
65            target: ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize),
66        }
67    }
68}
69
70#[cfg(feature = "example-db")]
71pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
72    use crate::export::SolutionPair;
73
74    vec![crate::example_db::specs::RuleExampleSpec {
75        id: "threedimensionalmatching_to_ilp",
76        build: || {
77            let source = ThreeDimensionalMatching::new(
78                3,
79                vec![(0, 1, 2), (1, 0, 1), (2, 2, 0), (0, 0, 0), (1, 2, 2)],
80            );
81            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
82                source,
83                SolutionPair {
84                    source_config: vec![1, 1, 1, 0, 0],
85                    target_config: vec![1, 1, 1, 0, 0],
86                },
87            )
88        },
89    }]
90}
91
92#[cfg(test)]
93#[path = "../unit_tests/rules/threedimensionalmatching_ilp.rs"]
94mod tests;
problemreductions/rules/threedimensionalmatching_ilp.rs

problemreductions/rules/
threedimensionalmatching_ilp.rs
