problemreductions/rules/
maximumleafspanningtree_ilp.rs

1//! Reduction from MaximumLeafSpanningTree to ILP (Integer Linear Programming).
2//!
3//! Uses a single-commodity flow formulation for spanning tree connectivity
4//! (rooted at vertex 0) combined with leaf-indicator variables.
5//!
6//! Variable layout (all non-negative integers, bounded by explicit constraints):
7//! - `y_e` for each undirected edge `e` (indices `0..m`): edge selector (binary)
8//! - `z_v` for each vertex `v` (indices `m..m+n`): leaf indicator (binary)
9//! - `f_{2e}`, `f_{2e+1}` for each edge `e=(u,v)` (indices `m+n..m+n+2m`):
10//!   directed flow from u to v and v to u respectively
11//!
12//! Constraints:
13//! 1. Tree cardinality: sum(y_e) = n-1
14//! 2. Flow conservation: net inflow = 1 for each non-root vertex; net outflow = n-1 for root
15//! 3. Flow-edge linking: f_{uv} + f_{vu} <= (n-1) * y_e
16//! 4. Leaf detection: degree_v <= 1 + (n-2)*(1 - z_v) for each vertex v
17//! 5. Variable bounds: y_e <= 1, z_v <= 1
18//!
19//! Objective: maximize sum(z_v)
20
21use crate::models::algebraic::{Bounded, IntegerVariable, LinearConstraint, ObjectiveSense, ILP};
22use crate::models::graph::MaximumLeafSpanningTree;
23use crate::reduction;
24use crate::rules::traits::{ReduceTo, ReductionResult};
25use crate::topology::{Graph, SimpleGraph};
26
27/// Result of reducing MaximumLeafSpanningTree to ILP.
28#[derive(Debug, Clone)]
29pub struct ReductionMaximumLeafSpanningTreeToILP {
30    target: ILP<i64, i64, Bounded>,
31    num_edges: usize,
32}
33
34impl ReductionResult for ReductionMaximumLeafSpanningTreeToILP {
35    type Source = MaximumLeafSpanningTree<SimpleGraph>;
36    type Target = ILP<i64, i64, Bounded>;
37
38    fn target_problem(&self) -> &ILP<i64, i64, Bounded> {
39        &self.target
40    }
41
42    fn extract_solution(
43        &self,
44        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
45    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
46        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
47
48        Ok({
49            // First m variables are edge selectors
50            target_solution[..self.num_edges]
51                .iter()
52                .map(|&value| value == 1)
53                .collect()
54        })
55    }
56}
57
58#[reduction(transform = {
59    exact {
60        num_vars = "3 * num_edges + num_vertices",
61        num_constraints = "3 * num_vertices + 2 * num_edges + 1",
62    },
63    upper_bound {
64        max_constraint_magnitude_bits = "num_vertices + 2",
65        num_nonzeros = "(3 * num_edges + num_vertices) * (3 * num_vertices + 2 * num_edges + 1)",
66    },
67})]
68impl ReduceTo<ILP<i64, i64, Bounded>> for MaximumLeafSpanningTree<SimpleGraph> {
69    type Result = ReductionMaximumLeafSpanningTreeToILP;
70
71    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
72        let n = self.num_vertices();
73        let m = self.num_edges();
74        let edges = self.graph().edges();
75        let root = 0usize;
76        let n_i64 = Self::exact_i64(n, "encoding the spanning-tree order")?;
77
78        let num_vars = 3 * m + n;
79        // Variable indices
80        let edge_var = |e: usize| e; // y_e: 0..m
81        let leaf_var = |v: usize| m + v; // z_v: m..m+n
82        let flow_var = |e: usize, dir: usize| m + n + 2 * e + dir; // f: m+n..m+n+2m
83
84        let mut constraints = Vec::new();
85
86        // 1. Tree cardinality: sum(y_e) = n - 1
87        let terms: Vec<(usize, i64)> = (0..m).map(|e| (edge_var(e), 1)).collect();
88        constraints.push(LinearConstraint::eq(terms, n_i64 - 1));
89
90        // 2. Flow conservation
91        // Build incidence: for each vertex, which edges are incident and which direction
92        for vertex in 0..n {
93            let mut terms = Vec::new();
94            for (edge_idx, &(u, v)) in edges.iter().enumerate() {
95                // flow_var(e, 0) is flow from u to v
96                // flow_var(e, 1) is flow from v to u
97                if v == vertex {
98                    // inflow from edge direction u->v
99                    terms.push((flow_var(edge_idx, 0), 1));
100                    // outflow from edge direction v->u
101                    terms.push((flow_var(edge_idx, 1), -1));
102                }
103                if u == vertex {
104                    // outflow from edge direction u->v
105                    terms.push((flow_var(edge_idx, 0), -1));
106                    // inflow from edge direction v->u
107                    terms.push((flow_var(edge_idx, 1), 1));
108                }
109            }
110
111            let rhs = if vertex == root {
112                // Root sends n-1 units out => net inflow = -(n-1)
113                1 - n_i64
114            } else {
115                // Each non-root vertex receives exactly 1 unit
116                1
117            };
118            constraints.push(LinearConstraint::eq(terms, rhs));
119        }
120
121        // 3. Flow-edge linking: f_{uv} + f_{vu} <= (n-1) * y_e
122        for edge_idx in 0..m {
123            constraints.push(LinearConstraint::le(
124                vec![
125                    (flow_var(edge_idx, 0), 1),
126                    (flow_var(edge_idx, 1), 1),
127                    (edge_var(edge_idx), 1 - n_i64),
128                ],
129                0,
130            ));
131        }
132
133        // 4. Leaf detection: for each vertex v,
134        //    degree_v <= 1 + (n-2)*(1 - z_v)
135        //    i.e. sum_{e incident to v} y_e + (n-2)*z_v <= n-1
136        // Build incidence lists
137        let mut incident: Vec<Vec<usize>> = vec![vec![]; n];
138        for (edge_idx, &(u, v)) in edges.iter().enumerate() {
139            incident[u].push(edge_idx);
140            incident[v].push(edge_idx);
141        }
142
143        for (v, inc) in incident.iter().enumerate() {
144            let mut terms: Vec<(usize, i64)> = inc.iter().map(|&e| (edge_var(e), 1)).collect();
145            terms.push((leaf_var(v), n_i64 - 2));
146            constraints.push(LinearConstraint::le(terms, n_i64 - 1));
147        }
148
149        // 5. Variable bounds: y_e <= 1, z_v <= 1
150        for e in 0..m {
151            constraints.push(LinearConstraint::le(vec![(edge_var(e), 1)], 1));
152        }
153        for v in 0..n {
154            constraints.push(LinearConstraint::le(vec![(leaf_var(v), 1)], 1));
155        }
156
157        // Objective: maximize sum(z_v)
158        let objective: Vec<(usize, i64)> = (0..n).map(|v| (leaf_var(v), 1)).collect();
159
160        let mut variables = vec![IntegerVariable::binary(); num_vars];
161        variables[m + n..].fill(
162            IntegerVariable::new(Some(0), Some((n_i64 - 1).max(0)))
163                .map_err(Self::target_construction)?,
164        );
165
166        let target =
167            ILP::with_variables(variables, constraints, objective, ObjectiveSense::Maximize)
168                .map_err(Self::target_construction)?;
169
170        Ok(ReductionMaximumLeafSpanningTreeToILP {
171            target,
172            num_edges: m,
173        })
174    }
175}
176
177#[cfg(feature = "example-db")]
178pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
179    vec![crate::example_db::specs::RuleExampleSpec {
180        id: "maximumleafspanningtree_to_ilp",
181        build: || {
182            let source = MaximumLeafSpanningTree::new(SimpleGraph::new(
183                4,
184                vec![(0, 1), (1, 2), (2, 3), (0, 2)],
185            ));
186            crate::example_db::specs::rule_example_via_bounded_ilp::<_>(source)
187        },
188    }]
189}
190
191#[cfg(test)]
192#[path = "../unit_tests/rules/maximumleafspanningtree_ilp.rs"]
193mod tests;
problemreductions/rules/maximumleafspanningtree_ilp.rs

problemreductions/rules/
maximumleafspanningtree_ilp.rs
