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(transform = {
50    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    upper_bound {
55        max_constraint_magnitude_bits = "num_vertices + 1",
56        num_nonzeros = "(num_edges + 2 * num_edges * num_vertices * (num_vertices - 1) / 2) * (1 + num_vertices * num_vertices * (num_vertices - 1) / 2 + 2 * num_edges * num_vertices * (num_vertices - 1) / 2)",
57    },
58})]
59impl ReduceTo<ILP<bool>> for OptimumCommunicationSpanningTree {
60    type Result = ReductionOptimumCommunicationSpanningTreeToILP;
61
62    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
63        let n = self.num_vertices();
64        let m = self.num_edges();
65        let edges = self.edges();
66        let w = self.edge_weights();
67        let r = self.requirements();
68
69        // Enumerate every pair: zero-requirement commodities still enforce spanning connectivity.
70        let mut commodities: Vec<(usize, usize)> = Vec::new();
71        for s in 0..n {
72            for t in (s + 1)..n {
73                commodities.push((s, t));
74            }
75        }
76        let num_commodities = commodities.len();
77
78        let num_vars = m + 2 * m * num_commodities;
79        let mut constraints = Vec::new();
80
81        // Edge variable index
82        let edge_var = |edge_idx: usize| edge_idx;
83
84        // Flow variable index: for commodity k, edge e, direction dir (0 = i->j, 1 = j->i)
85        let flow_var =
86            |k: usize, edge_idx: usize, dir: usize| -> usize { m + k * 2 * m + 2 * edge_idx + dir };
87
88        // Constraint 1: Tree has exactly n-1 edges
89        // sum x_e = n-1
90        let tree_terms: Vec<(usize, i64)> = (0..m).map(|e| (edge_var(e), 1)).collect();
91        constraints.push(LinearConstraint::eq(
92            tree_terms,
93            Self::exact_i64(n, "encoding the spanning-tree order")? - 1,
94        ));
95
96        // Constraint 2: Flow conservation for each commodity
97        for (k, &(src, dst)) in commodities.iter().enumerate() {
98            for vertex in 0..n {
99                let mut terms = Vec::new();
100                for (edge_idx, &(i, j)) in edges.iter().enumerate() {
101                    // Flow into vertex minus flow out of vertex
102                    if j == vertex {
103                        // Edge (i, j): direction 0 = i->j (inflow), direction 1 = j->i (outflow)
104                        terms.push((flow_var(k, edge_idx, 0), 1));
105                        terms.push((flow_var(k, edge_idx, 1), -1));
106                    }
107                    if i == vertex {
108                        // Edge (i, j): direction 1 = j->i (inflow), direction 0 = i->j (outflow)
109                        terms.push((flow_var(k, edge_idx, 1), 1));
110                        terms.push((flow_var(k, edge_idx, 0), -1));
111                    }
112                }
113
114                let rhs = if vertex == src {
115                    -1 // source: net outflow of 1
116                } else if vertex == dst {
117                    1 // sink: net inflow of 1
118                } else {
119                    0 // transit: balanced
120                };
121                constraints.push(LinearConstraint::eq(terms, rhs));
122            }
123        }
124
125        // Constraint 3: Capacity linking: flow <= edge selector
126        for k in 0..num_commodities {
127            for edge_idx in 0..m {
128                let sel = edge_var(edge_idx);
129                // f^k_(i->j) <= x_e
130                constraints.push(LinearConstraint::le(
131                    vec![(flow_var(k, edge_idx, 0), 1), (sel, -1)],
132                    0,
133                ));
134                // f^k_(j->i) <= x_e
135                constraints.push(LinearConstraint::le(
136                    vec![(flow_var(k, edge_idx, 1), 1), (sel, -1)],
137                    0,
138                ));
139            }
140        }
141
142        // Objective: minimize sum over commodities k of r(s,t) * sum_e w(e) * (f^k_e_fwd + f^k_e_bwd)
143        // This equals sum_{s<t} r(s,t) * W_T(s,t) because flow routes exactly along the tree path.
144        let mut objective: Vec<(usize, i64)> = Vec::new();
145        for (k, &(s, t)) in commodities.iter().enumerate() {
146            for (edge_idx, &(i, j)) in edges.iter().enumerate() {
147                let communication_cost = r[s][t].checked_mul(w[i][j]).ok_or_else(|| {
148                    crate::rules::ReductionError::integer_overflow::<
149                        OptimumCommunicationSpanningTree,
150                        ILP<bool>,
151                    >(
152                        "multiplying a communication requirement by an edge weight"
153                    )
154                })?;
155                let coeff = communication_cost;
156                if coeff != 0 {
157                    objective.push((flow_var(k, edge_idx, 0), coeff));
158                    objective.push((flow_var(k, edge_idx, 1), coeff));
159                }
160            }
161        }
162
163        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
164            .map_err(Self::target_construction)?;
165
166        Ok(ReductionOptimumCommunicationSpanningTreeToILP {
167            target,
168            num_edges: m,
169        })
170    }
171}
172
173#[cfg(feature = "example-db")]
174pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
175    vec![crate::example_db::specs::RuleExampleSpec {
176        id: "optimum_communication_spanning_tree_to_ilp",
177        build: || {
178            // K3 example from issue #967
179            let edge_weights = vec![vec![0, 1, 2], vec![1, 0, 3], vec![2, 3, 0]];
180            let requirements = vec![vec![0, 1, 1], vec![1, 0, 1], vec![1, 1, 0]];
181            let source = OptimumCommunicationSpanningTree::new(edge_weights, requirements);
182            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
183        },
184    }]
185}
186
187#[cfg(test)]
188#[path = "../unit_tests/rules/optimumcommunicationspanningtree_ilp.rs"]
189mod tests;
problemreductions/rules/optimumcommunicationspanningtree_ilp.rs

problemreductions/rules/
optimumcommunicationspanningtree_ilp.rs
