problemreductions/rules/
steinertree_ilp.rs

1//! Reduction from SteinerTree to ILP (Integer Linear Programming).
2//!
3//! Uses the standard rooted multi-commodity flow formulation:
4//! - Variables: edge selectors `y_e` plus directed flow variables `f^t_(u,v)`
5//!   for each non-root terminal `t`
6//! - Constraints: flow conservation for each commodity and capacity linking
7//!   `f^t_(u,v) <= y_e`
8//! - Objective: minimize the total weight of selected edges
9
10use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
11use crate::models::graph::SteinerTree;
12use crate::reduction;
13use crate::rules::traits::{ReduceTo, ReductionResult};
14use crate::topology::{Graph, SimpleGraph};
15
16/// Result of reducing SteinerTree to ILP.
17///
18/// Variable layout (all binary):
19/// - `y_e` for each undirected source edge `e` (indices `0..m`)
20/// - `f^t_(u,v)` and `f^t_(v,u)` for each non-root terminal `t` and each source edge
21///   `(u, v)` (indices `m..m + 2m(k-1)`)
22#[derive(Debug, Clone)]
23pub struct ReductionSteinerTreeToILP {
24    target: ILP<bool>,
25    num_edges: usize,
26}
27
28impl ReductionResult for ReductionSteinerTreeToILP {
29    type Source = SteinerTree<SimpleGraph, i32>;
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_terminals - 1)",
44        num_constraints = "num_vertices * (num_terminals - 1) + 2 * num_edges * (num_terminals - 1)",
45    }
46)]
47impl ReduceTo<ILP<bool>> for SteinerTree<SimpleGraph, i32> {
48    type Result = ReductionSteinerTreeToILP;
49
50    fn reduce_to(&self) -> Self::Result {
51        assert!(
52            self.edge_weights().iter().all(|&weight| weight > 0),
53            "SteinerTree -> ILP requires strictly positive edge weights (zero-weight edges should be contracted beforehand)"
54        );
55
56        let n = self.num_vertices();
57        let m = self.num_edges();
58        let root = self.terminals()[0];
59        let non_root_terminals = &self.terminals()[1..];
60        let edges = self.graph().edges();
61        let num_vars = m + 2 * m * non_root_terminals.len();
62        let num_constraints = n * non_root_terminals.len() + 2 * m * non_root_terminals.len();
63        let mut constraints = Vec::with_capacity(num_constraints);
64
65        let edge_var = |edge_idx: usize| edge_idx;
66        let flow_var = |terminal_pos: usize, edge_idx: usize, dir: usize| -> usize {
67            m + terminal_pos * 2 * m + 2 * edge_idx + dir
68        };
69
70        for (terminal_pos, &terminal) in non_root_terminals.iter().enumerate() {
71            for vertex in 0..n {
72                let mut terms = Vec::new();
73                for (edge_idx, &(u, v)) in edges.iter().enumerate() {
74                    if v == vertex {
75                        terms.push((flow_var(terminal_pos, edge_idx, 0), 1.0));
76                        terms.push((flow_var(terminal_pos, edge_idx, 1), -1.0));
77                    }
78                    if u == vertex {
79                        terms.push((flow_var(terminal_pos, edge_idx, 0), -1.0));
80                        terms.push((flow_var(terminal_pos, edge_idx, 1), 1.0));
81                    }
82                }
83
84                let rhs = if vertex == root {
85                    -1.0
86                } else if vertex == terminal {
87                    1.0
88                } else {
89                    0.0
90                };
91                constraints.push(LinearConstraint::eq(terms, rhs));
92            }
93        }
94
95        for terminal_pos in 0..non_root_terminals.len() {
96            for edge_idx in 0..m {
97                let selector = edge_var(edge_idx);
98                constraints.push(LinearConstraint::le(
99                    vec![(flow_var(terminal_pos, edge_idx, 0), 1.0), (selector, -1.0)],
100                    0.0,
101                ));
102                constraints.push(LinearConstraint::le(
103                    vec![(flow_var(terminal_pos, edge_idx, 1), 1.0), (selector, -1.0)],
104                    0.0,
105                ));
106            }
107        }
108
109        let objective: Vec<(usize, f64)> = self
110            .edge_weights()
111            .iter()
112            .enumerate()
113            .map(|(edge_idx, &weight)| (edge_var(edge_idx), weight as f64))
114            .collect();
115
116        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize);
117
118        ReductionSteinerTreeToILP {
119            target,
120            num_edges: m,
121        }
122    }
123}
124
125#[cfg(feature = "example-db")]
126pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
127    vec![crate::example_db::specs::RuleExampleSpec {
128        id: "steinertree_to_ilp",
129        build: || {
130            let source = SteinerTree::new(
131                SimpleGraph::new(
132                    5,
133                    vec![(0, 1), (1, 2), (1, 3), (3, 4), (0, 3), (3, 2), (2, 4)],
134                ),
135                vec![2, 2, 1, 1, 5, 5, 6],
136                vec![0, 2, 4],
137            );
138            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
139        },
140    }]
141}
142
143#[cfg(test)]
144#[path = "../unit_tests/rules/steinertree_ilp.rs"]
145mod tests;
problemreductions/rules/steinertree_ilp.rs

problemreductions/rules/
steinertree_ilp.rs
