problemreductions/rules/
steinertree_ilp.rs

1//! Exact Steiner-tree formulation for signed edge weights.
2//!
3//! Binary vertex selectors and rooted flows connect every selected vertex.
4//! Endpoint linking and |selected edges| = |selected vertices| - 1 then enforce
5//! a tree, independently of the objective's signs.
6
7use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
8use crate::models::graph::SteinerTree;
9use crate::reduction;
10use crate::rules::traits::{ReduceTo, ReductionResult};
11use crate::topology::{Graph, SimpleGraph};
12
13/// Binary layout: m edge selectors, n vertex selectors, then 2m flow arcs
14/// for each vertex other than the first terminal (in vertex-index order).
15#[derive(Debug, Clone)]
16pub struct ReductionSteinerTreeToILP {
17    target: ILP<bool>,
18    num_edges: usize,
19}
20
21impl ReductionResult for ReductionSteinerTreeToILP {
22    type Source = SteinerTree<SimpleGraph, i64>;
23    type Target = ILP<bool>;
24
25    fn target_problem(&self) -> &ILP<bool> {
26        &self.target
27    }
28
29    fn extract_solution(
30        &self,
31        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
32    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
33        crate::rules::traits::validate_target_witness(
34            self.target_problem(),
35            target_solution,
36            |value| value.value.is_some(),
37            "target ILP assignment is infeasible",
38        )?;
39        Ok(target_solution[..self.num_edges]
40            .iter()
41            .map(|&value| value == 1)
42            .collect())
43    }
44}
45
46#[reduction(transform = {
47    exact {
48        num_vars = "num_edges + num_vertices + 2 * num_edges * (num_vertices - 1)",
49        num_constraints = "num_vertices * (num_vertices - 1) + 2 * num_edges * num_vertices + num_terminals + 1",
50    },
51    upper_bound {
52        max_constraint_magnitude_bits = "1",
53        num_nonzeros = "(num_edges + num_vertices + 2 * num_edges * (num_vertices - 1)) * (num_vertices * (num_vertices - 1) + 2 * num_edges * num_vertices + num_terminals + 1)",
54    },
55})]
56impl ReduceTo<ILP<bool>> for SteinerTree<SimpleGraph, i64> {
57    type Result = ReductionSteinerTreeToILP;
58
59    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
60        let n = self.num_vertices();
61        let m = self.num_edges();
62        let (num_vars, num_constraints) = tree_ilp_sizes(n, m, self.terminals().len())?;
63        // The source constructor requires at least one terminal.
64        let root = self.terminals()[0];
65        let edges = self.graph().edges();
66        let vertex_var = |v: usize| m + v;
67        let flow_var = |commodity: usize, edge: usize, dir: usize| {
68            m + n + commodity * (2 * m) + 2 * edge + dir
69        };
70        let mut constraints = Vec::with_capacity(num_constraints);
71
72        for (e, &(u, v)) in edges.iter().enumerate() {
73            for endpoint in [u, v] {
74                constraints.push(LinearConstraint::le(
75                    vec![(e, 1), (vertex_var(endpoint), -1)],
76                    0,
77                ));
78            }
79        }
80        for &terminal in self.terminals() {
81            constraints.push(LinearConstraint::eq(vec![(vertex_var(terminal), 1)], 1));
82        }
83        let cardinality = (0..m)
84            .map(|e| (e, 1))
85            .chain((0..n).map(|v| (vertex_var(v), -1)))
86            .collect();
87        constraints.push(LinearConstraint::eq(cardinality, -1));
88
89        for (commodity, sink) in (0..n).filter(|&v| v != root).enumerate() {
90            for vertex in 0..n {
91                let mut terms = Vec::new();
92                for (edge, &(u, v)) in edges.iter().enumerate() {
93                    if vertex == u {
94                        terms.push((flow_var(commodity, edge, 0), -1));
95                        terms.push((flow_var(commodity, edge, 1), 1));
96                    }
97                    if vertex == v {
98                        terms.push((flow_var(commodity, edge, 0), 1));
99                        terms.push((flow_var(commodity, edge, 1), -1));
100                    }
101                }
102                // Inflow - outflow = z_sink at sink and -z_sink at root.
103                if vertex == root {
104                    terms.push((vertex_var(sink), 1));
105                } else if vertex == sink {
106                    terms.push((vertex_var(sink), -1));
107                }
108                constraints.push(LinearConstraint::eq(terms, 0));
109            }
110            for edge in 0..m {
111                for dir in 0..2 {
112                    constraints.push(LinearConstraint::le(
113                        vec![(flow_var(commodity, edge, dir), 1), (edge, -1)],
114                        0,
115                    ));
116                }
117            }
118        }
119        let objective = self
120            .edge_weights()
121            .iter()
122            .enumerate()
123            .map(|(e, &w)| (e, w))
124            .collect();
125        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize)
126            .map_err(Self::target_construction)?;
127        Ok(ReductionSteinerTreeToILP {
128            target,
129            num_edges: m,
130        })
131    }
132}
133
134/// Bounds for all offsets and allocation sizes; n >= 1 is a source invariant.
135fn tree_ilp_sizes(
136    n: usize,
137    m: usize,
138    k: usize,
139) -> Result<(usize, usize), crate::rules::ReductionError> {
140    let overflow = || {
141        crate::rules::ReductionError::integer_overflow::<SteinerTree<SimpleGraph, i64>, ILP<bool>>(
142            "counting Steiner tree ILP variables and constraints",
143        )
144    };
145    let non_root = n.checked_sub(1).ok_or_else(overflow)?;
146    let arcs = m.checked_mul(2).ok_or_else(overflow)?;
147    let vars = arcs
148        .checked_mul(non_root)
149        .and_then(|x| x.checked_add(m))
150        .and_then(|x| x.checked_add(n))
151        .ok_or_else(overflow)?;
152    let rows = n
153        .checked_mul(non_root)
154        .and_then(|x| arcs.checked_mul(n).and_then(|a| x.checked_add(a)))
155        .and_then(|x| x.checked_add(k))
156        .and_then(|x| x.checked_add(1))
157        .ok_or_else(overflow)?;
158    Ok((vars, rows))
159}
160
161#[cfg(feature = "example-db")]
162pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
163    vec![crate::example_db::specs::RuleExampleSpec {
164        id: "steinertree_to_ilp",
165        build: || {
166            let source = SteinerTree::new(
167                SimpleGraph::new(
168                    5,
169                    vec![(0, 1), (1, 2), (1, 3), (3, 4), (0, 3), (3, 2), (2, 4)],
170                ),
171                vec![2, 2, 1, 1, 5, 5, 6],
172                vec![0, 2, 4],
173            );
174            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
175        },
176    }]
177}
178
179#[cfg(test)]
180#[path = "../unit_tests/rules/steinertree_ilp.rs"]
181mod tests;
problemreductions/rules/steinertree_ilp.rs

problemreductions/rules/
steinertree_ilp.rs
