problemreductions/rules/
minimumcapacitatedspanningtree_ilp.rs

1//! Reduction from MinimumCapacitatedSpanningTree to ILP (Integer Linear Programming).
2//!
3//! Uses a requirement-weighted single-commodity flow formulation:
4//! - Each non-root vertex generates r(v) units of flow toward the root
5//! - Flow on each edge is bounded by the capacity constraint
6//! - Flow-edge linking ensures flow only travels on selected edges
7//!
8//! Variable layout (all non-negative integers, ILP<i32>):
9//! - `y_e` for each undirected edge `e` (indices `0..m`): edge selector (binary)
10//! - `f_{2e}`, `f_{2e+1}` for each edge `e=(u,v)` (indices `m..3m`):
11//!   directed flow from u to v and v to u respectively
12//!
13//! Constraints:
14//! 1. Tree cardinality: sum(y_e) = n-1
15//! 2. Binary edge bounds: y_e <= 1
16//! 3. Flow conservation: each non-root vertex v generates r(v) units;
17//!    root absorbs all (total R = sum of requirements)
18//! 4. Flow-edge linking: f_{uv} + f_{vu} <= R * y_e
19//! 5. Capacity: f_{uv} <= c and f_{vu} <= c for each directed edge
20//!
21//! Objective: minimize sum(w_e * y_e)
22
23use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
24use crate::models::graph::MinimumCapacitatedSpanningTree;
25use crate::reduction;
26use crate::rules::traits::{ReduceTo, ReductionResult};
27use crate::topology::{Graph, SimpleGraph};
28use crate::types::WeightElement;
29
30/// Result of reducing MinimumCapacitatedSpanningTree to ILP.
31#[derive(Debug, Clone)]
32pub struct ReductionMinimumCapacitatedSpanningTreeToILP {
33    target: ILP<i32>,
34    num_edges: usize,
35}
36
37impl ReductionResult for ReductionMinimumCapacitatedSpanningTreeToILP {
38    type Source = MinimumCapacitatedSpanningTree<SimpleGraph, i32>;
39    type Target = ILP<i32>;
40
41    fn target_problem(&self) -> &ILP<i32> {
42        &self.target
43    }
44
45    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
46        // First m variables are edge selectors
47        target_solution[..self.num_edges].to_vec()
48    }
49}
50
51#[reduction(
52    overhead = {
53        num_vars = "3 * num_edges",
54        num_constraints = "5 * num_edges + num_vertices + 1",
55    }
56)]
57impl ReduceTo<ILP<i32>> for MinimumCapacitatedSpanningTree<SimpleGraph, i32> {
58    type Result = ReductionMinimumCapacitatedSpanningTreeToILP;
59
60    fn reduce_to(&self) -> Self::Result {
61        let n = self.num_vertices();
62        let m = self.num_edges();
63        let edges = self.graph().edges();
64        let root = self.root();
65        let requirements = self.requirements();
66        let cap = *self.capacity() as f64;
67
68        let num_vars = 3 * m;
69
70        // Variable indices
71        let edge_var = |e: usize| e; // y_e: 0..m
72        let flow_var = |e: usize, dir: usize| m + 2 * e + dir; // f: m..3m
73
74        // Total requirement (flow from all non-root vertices to root)
75        let total_req: f64 = requirements.iter().map(|r| r.to_sum() as f64).sum();
76
77        let mut constraints = Vec::new();
78
79        // 1. Tree cardinality: sum(y_e) = n - 1
80        let terms: Vec<(usize, f64)> = (0..m).map(|e| (edge_var(e), 1.0)).collect();
81        constraints.push(LinearConstraint::eq(terms, (n - 1) as f64));
82
83        // 2. Binary edge bounds: y_e <= 1
84        for e in 0..m {
85            constraints.push(LinearConstraint::le(vec![(edge_var(e), 1.0)], 1.0));
86        }
87
88        // 3. Flow conservation
89        // For non-root vertex v: outflow - inflow = r(v)
90        // For root: inflow - outflow = total_req (i.e., outflow - inflow = -total_req)
91        for (vertex, req) in requirements.iter().enumerate() {
92            let mut terms = Vec::new();
93            for (edge_idx, &(u, v)) in edges.iter().enumerate() {
94                // flow_var(e, 0) = flow from u to v
95                // flow_var(e, 1) = flow from v to u
96                if v == vertex {
97                    // inflow from u->v direction
98                    terms.push((flow_var(edge_idx, 0), 1.0));
99                    // outflow from v->u direction
100                    terms.push((flow_var(edge_idx, 1), -1.0));
101                }
102                if u == vertex {
103                    // outflow from u->v direction
104                    terms.push((flow_var(edge_idx, 0), -1.0));
105                    // inflow from v->u direction
106                    terms.push((flow_var(edge_idx, 1), 1.0));
107                }
108            }
109
110            let rhs = if vertex == root {
111                // Root absorbs all flow: net inflow = total_req
112                total_req
113            } else {
114                // Non-root vertex generates r(v) units toward root:
115                // net inflow = -r(v)
116                -(req.to_sum() as f64)
117            };
118            constraints.push(LinearConstraint::eq(terms, rhs));
119        }
120
121        // 4. Flow-edge linking: f_{uv} + f_{vu} <= R * y_e
122        for edge_idx in 0..m {
123            constraints.push(LinearConstraint::le(
124                vec![
125                    (flow_var(edge_idx, 0), 1.0),
126                    (flow_var(edge_idx, 1), 1.0),
127                    (edge_var(edge_idx), -total_req),
128                ],
129                0.0,
130            ));
131        }
132
133        // 5. Capacity bounds: f_{uv} <= c, f_{vu} <= c
134        for edge_idx in 0..m {
135            constraints.push(LinearConstraint::le(
136                vec![(flow_var(edge_idx, 0), 1.0)],
137                cap,
138            ));
139            constraints.push(LinearConstraint::le(
140                vec![(flow_var(edge_idx, 1), 1.0)],
141                cap,
142            ));
143        }
144
145        // Objective: minimize sum(w_e * y_e)
146        let objective: Vec<(usize, f64)> = self
147            .weights()
148            .iter()
149            .enumerate()
150            .map(|(edge_idx, w)| (edge_var(edge_idx), w.to_sum() as f64))
151            .collect();
152
153        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize);
154
155        ReductionMinimumCapacitatedSpanningTreeToILP {
156            target,
157            num_edges: m,
158        }
159    }
160}
161
162#[cfg(feature = "example-db")]
163pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
164    vec![crate::example_db::specs::RuleExampleSpec {
165        id: "minimumcapacitatedspanningtree_to_ilp",
166        build: || {
167            let source = MinimumCapacitatedSpanningTree::new(
168                SimpleGraph::new(4, vec![(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)]),
169                vec![2, 3, 1, 1, 2], // edge weights
170                0,                   // root
171                vec![0, 1, 1, 1],    // requirements
172                2,                   // capacity
173            );
174            crate::example_db::specs::rule_example_via_ilp::<_, i32>(source)
175        },
176    }]
177}
178
179#[cfg(test)]
180#[path = "../unit_tests/rules/minimumcapacitatedspanningtree_ilp.rs"]
181mod tests;
problemreductions/rules/minimumcapacitatedspanningtree_ilp.rs

problemreductions/rules/
minimumcapacitatedspanningtree_ilp.rs
