problemreductions/rules/
biconnectivityaugmentation_ilp.rs

1//! Reduction from BiconnectivityAugmentation to ILP<i32>.
2//!
3//! Select candidate edges under budget and, for every deleted vertex q,
4//! certify that the remaining augmented graph stays connected via unit-flow
5//! commodities from a surviving root to every other surviving vertex.
6
7use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
8use crate::models::graph::BiconnectivityAugmentation;
9use crate::reduction;
10use crate::rules::traits::{ReduceTo, ReductionResult};
11use crate::topology::{Graph, SimpleGraph};
12
13#[derive(Debug, Clone)]
14pub struct ReductionBiconnAugToILP {
15    target: ILP<i32>,
16    num_candidates: usize,
17}
18
19impl ReductionResult for ReductionBiconnAugToILP {
20    type Source = BiconnectivityAugmentation<SimpleGraph, i32>;
21    type Target = ILP<i32>;
22
23    fn target_problem(&self) -> &ILP<i32> {
24        &self.target
25    }
26
27    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
28        target_solution[..self.num_candidates].to_vec()
29    }
30}
31
32#[reduction(
33    overhead = {
34        num_vars = "num_potential_edges + 2 * num_vertices * num_vertices * (num_edges + num_potential_edges)",
35        num_constraints = "1 + 2 * num_vertices * num_vertices * num_potential_edges + num_vertices * num_vertices * num_vertices",
36    }
37)]
38impl ReduceTo<ILP<i32>> for BiconnectivityAugmentation<SimpleGraph, i32> {
39    type Result = ReductionBiconnAugToILP;
40
41    fn reduce_to(&self) -> Self::Result {
42        let n = self.num_vertices();
43        let p = self.num_potential_edges();
44
45        // Trivial case: n ≤ 1 already biconnected
46        if n <= 1 {
47            let target = ILP::new(p, vec![], vec![], ObjectiveSense::Minimize);
48            return ReductionBiconnAugToILP {
49                target,
50                num_candidates: p,
51            };
52        }
53
54        let base_edges = self.graph().edges();
55        let m = base_edges.len();
56
57        // Variable layout:
58        // y_j:                j                                      [0, p)
59        // f^{q,t}_{i,eta}:   p + ((q*n + t)*m + i)*2 + eta          [p, p + 2*m*n^2)
60        // g^{q,t}_{j,eta}:   p + 2*m*n^2 + ((q*n + t)*p + j)*2 + eta  [p + 2*m*n^2, p + 2*n^2*(m+p))
61        let num_vars = p + 2 * n * n * (m + p);
62        let f_idx = |q: usize, t: usize, i: usize, eta: usize| -> usize {
63            p + ((q * n + t) * m + i) * 2 + eta
64        };
65        let g_idx = |q: usize, t: usize, j: usize, eta: usize| -> usize {
66            p + 2 * m * n * n + ((q * n + t) * p + j) * 2 + eta
67        };
68
69        let mut constraints = Vec::new();
70
71        // Binary bounds: y_j ≤ 1
72        for j in 0..p {
73            constraints.push(LinearConstraint::le(vec![(j, 1.0)], 1.0));
74        }
75
76        // Budget constraint: Σ w_j y_j ≤ B
77        let budget_terms: Vec<(usize, f64)> = self
78            .potential_weights()
79            .iter()
80            .enumerate()
81            .map(|(j, &(_, _, w))| (j, w as f64))
82            .collect();
83        constraints.push(LinearConstraint::le(budget_terms, *self.budget() as f64));
84
85        // For each deleted vertex q
86        for q in 0..n {
87            let root = if q != 0 { 0 } else { 1 };
88
89            for t in 0..n {
90                // Pin trivial commodities to zero
91                if t == q || t == root {
92                    for i in 0..m {
93                        for eta in 0..2 {
94                            constraints
95                                .push(LinearConstraint::eq(vec![(f_idx(q, t, i, eta), 1.0)], 0.0));
96                        }
97                    }
98                    for j in 0..p {
99                        for eta in 0..2 {
100                            constraints
101                                .push(LinearConstraint::eq(vec![(g_idx(q, t, j, eta), 1.0)], 0.0));
102                        }
103                    }
104                    continue;
105                }
106
107                // Pin flows on edges incident to deleted vertex q
108                for (i, &(u, v)) in base_edges.iter().enumerate() {
109                    if u == q || v == q {
110                        for eta in 0..2 {
111                            constraints
112                                .push(LinearConstraint::eq(vec![(f_idx(q, t, i, eta), 1.0)], 0.0));
113                        }
114                    }
115                }
116                for (j, &(sj, tj, _)) in self.potential_weights().iter().enumerate() {
117                    if sj == q || tj == q {
118                        for eta in 0..2 {
119                            constraints
120                                .push(LinearConstraint::eq(vec![(g_idx(q, t, j, eta), 1.0)], 0.0));
121                        }
122                    }
123                }
124
125                // Activation: g^{q,t}_{j,eta} ≤ y_j
126                for j in 0..p {
127                    let &(sj, tj, _) = &self.potential_weights()[j];
128                    if sj == q || tj == q {
129                        continue; // already pinned to 0
130                    }
131                    for eta in 0..2 {
132                        constraints.push(LinearConstraint::le(
133                            vec![(g_idx(q, t, j, eta), 1.0), (j, -1.0)],
134                            0.0,
135                        ));
136                    }
137                }
138
139                // Flow conservation for each surviving vertex v ≠ q
140                for v in 0..n {
141                    if v == q {
142                        continue;
143                    }
144                    let mut terms: Vec<(usize, f64)> = Vec::new();
145
146                    // Base edges
147                    for (i, &(u_e, v_e)) in base_edges.iter().enumerate() {
148                        if u_e == q || v_e == q {
149                            continue;
150                        }
151                        // eta=0 means u->v direction
152                        if u_e == v {
153                            terms.push((f_idx(q, t, i, 0), 1.0)); // outgoing
154                            terms.push((f_idx(q, t, i, 1), -1.0)); // incoming
155                        }
156                        if v_e == v {
157                            terms.push((f_idx(q, t, i, 0), -1.0)); // incoming
158                            terms.push((f_idx(q, t, i, 1), 1.0)); // outgoing
159                        }
160                    }
161
162                    // Candidate edges
163                    for (j, &(sj, tj, _)) in self.potential_weights().iter().enumerate() {
164                        if sj == q || tj == q {
165                            continue;
166                        }
167                        // eta=0 means s->t direction
168                        if sj == v {
169                            terms.push((g_idx(q, t, j, 0), 1.0));
170                            terms.push((g_idx(q, t, j, 1), -1.0));
171                        }
172                        if tj == v {
173                            terms.push((g_idx(q, t, j, 0), -1.0));
174                            terms.push((g_idx(q, t, j, 1), 1.0));
175                        }
176                    }
177
178                    let rhs = if v == root {
179                        1.0
180                    } else if v == t {
181                        -1.0
182                    } else {
183                        0.0
184                    };
185                    constraints.push(LinearConstraint::eq(terms, rhs));
186                }
187            }
188        }
189
190        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize);
191        ReductionBiconnAugToILP {
192            target,
193            num_candidates: p,
194        }
195    }
196}
197
198#[cfg(feature = "example-db")]
199pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
200    use crate::export::SolutionPair;
201    vec![crate::example_db::specs::RuleExampleSpec {
202        id: "biconnectivityaugmentation_to_ilp",
203        build: || {
204            // Path 0-1-2-3, candidates: (0,2,1),(0,3,2),(1,3,1), budget=3
205            let source = BiconnectivityAugmentation::new(
206                SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]),
207                vec![(0, 2, 1), (0, 3, 2), (1, 3, 1)],
208                3,
209            );
210            let reduction: ReductionBiconnAugToILP =
211                crate::rules::ReduceTo::<ILP<i32>>::reduce_to(&source);
212            let ilp_sol = crate::solvers::ILPSolver::new()
213                .solve(reduction.target_problem())
214                .expect("ILP should be solvable");
215            let extracted = reduction.extract_solution(&ilp_sol);
216            crate::example_db::specs::rule_example_with_witness::<_, ILP<i32>>(
217                source,
218                SolutionPair {
219                    source_config: extracted,
220                    target_config: ilp_sol,
221                },
222            )
223        },
224    }]
225}
226
227#[cfg(test)]
228#[path = "../unit_tests/rules/biconnectivityaugmentation_ilp.rs"]
229mod tests;
problemreductions/rules/biconnectivityaugmentation_ilp.rs

problemreductions/rules/
biconnectivityaugmentation_ilp.rs
