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<i64, i64, Bounded>`):
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 requirement flow from u to v and v to u respectively
12//! - `g_{2e}`, `g_{2e+1}` for each edge `e=(u,v)` (indices `3m..5m`):
13//!   directed unit-demand connectivity flow
14//!
15//! Constraints:
16//! 1. Tree cardinality: sum(y_e) = n-1
17//! 2. Binary edge bounds: y_e <= 1
18//! 3. Flow conservation: each non-root vertex v generates r(v) units;
19//!    root absorbs all (total R = sum of requirements)
20//! 4. Flow-edge linking: f_{uv} + f_{vu} <= R * y_e
21//! 5. Capacity: f_{uv} <= c and f_{vu} <= c for each directed edge
22//! 6. Connectivity flow: each non-root vertex sends one unit to the root,
23//!    linked to selected edges by g_{uv} + g_{vu} <= (n-1)y_e
24//!
25//! Objective: minimize sum(w_e * y_e)
26
27use crate::models::algebraic::{Bounded, IntegerVariable, LinearConstraint, ObjectiveSense, ILP};
28use crate::models::graph::MinimumCapacitatedSpanningTree;
29use crate::reduction;
30use crate::rules::traits::{ReduceTo, ReductionResult};
31use crate::topology::{Graph, SimpleGraph};
32use crate::types::WeightElement;
33
34/// Result of reducing MinimumCapacitatedSpanningTree to ILP.
35#[derive(Debug, Clone)]
36pub struct ReductionMinimumCapacitatedSpanningTreeToILP {
37    target: ILP<i64, i64, Bounded>,
38    num_edges: usize,
39}
40
41impl ReductionResult for ReductionMinimumCapacitatedSpanningTreeToILP {
42    type Source = MinimumCapacitatedSpanningTree<SimpleGraph, i64>;
43    type Target = ILP<i64, i64, Bounded>;
44
45    fn target_problem(&self) -> &ILP<i64, i64, Bounded> {
46        &self.target
47    }
48
49    fn extract_solution(
50        &self,
51        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
52    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
53        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
54
55        Ok({
56            // First m variables are edge selectors
57            target_solution[..self.num_edges]
58                .iter()
59                .map(|&value| value == 1)
60                .collect()
61        })
62    }
63}
64
65// Five edge variables per edge; all row blocks are unconditional. Nonzeros:
66// cardinality m, binary m, two conservation blocks 8m, linking 6m, capacity 2m.
67#[reduction(transform = {
68    exact {
69        num_vars = "5 * num_edges",
70        num_constraints = "5 * num_edges + 2 * num_vertices + 1",
71    },
72    upper_bound {
73        max_constraint_magnitude_bits = "max_requirement_bits + num_vertices",
74        num_nonzeros = "18 * num_edges",
75    },
76})]
77impl ReduceTo<ILP<i64, i64, Bounded>> for MinimumCapacitatedSpanningTree<SimpleGraph, i64> {
78    type Result = ReductionMinimumCapacitatedSpanningTreeToILP;
79
80    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
81        let n = self.num_vertices();
82        let m = self.num_edges();
83        let edges = self.graph().edges();
84        let root = self.root();
85        let requirements = self.requirements();
86        let cap = *self.capacity();
87
88        let num_vars = 5 * m;
89
90        // Variable indices
91        let edge_var = |e: usize| e; // y_e: 0..m
92        let flow_var = |e: usize, dir: usize| m + 2 * e + dir; // f: m..3m
93        let connectivity_var = |e: usize, dir: usize| 3 * m + 2 * e + dir; // g: 3m..5m
94
95        // Total requirement (flow from all non-root vertices to root)
96        let total_req = requirements
97            .iter()
98            .enumerate()
99            .filter(|(vertex, _)| *vertex != root)
100            .try_fold(0_i64, |total, (_, requirement)| {
101                total.checked_add(requirement.to_sum()).ok_or_else(|| {
102                    crate::rules::ReductionError::integer_overflow::<
103                        MinimumCapacitatedSpanningTree<SimpleGraph, i64>,
104                        ILP<i64, i64, Bounded>,
105                    >("summing vertex requirements")
106                })
107            })?;
108        let mut constraints = Vec::new();
109
110        // 1. Tree cardinality: sum(y_e) = n - 1
111        let terms: Vec<(usize, i64)> = (0..m).map(|e| (edge_var(e), 1)).collect();
112        constraints.push(LinearConstraint::eq(
113            terms,
114            Self::exact_i64(n, "encoding the spanning-tree order")? - 1,
115        ));
116
117        // 2. Binary edge bounds: y_e <= 1
118        for e in 0..m {
119            constraints.push(LinearConstraint::le(vec![(edge_var(e), 1)], 1));
120        }
121
122        // 3. Flow conservation
123        // For non-root vertex v: outflow - inflow = r(v)
124        // For root: inflow - outflow = total_req (i.e., outflow - inflow = -total_req)
125        for (vertex, req) in requirements.iter().enumerate() {
126            let mut terms = Vec::new();
127            for (edge_idx, &(u, v)) in edges.iter().enumerate() {
128                // flow_var(e, 0) = flow from u to v
129                // flow_var(e, 1) = flow from v to u
130                if v == vertex {
131                    // inflow from u->v direction
132                    terms.push((flow_var(edge_idx, 0), 1));
133                    // outflow from v->u direction
134                    terms.push((flow_var(edge_idx, 1), -1));
135                }
136                if u == vertex {
137                    // outflow from u->v direction
138                    terms.push((flow_var(edge_idx, 0), -1));
139                    // inflow from v->u direction
140                    terms.push((flow_var(edge_idx, 1), 1));
141                }
142            }
143
144            let rhs = if vertex == root {
145                // Root absorbs all flow: net inflow = total_req
146                total_req
147            } else {
148                // Non-root vertex generates r(v) units toward root:
149                // net inflow = -r(v)
150                -req.to_sum()
151            };
152            constraints.push(LinearConstraint::eq(terms, rhs));
153        }
154
155        // 4. Flow-edge linking: f_{uv} + f_{vu} <= R * y_e
156        for edge_idx in 0..m {
157            constraints.push(LinearConstraint::le(
158                vec![
159                    (flow_var(edge_idx, 0), 1),
160                    (flow_var(edge_idx, 1), 1),
161                    (edge_var(edge_idx), -total_req),
162                ],
163                0,
164            ));
165        }
166
167        // 5. Capacity bounds: f_{uv} <= c, f_{vu} <= c
168        for edge_idx in 0..m {
169            constraints.push(LinearConstraint::le(vec![(flow_var(edge_idx, 0), 1)], cap));
170            constraints.push(LinearConstraint::le(vec![(flow_var(edge_idx, 1), 1)], cap));
171        }
172
173        // 6. Unit-demand flow guarantees that every vertex is connected to the root,
174        // including vertices whose capacity requirement is zero.
175        let connectivity_total = Self::exact_i64(n, "encoding connectivity flow")? - 1;
176        for vertex in 0..n {
177            let mut terms = Vec::new();
178            for (edge_idx, &(u, v)) in edges.iter().enumerate() {
179                if v == vertex {
180                    terms.push((connectivity_var(edge_idx, 0), 1));
181                    terms.push((connectivity_var(edge_idx, 1), -1));
182                }
183                if u == vertex {
184                    terms.push((connectivity_var(edge_idx, 0), -1));
185                    terms.push((connectivity_var(edge_idx, 1), 1));
186                }
187            }
188            let rhs = if vertex == root {
189                connectivity_total
190            } else {
191                -1
192            };
193            constraints.push(LinearConstraint::eq(terms, rhs));
194        }
195        for edge_idx in 0..m {
196            constraints.push(LinearConstraint::le(
197                vec![
198                    (connectivity_var(edge_idx, 0), 1),
199                    (connectivity_var(edge_idx, 1), 1),
200                    (edge_var(edge_idx), -connectivity_total),
201                ],
202                0,
203            ));
204        }
205
206        // Objective: minimize sum(w_e * y_e)
207        let objective: Vec<(usize, i64)> = self
208            .weights()
209            .iter()
210            .enumerate()
211            .map(|(edge_idx, weight)| (edge_var(edge_idx), weight.to_sum()))
212            .collect();
213
214        let mut variables = vec![IntegerVariable::binary(); num_vars];
215        variables[m..3 * m].fill(
216            IntegerVariable::new(Some(0), Some(cap.min(total_req).max(0)))
217                .map_err(Self::target_construction)?,
218        );
219        variables[3 * m..].fill(
220            IntegerVariable::new(Some(0), Some(connectivity_total))
221                .map_err(Self::target_construction)?,
222        );
223
224        let target =
225            ILP::with_variables(variables, constraints, objective, ObjectiveSense::Minimize)
226                .map_err(Self::target_construction)?;
227
228        Ok(ReductionMinimumCapacitatedSpanningTreeToILP {
229            target,
230            num_edges: m,
231        })
232    }
233}
234
235#[cfg(feature = "example-db")]
236pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
237    vec![crate::example_db::specs::RuleExampleSpec {
238        id: "minimumcapacitatedspanningtree_to_ilp",
239        build: || {
240            let source = MinimumCapacitatedSpanningTree::new(
241                SimpleGraph::new(4, vec![(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)]),
242                vec![2, 3, 1, 1, 2], // edge weights
243                0,                   // root
244                vec![0, 1, 1, 1],    // requirements
245                2,                   // capacity
246            );
247            crate::example_db::specs::rule_example_via_bounded_ilp::<_>(source)
248        },
249    }]
250}
251
252#[cfg(test)]
253#[path = "../unit_tests/rules/minimumcapacitatedspanningtree_ilp.rs"]
254mod tests;
problemreductions/rules/minimumcapacitatedspanningtree_ilp.rs

problemreductions/rules/
minimumcapacitatedspanningtree_ilp.rs
