problemreductions/rules/
steinertreeingraphs_ilp.rs

1//! Reduction from SteinerTreeInGraphs to ILP (Integer Linear Programming).
2//!
3//! Uses the rooted multi-commodity flow formulation:
4//! - Variables: binary edge selectors `y_e` plus binary directed flow variables
5//!   `f^t_(u,v)` for each non-root terminal `t`
6//! - Constraints: flow conservation and capacity linking `f^t_(u,v) <= y_e`
7//! - Objective: minimize total weight of selected edges
8
9use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
10use crate::models::graph::SteinerTreeInGraphs;
11use crate::reduction;
12use crate::rules::traits::{ReduceTo, ReductionResult};
13use crate::topology::{Graph, SimpleGraph};
14use crate::types::WeightElement;
15
16/// Result of reducing SteinerTreeInGraphs 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 edge
21///   (indices `m..m + 2m(k-1)`)
22#[derive(Debug, Clone)]
23pub struct ReductionSTIGToILP {
24    target: ILP<bool>,
25    num_edges: usize,
26}
27
28impl ReductionResult for ReductionSTIGToILP {
29    type Source = SteinerTreeInGraphs<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 SteinerTreeInGraphs<SimpleGraph, i32> {
48    type Result = ReductionSTIGToILP;
49
50    fn reduce_to(&self) -> Self::Result {
51        assert!(
52            self.weights().iter().all(|&w| w > 0),
53            "SteinerTreeInGraphs -> ILP requires strictly positive edge weights"
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 mut constraints = Vec::new();
63
64        let edge_var = |edge_idx: usize| edge_idx;
65        let flow_var = |terminal_pos: usize, edge_idx: usize, dir: usize| -> usize {
66            m + terminal_pos * 2 * m + 2 * edge_idx + dir
67        };
68
69        // Flow conservation for each non-root terminal commodity
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        // Capacity linking: f^t_{e,dir} <= y_e
96        for terminal_pos in 0..non_root_terminals.len() {
97            for edge_idx in 0..m {
98                let selector = edge_var(edge_idx);
99                constraints.push(LinearConstraint::le(
100                    vec![(flow_var(terminal_pos, edge_idx, 0), 1.0), (selector, -1.0)],
101                    0.0,
102                ));
103                constraints.push(LinearConstraint::le(
104                    vec![(flow_var(terminal_pos, edge_idx, 1), 1.0), (selector, -1.0)],
105                    0.0,
106                ));
107            }
108        }
109
110        // Objective: minimize total weight
111        let edge_weights = self.weights();
112        let objective: Vec<(usize, f64)> = edge_weights
113            .iter()
114            .enumerate()
115            .map(|(edge_idx, w)| (edge_var(edge_idx), w.to_sum() as f64))
116            .collect();
117
118        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize);
119
120        ReductionSTIGToILP {
121            target,
122            num_edges: m,
123        }
124    }
125}
126
127#[cfg(feature = "example-db")]
128pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
129    vec![crate::example_db::specs::RuleExampleSpec {
130        id: "steinertreeingraphs_to_ilp",
131        build: || {
132            // 4 vertices, 4 edges, 2 terminals
133            // ILP: 4 + 2*4*1 = 12 binary variables = 4096 configs
134            let source = SteinerTreeInGraphs::new(
135                SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3), (0, 3)]),
136                vec![0, 2],
137                vec![1, 1, 1, 3],
138            );
139            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
140        },
141    }]
142}
143
144#[cfg(test)]
145#[path = "../unit_tests/rules/steinertreeingraphs_ilp.rs"]
146mod tests;
problemreductions/rules/steinertreeingraphs_ilp.rs

problemreductions/rules/
steinertreeingraphs_ilp.rs
