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::{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<i32>,
31    num_edges: usize,
32}
33
34impl ReductionResult for ReductionMaximumLeafSpanningTreeToILP {
35    type Source = MaximumLeafSpanningTree<SimpleGraph>;
36    type Target = ILP<i32>;
37
38    fn target_problem(&self) -> &ILP<i32> {
39        &self.target
40    }
41
42    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
43        // First m variables are edge selectors
44        target_solution[..self.num_edges].to_vec()
45    }
46}
47
48#[reduction(
49    overhead = {
50        num_vars = "3 * num_edges + num_vertices",
51        num_constraints = "3 * num_vertices + 2 * num_edges + 1",
52    }
53)]
54impl ReduceTo<ILP<i32>> for MaximumLeafSpanningTree<SimpleGraph> {
55    type Result = ReductionMaximumLeafSpanningTreeToILP;
56
57    fn reduce_to(&self) -> Self::Result {
58        let n = self.num_vertices();
59        let m = self.num_edges();
60        let edges = self.graph().edges();
61        let root = 0usize;
62
63        let num_vars = 3 * m + n;
64        // Variable indices
65        let edge_var = |e: usize| e; // y_e: 0..m
66        let leaf_var = |v: usize| m + v; // z_v: m..m+n
67        let flow_var = |e: usize, dir: usize| m + n + 2 * e + dir; // f: m+n..m+n+2m
68
69        let mut constraints = Vec::new();
70
71        // 1. Tree cardinality: sum(y_e) = n - 1
72        let terms: Vec<(usize, f64)> = (0..m).map(|e| (edge_var(e), 1.0)).collect();
73        constraints.push(LinearConstraint::eq(terms, (n - 1) as f64));
74
75        // 2. Flow conservation
76        // Build incidence: for each vertex, which edges are incident and which direction
77        for vertex in 0..n {
78            let mut terms = Vec::new();
79            for (edge_idx, &(u, v)) in edges.iter().enumerate() {
80                // flow_var(e, 0) is flow from u to v
81                // flow_var(e, 1) is flow from v to u
82                if v == vertex {
83                    // inflow from edge direction u->v
84                    terms.push((flow_var(edge_idx, 0), 1.0));
85                    // outflow from edge direction v->u
86                    terms.push((flow_var(edge_idx, 1), -1.0));
87                }
88                if u == vertex {
89                    // outflow from edge direction u->v
90                    terms.push((flow_var(edge_idx, 0), -1.0));
91                    // inflow from edge direction v->u
92                    terms.push((flow_var(edge_idx, 1), 1.0));
93                }
94            }
95
96            let rhs = if vertex == root {
97                // Root sends n-1 units out => net inflow = -(n-1)
98                -((n - 1) as f64)
99            } else {
100                // Each non-root vertex receives exactly 1 unit
101                1.0
102            };
103            constraints.push(LinearConstraint::eq(terms, rhs));
104        }
105
106        // 3. Flow-edge linking: f_{uv} + f_{vu} <= (n-1) * y_e
107        for edge_idx in 0..m {
108            constraints.push(LinearConstraint::le(
109                vec![
110                    (flow_var(edge_idx, 0), 1.0),
111                    (flow_var(edge_idx, 1), 1.0),
112                    (edge_var(edge_idx), -((n - 1) as f64)),
113                ],
114                0.0,
115            ));
116        }
117
118        // 4. Leaf detection: for each vertex v,
119        //    degree_v <= 1 + (n-2)*(1 - z_v)
120        //    i.e. sum_{e incident to v} y_e + (n-2)*z_v <= n-1
121        // Build incidence lists
122        let mut incident: Vec<Vec<usize>> = vec![vec![]; n];
123        for (edge_idx, &(u, v)) in edges.iter().enumerate() {
124            incident[u].push(edge_idx);
125            incident[v].push(edge_idx);
126        }
127
128        for (v, inc) in incident.iter().enumerate() {
129            let mut terms: Vec<(usize, f64)> = inc.iter().map(|&e| (edge_var(e), 1.0)).collect();
130            terms.push((leaf_var(v), (n - 2) as f64));
131            constraints.push(LinearConstraint::le(terms, (n - 1) as f64));
132        }
133
134        // 5. Variable bounds: y_e <= 1, z_v <= 1
135        for e in 0..m {
136            constraints.push(LinearConstraint::le(vec![(edge_var(e), 1.0)], 1.0));
137        }
138        for v in 0..n {
139            constraints.push(LinearConstraint::le(vec![(leaf_var(v), 1.0)], 1.0));
140        }
141
142        // Objective: maximize sum(z_v)
143        let objective: Vec<(usize, f64)> = (0..n).map(|v| (leaf_var(v), 1.0)).collect();
144
145        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Maximize);
146
147        ReductionMaximumLeafSpanningTreeToILP {
148            target,
149            num_edges: m,
150        }
151    }
152}
153
154#[cfg(feature = "example-db")]
155pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
156    vec![crate::example_db::specs::RuleExampleSpec {
157        id: "maximumleafspanningtree_to_ilp",
158        build: || {
159            let source = MaximumLeafSpanningTree::new(SimpleGraph::new(
160                4,
161                vec![(0, 1), (1, 2), (2, 3), (0, 2)],
162            ));
163            crate::example_db::specs::rule_example_via_ilp::<_, i32>(source)
164        },
165    }]
166}
167
168#[cfg(test)]
169#[path = "../unit_tests/rules/maximumleafspanningtree_ilp.rs"]
170mod tests;
problemreductions/rules/maximumleafspanningtree_ilp.rs

problemreductions/rules/
maximumleafspanningtree_ilp.rs
