problemreductions/rules/
optimumcommunicationspanningtree_ilp.rs

1//! Reduction from OptimumCommunicationSpanningTree to ILP (Integer Linear Programming).
2//!
3//! Uses a multi-commodity flow formulation:
4//! - Binary edge variables x_e for each edge of K_n
5//! - For every vertex pair (u,v), directed flow variables route 1 unit, proving connectivity
6//!   from u to v through the tree
7//! - Tree constraints: sum x_e = n-1, and connectivity via flow conservation
8//! - Objective: minimize sum_{(u,v): r>0} r(u,v) * w(e) * (flow_uv(e->dir) + flow_uv(e<-dir))
9
10use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
11use crate::models::misc::OptimumCommunicationSpanningTree;
12use crate::reduction;
13use crate::rules::traits::{ReduceTo, ReductionResult};
14
15/// Result of reducing OptimumCommunicationSpanningTree to ILP.
16///
17/// Variable layout (all binary):
18/// - `x_e` for each undirected edge `e` (indices `0..m`)
19/// - For each commodity `k` (pair (u,v) with u < v and r(u,v) > 0):
20///   `f^k_(i,j)` and `f^k_(j,i)` for each edge (i,j), two directed flow variables
21///   (indices `m + k * 2m .. m + (k+1) * 2m`)
22#[derive(Debug, Clone)]
23pub struct ReductionOptimumCommunicationSpanningTreeToILP {
24    target: ILP<bool>,
25    num_edges: usize,
26}
27
28impl ReductionResult for ReductionOptimumCommunicationSpanningTreeToILP {
29    type Source = OptimumCommunicationSpanningTree;
30    type Target = ILP<bool>;
31
32    fn target_problem(&self) -> &ILP<bool> {
33        &self.target
34    }
35
36    fn extract_solution(
37        &self,
38        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
39    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
40        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
41
42        Ok(target_solution[..self.num_edges]
43            .iter()
44            .map(|&value| value == 1)
45            .collect())
46    }
47}
48
49#[reduction(
50    transform = exact {
51        num_vars = "num_edges + 2 * num_edges * num_vertices * (num_vertices - 1) / 2",
52        num_constraints = "1 + num_vertices * num_vertices * (num_vertices - 1) / 2 + 2 * num_edges * num_vertices * (num_vertices - 1) / 2",
53    },
54    unavailable = {
55        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
56    }
57)]
58impl ReduceTo<ILP<bool>> for OptimumCommunicationSpanningTree {
59    type Result = ReductionOptimumCommunicationSpanningTreeToILP;
60
61    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
62        let n = self.num_vertices();
63        let m = self.num_edges();
64        let edges = self.edges();
65        let w = self.edge_weights();
66        let r = self.requirements();
67
68        // Enumerate every pair: zero-requirement commodities still enforce spanning connectivity.
69        let mut commodities: Vec<(usize, usize)> = Vec::new();
70        for s in 0..n {
71            for t in (s + 1)..n {
72                commodities.push((s, t));
73            }
74        }
75        let num_commodities = commodities.len();
76
77        let num_vars = m + 2 * m * num_commodities;
78        let mut constraints = Vec::new();
79
80        // Edge variable index
81        let edge_var = |edge_idx: usize| edge_idx;
82
83        // Flow variable index: for commodity k, edge e, direction dir (0 = i->j, 1 = j->i)
84        let flow_var =
85            |k: usize, edge_idx: usize, dir: usize| -> usize { m + k * 2 * m + 2 * edge_idx + dir };
86
87        // Constraint 1: Tree has exactly n-1 edges
88        // sum x_e = n-1
89        let tree_terms: Vec<(usize, i64)> = (0..m).map(|e| (edge_var(e), 1)).collect();
90        constraints.push(LinearConstraint::eq(
91            tree_terms,
92            Self::exact_i64(n, "encoding the spanning-tree order")? - 1,
93        ));
94
95        // Constraint 2: Flow conservation for each commodity
96        for (k, &(src, dst)) in commodities.iter().enumerate() {
97            for vertex in 0..n {
98                let mut terms = Vec::new();
99                for (edge_idx, &(i, j)) in edges.iter().enumerate() {
100                    // Flow into vertex minus flow out of vertex
101                    if j == vertex {
102                        // Edge (i, j): direction 0 = i->j (inflow), direction 1 = j->i (outflow)
103                        terms.push((flow_var(k, edge_idx, 0), 1));
104                        terms.push((flow_var(k, edge_idx, 1), -1));
105                    }
106                    if i == vertex {
107                        // Edge (i, j): direction 1 = j->i (inflow), direction 0 = i->j (outflow)
108                        terms.push((flow_var(k, edge_idx, 1), 1));
109                        terms.push((flow_var(k, edge_idx, 0), -1));
110                    }
111                }
112
113                let rhs = if vertex == src {
114                    -1 // source: net outflow of 1
115                } else if vertex == dst {
116                    1 // sink: net inflow of 1
117                } else {
118                    0 // transit: balanced
119                };
120                constraints.push(LinearConstraint::eq(terms, rhs));
121            }
122        }
123
124        // Constraint 3: Capacity linking: flow <= edge selector
125        for k in 0..num_commodities {
126            for edge_idx in 0..m {
127                let sel = edge_var(edge_idx);
128                // f^k_(i->j) <= x_e
129                constraints.push(LinearConstraint::le(
130                    vec![(flow_var(k, edge_idx, 0), 1), (sel, -1)],
131                    0,
132                ));
133                // f^k_(j->i) <= x_e
134                constraints.push(LinearConstraint::le(
135                    vec![(flow_var(k, edge_idx, 1), 1), (sel, -1)],
136                    0,
137                ));
138            }
139        }
140
141        // Objective: minimize sum over commodities k of r(s,t) * sum_e w(e) * (f^k_e_fwd + f^k_e_bwd)
142        // This equals sum_{s<t} r(s,t) * W_T(s,t) because flow routes exactly along the tree path.
143        let mut objective: Vec<(usize, i64)> = Vec::new();
144        for (k, &(s, t)) in commodities.iter().enumerate() {
145            for (edge_idx, &(i, j)) in edges.iter().enumerate() {
146                let communication_cost = r[s][t].checked_mul(w[i][j]).ok_or_else(|| {
147                    crate::rules::ReductionError::integer_overflow::<
148                        OptimumCommunicationSpanningTree,
149                        ILP<bool>,
150                    >(
151                        "multiplying a communication requirement by an edge weight"
152                    )
153                })?;
154                let coeff = communication_cost;
155                if coeff != 0 {
156                    objective.push((flow_var(k, edge_idx, 0), coeff));
157                    objective.push((flow_var(k, edge_idx, 1), coeff));
158                }
159            }
160        }
161
162        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
163            .map_err(Self::target_construction)?;
164
165        Ok(ReductionOptimumCommunicationSpanningTreeToILP {
166            target,
167            num_edges: m,
168        })
169    }
170}
171
172#[cfg(feature = "example-db")]
173pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
174    vec![crate::example_db::specs::RuleExampleSpec {
175        id: "optimum_communication_spanning_tree_to_ilp",
176        build: || {
177            // K3 example from issue #967
178            let edge_weights = vec![vec![0, 1, 2], vec![1, 0, 3], vec![2, 3, 0]];
179            let requirements = vec![vec![0, 1, 1], vec![1, 0, 1], vec![1, 1, 0]];
180            let source = OptimumCommunicationSpanningTree::new(edge_weights, requirements);
181            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
182        },
183    }]
184}
185
186#[cfg(test)]
187#[path = "../unit_tests/rules/optimumcommunicationspanningtree_ilp.rs"]
188mod tests;
problemreductions/rules/optimumcommunicationspanningtree_ilp.rs

problemreductions/rules/
optimumcommunicationspanningtree_ilp.rs
