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 each pair (u,v) with r(u,v) > 0, directed flow variables route 1 unit
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(&self, target_solution: &[usize]) -> Vec<usize> {
37        target_solution[..self.num_edges].to_vec()
38    }
39}
40
41#[reduction(
42    overhead = {
43        num_vars = "num_edges + 2 * num_edges * num_vertices * (num_vertices - 1) / 2",
44        num_constraints = "1 + num_vertices * num_vertices * (num_vertices - 1) / 2 + 2 * num_edges * num_vertices * (num_vertices - 1) / 2",
45    }
46)]
47impl ReduceTo<ILP<bool>> for OptimumCommunicationSpanningTree {
48    type Result = ReductionOptimumCommunicationSpanningTreeToILP;
49
50    fn reduce_to(&self) -> Self::Result {
51        let n = self.num_vertices();
52        let m = self.num_edges();
53        let edges = self.edges();
54        let w = self.edge_weights();
55        let r = self.requirements();
56
57        // Enumerate commodities: all pairs (s, t) with s < t and r(s,t) > 0
58        let mut commodities: Vec<(usize, usize)> = Vec::new();
59        for (s, row) in r.iter().enumerate() {
60            for (t, &req) in row.iter().enumerate().skip(s + 1) {
61                if req > 0 {
62                    commodities.push((s, t));
63                }
64            }
65        }
66        let num_commodities = commodities.len();
67
68        let num_vars = m + 2 * m * num_commodities;
69        let mut constraints = Vec::new();
70
71        // Edge variable index
72        let edge_var = |edge_idx: usize| edge_idx;
73
74        // Flow variable index: for commodity k, edge e, direction dir (0 = i->j, 1 = j->i)
75        let flow_var =
76            |k: usize, edge_idx: usize, dir: usize| -> usize { m + k * 2 * m + 2 * edge_idx + dir };
77
78        // Constraint 1: Tree has exactly n-1 edges
79        // sum x_e = n-1
80        let tree_terms: Vec<(usize, f64)> = (0..m).map(|e| (edge_var(e), 1.0)).collect();
81        constraints.push(LinearConstraint::eq(tree_terms, (n - 1) as f64));
82
83        // Constraint 2: Flow conservation for each commodity
84        for (k, &(src, dst)) in commodities.iter().enumerate() {
85            for vertex in 0..n {
86                let mut terms = Vec::new();
87                for (edge_idx, &(i, j)) in edges.iter().enumerate() {
88                    // Flow into vertex minus flow out of vertex
89                    if j == vertex {
90                        // Edge (i, j): direction 0 = i->j (inflow), direction 1 = j->i (outflow)
91                        terms.push((flow_var(k, edge_idx, 0), 1.0));
92                        terms.push((flow_var(k, edge_idx, 1), -1.0));
93                    }
94                    if i == vertex {
95                        // Edge (i, j): direction 1 = j->i (inflow), direction 0 = i->j (outflow)
96                        terms.push((flow_var(k, edge_idx, 1), 1.0));
97                        terms.push((flow_var(k, edge_idx, 0), -1.0));
98                    }
99                }
100
101                let rhs = if vertex == src {
102                    -1.0 // source: net outflow of 1
103                } else if vertex == dst {
104                    1.0 // sink: net inflow of 1
105                } else {
106                    0.0 // transit: balanced
107                };
108                constraints.push(LinearConstraint::eq(terms, rhs));
109            }
110        }
111
112        // Constraint 3: Capacity linking: flow <= edge selector
113        for k in 0..num_commodities {
114            for edge_idx in 0..m {
115                let sel = edge_var(edge_idx);
116                // f^k_(i->j) <= x_e
117                constraints.push(LinearConstraint::le(
118                    vec![(flow_var(k, edge_idx, 0), 1.0), (sel, -1.0)],
119                    0.0,
120                ));
121                // f^k_(j->i) <= x_e
122                constraints.push(LinearConstraint::le(
123                    vec![(flow_var(k, edge_idx, 1), 1.0), (sel, -1.0)],
124                    0.0,
125                ));
126            }
127        }
128
129        // Objective: minimize sum over commodities k of r(s,t) * sum_e w(e) * (f^k_e_fwd + f^k_e_bwd)
130        // This equals sum_{s<t} r(s,t) * W_T(s,t) because flow routes exactly along the tree path.
131        let mut objective: Vec<(usize, f64)> = Vec::new();
132        for (k, &(s, t)) in commodities.iter().enumerate() {
133            let req = r[s][t] as f64;
134            for (edge_idx, &(i, j)) in edges.iter().enumerate() {
135                let weight = w[i][j] as f64;
136                let coeff = req * weight;
137                if coeff != 0.0 {
138                    objective.push((flow_var(k, edge_idx, 0), coeff));
139                    objective.push((flow_var(k, edge_idx, 1), coeff));
140                }
141            }
142        }
143
144        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize);
145
146        ReductionOptimumCommunicationSpanningTreeToILP {
147            target,
148            num_edges: m,
149        }
150    }
151}
152
153#[cfg(feature = "example-db")]
154pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
155    vec![crate::example_db::specs::RuleExampleSpec {
156        id: "optimum_communication_spanning_tree_to_ilp",
157        build: || {
158            // K3 example from issue #967
159            let edge_weights = vec![vec![0, 1, 2], vec![1, 0, 3], vec![2, 3, 0]];
160            let requirements = vec![vec![0, 1, 1], vec![1, 0, 1], vec![1, 1, 0]];
161            let source = OptimumCommunicationSpanningTree::new(edge_weights, requirements);
162            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
163        },
164    }]
165}
166
167#[cfg(test)]
168#[path = "../unit_tests/rules/optimumcommunicationspanningtree_ilp.rs"]
169mod tests;
problemreductions/rules/optimumcommunicationspanningtree_ilp.rs

problemreductions/rules/
optimumcommunicationspanningtree_ilp.rs
