problemreductions/rules/
partitionintoperfectmatchings_ilp.rs

1//! Group labels with exact same-group edge indicators and degree one.
2use crate::models::algebraic::{Bounded, IntegerVariable, LinearConstraint, ObjectiveSense, ILP};
3use crate::models::graph::PartitionIntoPerfectMatchings;
4use crate::rules::traits::{ReduceTo, ReductionResult};
5use crate::topology::{Graph, SimpleGraph};
6
7#[derive(Debug, Clone)]
8pub struct ReductionPartitionIntoPerfectMatchingsToILP {
9    target: ILP<i64, i64, Bounded>,
10    num_vertices: usize,
11}
12impl ReductionResult for ReductionPartitionIntoPerfectMatchingsToILP {
13    type Source = PartitionIntoPerfectMatchings<SimpleGraph>;
14    type Target = ILP<i64, i64, Bounded>;
15    fn target_problem(&self) -> &Self::Target {
16        &self.target
17    }
18    fn extract_solution(&self, solution: &Vec<i64>) -> crate::rules::ExtractionResult<Vec<usize>> {
19        crate::rules::traits::validate_target_witness(
20            &self.target,
21            solution,
22            |v| v.value.is_some(),
23            "target ILP assignment is infeasible",
24        )?;
25        crate::rules::ilp_helpers::decode_usize_values(&solution[..self.num_vertices])
26    }
27}
28#[crate::aggregate_reduction(ilp_feasibility)]
29impl crate::rules::AggregateReductionResult for ReductionPartitionIntoPerfectMatchingsToILP {}
30#[crate::reduction(transform = upper_bound {
31    num_vars = "num_vertices + 2 * num_edges",
32    num_constraints = "num_vertices + 4 * num_edges",
33    num_nonzeros = "16 * num_edges",
34    max_constraint_magnitude_bits = "num_matchings",
35})]
36impl ReduceTo<ILP<i64, i64, Bounded>> for PartitionIntoPerfectMatchings<SimpleGraph> {
37    type Result = ReductionPartitionIntoPerfectMatchingsToILP;
38    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
39        let n = self.num_vertices();
40        let k = Self::exact_i64(self.num_matchings(), "bounding matching-group labels")?;
41        // The source counts distinct other neighbors, ignoring loops and multiplicity.
42        let mut edges: Vec<_> = self
43            .graph()
44            .edges()
45            .into_iter()
46            .filter(|(u, v)| u != v)
47            .map(|(u, v)| (u.min(v), u.max(v)))
48            .collect();
49        edges.sort_unstable();
50        edges.dedup();
51        let m = edges.len();
52        let count = m
53            .checked_mul(2)
54            .and_then(|v| v.checked_add(n))
55            .ok_or_else(|| {
56                crate::rules::ReductionError::integer_overflow::<Self, ILP<i64, i64, Bounded>>(
57                    "counting matching-partition variables",
58                )
59            })?;
60        let mut variables =
61            vec![IntegerVariable::new(Some(0), Some(k - 1)).map_err(Self::target_construction)?; n];
62        variables.resize(count, IntegerVariable::binary());
63        let mut degree = vec![Vec::new(); n];
64        let mut rows = Vec::new();
65        for (i, &(u, v)) in edges.iter().enumerate() {
66            let same = n + i;
67            let direction = n + m + i;
68            degree[u].push((same, 1));
69            degree[v].push((same, 1));
70            rows.push(LinearConstraint::le(
71                vec![(v, 1), (u, -1), (same, k - 1)],
72                k - 1,
73            ));
74            rows.push(LinearConstraint::le(
75                vec![(u, 1), (v, -1), (same, k - 1)],
76                k - 1,
77            ));
78            rows.push(LinearConstraint::ge(
79                vec![(v, 1), (u, -1), (direction, -k), (same, 1)],
80                1 - k,
81            ));
82            rows.push(LinearConstraint::ge(
83                vec![(u, 1), (v, -1), (direction, k), (same, 1)],
84                1,
85            ));
86        }
87        rows.extend(
88            degree
89                .into_iter()
90                .map(|terms| LinearConstraint::eq(terms, 1)),
91        );
92        let target = ILP::with_variables(variables, rows, vec![], ObjectiveSense::Minimize)
93            .map_err(Self::target_construction)?;
94        crate::rules::ilp_helpers::validate_bounded_constraint_arithmetic::<Self>(&target)?;
95        Ok(Self::Result {
96            target,
97            num_vertices: n,
98        })
99    }
100}
101#[cfg(feature = "example-db")]
102pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
103    vec![crate::example_db::specs::RuleExampleSpec {
104        id: "partitionintoperfectmatchings_to_ilp",
105        build: || {
106            crate::example_db::specs::rule_example_via_bounded_ilp(
107                PartitionIntoPerfectMatchings::new(
108                    SimpleGraph::new(4, vec![(0, 1), (0, 2), (1, 3), (2, 3)]),
109                    2,
110                ),
111            )
112        },
113    }]
114}
115#[cfg(test)]
116#[path = "../unit_tests/rules/partitionintoperfectmatchings_ilp.rs"]
117mod tests;
problemreductions/rules/partitionintoperfectmatchings_ilp.rs

problemreductions/rules/
partitionintoperfectmatchings_ilp.rs
