problemreductions/rules/
boundeddiameterspanningtree_ilp.rs

1//! A bounded-depth tree rooted at a vertex or the two ends of a center edge.
2use crate::models::algebraic::{Bounded, IntegerVariable, LinearConstraint, ObjectiveSense, ILP};
3use crate::models::graph::BoundedDiameterSpanningTree;
4use crate::rules::traits::{ReduceTo, ReductionResult};
5use crate::topology::SimpleGraph;
6
7#[derive(Debug, Clone)]
8pub struct ReductionBoundedDiameterSpanningTreeToILP {
9    target: ILP<i64, i64, Bounded>,
10    num_edges: usize,
11}
12impl ReductionResult for ReductionBoundedDiameterSpanningTreeToILP {
13    type Source = BoundedDiameterSpanningTree<SimpleGraph, i64>;
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<bool>> {
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        Ok(solution[..self.num_edges].iter().map(|&v| v == 1).collect())
26    }
27}
28#[crate::aggregate_reduction(ilp_feasibility)]
29impl crate::rules::AggregateReductionResult for ReductionBoundedDiameterSpanningTreeToILP {}
30#[crate::reduction(transform = upper_bound {
31    num_vars = "4 * num_edges + 2 * num_vertices",
32    num_constraints = "3 * num_edges + 3 * num_vertices + 2",
33    num_nonzeros = "16 * num_edges + 4 * num_vertices",
34    max_constraint_magnitude_bits = "64",
35})]
36impl ReduceTo<ILP<i64, i64, Bounded>> for BoundedDiameterSpanningTree<SimpleGraph, i64> {
37    type Result = ReductionBoundedDiameterSpanningTreeToILP;
38    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
39        let n = self.num_vertices();
40        let m = self.num_edges();
41        if n == 0 {
42            return Ok(Self::Result {
43                target: ILP::empty(),
44                num_edges: 0,
45            });
46        }
47        let diameter = self.diameter_bound().min(n - 1);
48        let odd = diameter % 2 == 1;
49        let q = Self::exact_i64(diameter / 2, "bounding tree depth")?;
50        let big_m = q + 1;
51        let count = m
52            .checked_mul(if odd { 4 } else { 3 })
53            .and_then(|v| n.checked_mul(2).and_then(|w| v.checked_add(w)))
54            .ok_or_else(|| {
55                crate::rules::ReductionError::integer_overflow::<Self, ILP<i64, i64, Bounded>>(
56                    "counting tree variables",
57                )
58            })?;
59        let root = 3 * m;
60        let depth = root + n;
61        let center = depth + n;
62        let mut variables = vec![IntegerVariable::binary(); count];
63        variables[depth..center]
64            .fill(IntegerVariable::new(Some(0), Some(q)).map_err(Self::target_construction)?);
65        let mut incoming: Vec<_> = (0..n).map(|v| vec![(root + v, 1)]).collect();
66        let mut centers: Vec<_> = (0..n).map(|v| vec![(root + v, 1)]).collect();
67        let mut rows = Vec::new();
68        for (e, &(u, v)) in self.edge_list().iter().enumerate() {
69            let forward = m + 2 * e;
70            let reverse = forward + 1;
71            if u == v {
72                for i in [e, forward, reverse]
73                    .into_iter()
74                    .chain(odd.then_some(center + e))
75                {
76                    variables[i] = IntegerVariable::new(Some(0), Some(0))
77                        .map_err(Self::target_construction)?;
78                }
79            }
80            let mut terms = vec![(e, 1), (forward, -1), (reverse, -1)];
81            if odd {
82                terms.push((center + e, -1));
83            }
84            rows.push(LinearConstraint::eq(terms, 0));
85            incoming[v].push((forward, 1));
86            incoming[u].push((reverse, 1));
87            rows.push(LinearConstraint::ge(
88                vec![(depth + v, 1), (depth + u, -1), (forward, -big_m)],
89                1 - big_m,
90            ));
91            rows.push(LinearConstraint::ge(
92                vec![(depth + u, 1), (depth + v, -1), (reverse, -big_m)],
93                1 - big_m,
94            ));
95            if odd {
96                centers[u].push((center + e, -1));
97                if u != v {
98                    centers[v].push((center + e, -1));
99                }
100            }
101        }
102        for (v, terms) in incoming.into_iter().enumerate() {
103            rows.push(LinearConstraint::eq(terms, 1));
104            rows.push(LinearConstraint::le(vec![(depth + v, 1), (root + v, q)], q));
105        }
106        if odd {
107            rows.push(LinearConstraint::eq(
108                (0..m).map(|e| (center + e, 1)).collect(),
109                1,
110            ));
111            rows.extend(
112                centers
113                    .into_iter()
114                    .map(|terms| LinearConstraint::eq(terms, 0)),
115            );
116        } else {
117            rows.push(LinearConstraint::eq(
118                (0..n).map(|v| (root + v, 1)).collect(),
119                1,
120            ));
121        }
122        rows.push(LinearConstraint::le(
123            self.edge_weights().iter().copied().enumerate().collect(),
124            *self.weight_bound(),
125        ));
126        let target = ILP::with_variables(variables, rows, vec![], ObjectiveSense::Minimize)
127            .map_err(Self::target_construction)?;
128        crate::rules::ilp_helpers::validate_bounded_constraint_arithmetic::<Self>(&target)?;
129        Ok(Self::Result {
130            target,
131            num_edges: m,
132        })
133    }
134}
135#[cfg(feature = "example-db")]
136pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
137    vec![crate::example_db::specs::RuleExampleSpec {
138        id: "boundeddiameterspanningtree_to_ilp",
139        build: || {
140            crate::example_db::specs::rule_example_via_bounded_ilp(
141                BoundedDiameterSpanningTree::new(
142                    SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]),
143                    vec![1; 3],
144                    3,
145                    3,
146                ),
147            )
148        },
149    }]
150}
151#[cfg(test)]
152#[path = "../unit_tests/rules/boundeddiameterspanningtree_ilp.rs"]
153mod tests;
problemreductions/rules/boundeddiameterspanningtree_ilp.rs

problemreductions/rules/
boundeddiameterspanningtree_ilp.rs
