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, i64>;
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_terminals - 1)",
52        num_constraints = "num_vertices * (num_terminals - 1) + 2 * num_edges * (num_terminals - 1)",
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 SteinerTreeInGraphs<SimpleGraph, i64> {
59    type Result = ReductionSTIGToILP;
60
61    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
62        if self.weights().iter().any(|&weight| weight <= 0) {
63            return Err(crate::rules::ReductionError::invalid_target::<
64                SteinerTreeInGraphs<SimpleGraph, i64>,
65                ILP<bool>,
66            >(
67                "ILP construction requires strictly positive edge weights"
68            ));
69        }
70
71        let n = self.num_vertices();
72        let m = self.num_edges();
73        let root = *self.terminals().first().ok_or_else(|| {
74            crate::rules::ReductionError::invalid_target::<
75                SteinerTreeInGraphs<SimpleGraph, i64>,
76                ILP<bool>,
77            >("source must contain at least one terminal")
78        })?;
79        let non_root_terminals = &self.terminals()[1..];
80        let edges = self.graph().edges();
81        let num_vars = m + 2 * m * non_root_terminals.len();
82        let mut constraints = Vec::new();
83
84        let edge_var = |edge_idx: usize| edge_idx;
85        let flow_var = |terminal_pos: usize, edge_idx: usize, dir: usize| -> usize {
86            m + terminal_pos * 2 * m + 2 * edge_idx + dir
87        };
88
89        // Flow conservation for each non-root terminal commodity
90        for (terminal_pos, &terminal) in non_root_terminals.iter().enumerate() {
91            for vertex in 0..n {
92                let mut terms = Vec::new();
93                for (edge_idx, &(u, v)) in edges.iter().enumerate() {
94                    if v == vertex {
95                        terms.push((flow_var(terminal_pos, edge_idx, 0), 1));
96                        terms.push((flow_var(terminal_pos, edge_idx, 1), -1));
97                    }
98                    if u == vertex {
99                        terms.push((flow_var(terminal_pos, edge_idx, 0), -1));
100                        terms.push((flow_var(terminal_pos, edge_idx, 1), 1));
101                    }
102                }
103
104                let rhs = if vertex == root {
105                    -1
106                } else if vertex == terminal {
107                    1
108                } else {
109                    0
110                };
111                constraints.push(LinearConstraint::eq(terms, rhs));
112            }
113        }
114
115        // Capacity linking: f^t_{e,dir} <= y_e
116        for terminal_pos in 0..non_root_terminals.len() {
117            for edge_idx in 0..m {
118                let selector = edge_var(edge_idx);
119                constraints.push(LinearConstraint::le(
120                    vec![(flow_var(terminal_pos, edge_idx, 0), 1), (selector, -1)],
121                    0,
122                ));
123                constraints.push(LinearConstraint::le(
124                    vec![(flow_var(terminal_pos, edge_idx, 1), 1), (selector, -1)],
125                    0,
126                ));
127            }
128        }
129
130        // Objective: minimize total weight
131        let edge_weights = self.weights();
132        let objective: Vec<(usize, i64)> = edge_weights
133            .iter()
134            .enumerate()
135            .map(|(edge_idx, weight)| (edge_var(edge_idx), weight.to_sum()))
136            .collect();
137
138        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
139            .map_err(Self::target_construction)?;
140
141        Ok(ReductionSTIGToILP {
142            target,
143            num_edges: m,
144        })
145    }
146}
147
148#[cfg(feature = "example-db")]
149pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
150    vec![crate::example_db::specs::RuleExampleSpec {
151        id: "steinertreeingraphs_to_ilp",
152        build: || {
153            // 4 vertices, 4 edges, 2 terminals
154            // ILP: 4 + 2*4*1 = 12 binary variables = 4096 configs
155            let source = SteinerTreeInGraphs::new(
156                SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3), (0, 3)]),
157                vec![0, 2],
158                vec![1, 1, 1, 3],
159            );
160            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
161        },
162    }]
163}
164
165#[cfg(test)]
166#[path = "../unit_tests/rules/steinertreeingraphs_ilp.rs"]
167mod tests;
problemreductions/rules/steinertreeingraphs_ilp.rs

problemreductions/rules/
steinertreeingraphs_ilp.rs
