problemreductions/rules/
biconnectivityaugmentation_ilp.rs

1//! Reduction from BiconnectivityAugmentation to `ILP<bool>`.
2//!
3//! Select candidate edges under budget and, both before deletion 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<bool>,
16    num_candidates: usize,
17}
18
19impl ReductionBiconnAugToILP {
20    fn dimensions(
21        n: usize,
22        m: usize,
23        p: usize,
24    ) -> Result<(usize, usize), crate::rules::ReductionError> {
25        let overflow = || {
26            crate::rules::ReductionError::integer_overflow::<
27                BiconnectivityAugmentation<SimpleGraph, i64>,
28                ILP<bool>,
29            >("computing connectivity flow variable counts")
30        };
31        let commodities = n
32            .checked_add(1)
33            .and_then(|x| x.checked_mul(n))
34            .ok_or_else(overflow)?;
35        let base_variables = commodities
36            .checked_mul(m)
37            .and_then(|x| x.checked_mul(2))
38            .ok_or_else(overflow)?;
39        let candidate_start = p.checked_add(base_variables).ok_or_else(overflow)?;
40        let num_variables = commodities
41            .checked_mul(p)
42            .and_then(|x| x.checked_mul(2))
43            .and_then(|x| x.checked_add(candidate_start))
44            .ok_or_else(overflow)?;
45        Ok((candidate_start, num_variables))
46    }
47}
48
49impl ReductionResult for ReductionBiconnAugToILP {
50    type Source = BiconnectivityAugmentation<SimpleGraph, i64>;
51    type Target = ILP<bool>;
52
53    fn target_problem(&self) -> &ILP<bool> {
54        &self.target
55    }
56
57    fn extract_solution(
58        &self,
59        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
60    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
61        crate::rules::traits::validate_target_witness(
62            self.target_problem(),
63            target_solution,
64            |value| value.value.is_some(),
65            "target ILP assignment is infeasible",
66        )?;
67
68        Ok(target_solution[..self.num_candidates]
69            .iter()
70            .map(|&value| value == 1)
71            .collect())
72    }
73}
74
75#[crate::aggregate_reduction(ilp_feasibility)]
76impl crate::rules::AggregateReductionResult for ReductionBiconnAugToILP {}
77
78// Budget uses at most p terms. Each of n(n+1) commodities contributes at most
79// 4m base-flow terms and 8p candidate-flow/activation terms. Deleted-edge pins
80// replace those terms; trivial commodities and normalization only reduce them.
81#[reduction(transform = {
82    exact {
83        max_constraint_magnitude_bits = "max_numeric_magnitude_bits",
84    },
85    upper_bound {
86        num_vars = "num_potential_edges + 2 * num_vertices * (num_vertices + 1) * (num_edges + num_potential_edges)",
87        num_constraints = "1 + num_vertices * (num_vertices + 1) * (2 * num_edges + 4 * num_potential_edges + num_vertices)",
88        num_nonzeros = "num_potential_edges + num_vertices * (num_vertices + 1) * (4 * num_edges + 8 * num_potential_edges)",
89    },
90})]
91impl ReduceTo<ILP<bool>> for BiconnectivityAugmentation<SimpleGraph, i64> {
92    type Result = ReductionBiconnAugToILP;
93
94    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
95        let n = self.num_vertices();
96        let p = self.num_potential_edges();
97
98        let base_edges = self.graph().edges();
99        let m = base_edges.len();
100
101        // q = n certifies the original graph; q < n deletes that vertex.
102        // y_j occupies [0,p), followed by all base-edge and candidate-edge flows.
103        let (candidate_start, num_vars) = ReductionBiconnAugToILP::dimensions(n, m, p)?;
104        let f_idx = |q: usize, t: usize, i: usize, eta: usize| -> usize {
105            p + ((q * n + t) * m + i) * 2 + eta
106        };
107        let g_idx = |q: usize, t: usize, j: usize, eta: usize| -> usize {
108            candidate_start + ((q * n + t) * p + j) * 2 + eta
109        };
110        let mut constraints = Vec::new();
111
112        // Budget constraint: Σ w_j y_j ≤ B
113        let budget_terms: Vec<(usize, i64)> = self
114            .potential_weights()
115            .iter()
116            .enumerate()
117            .map(|(candidate, &(_, _, weight))| (candidate, weight))
118            .collect();
119        constraints.push(LinearConstraint::le(budget_terms, *self.budget()));
120
121        // Include q = n: no endpoint equals n, so no vertex or edge is deleted.
122        for q in 0..=n {
123            let root = if q != 0 { 0 } else { 1 };
124
125            for t in 0..n {
126                // Pin trivial commodities to zero
127                if t == q || t == root {
128                    for i in 0..m {
129                        for eta in 0..2 {
130                            constraints
131                                .push(LinearConstraint::eq(vec![(f_idx(q, t, i, eta), 1)], 0));
132                        }
133                    }
134                    for j in 0..p {
135                        for eta in 0..2 {
136                            constraints
137                                .push(LinearConstraint::eq(vec![(g_idx(q, t, j, eta), 1)], 0));
138                        }
139                    }
140                    continue;
141                }
142
143                // Pin flows on edges incident to deleted vertex q
144                for (i, &(u, v)) in base_edges.iter().enumerate() {
145                    if u == q || v == q {
146                        for eta in 0..2 {
147                            constraints
148                                .push(LinearConstraint::eq(vec![(f_idx(q, t, i, eta), 1)], 0));
149                        }
150                    }
151                }
152                for (j, &(sj, tj, _)) in self.potential_weights().iter().enumerate() {
153                    if sj == q || tj == q {
154                        for eta in 0..2 {
155                            constraints
156                                .push(LinearConstraint::eq(vec![(g_idx(q, t, j, eta), 1)], 0));
157                        }
158                    }
159                }
160
161                // Activation: g^{q,t}_{j,eta} ≤ y_j
162                for j in 0..p {
163                    let &(sj, tj, _) = &self.potential_weights()[j];
164                    if sj == q || tj == q {
165                        continue; // already pinned to 0
166                    }
167                    for eta in 0..2 {
168                        constraints.push(LinearConstraint::le(
169                            vec![(g_idx(q, t, j, eta), 1), (j, -1)],
170                            0,
171                        ));
172                    }
173                }
174
175                // Flow conservation for each surviving vertex v ≠ q
176                for v in 0..n {
177                    if v == q {
178                        continue;
179                    }
180                    let mut terms: Vec<(usize, i64)> = Vec::new();
181
182                    // Base edges
183                    for (i, &(u_e, v_e)) in base_edges.iter().enumerate() {
184                        if u_e == q || v_e == q {
185                            continue;
186                        }
187                        // eta=0 means u->v direction
188                        if u_e == v {
189                            terms.push((f_idx(q, t, i, 0), 1)); // outgoing
190                            terms.push((f_idx(q, t, i, 1), -1)); // incoming
191                        }
192                        if v_e == v {
193                            terms.push((f_idx(q, t, i, 0), -1)); // incoming
194                            terms.push((f_idx(q, t, i, 1), 1)); // outgoing
195                        }
196                    }
197
198                    // Candidate edges
199                    for (j, &(sj, tj, _)) in self.potential_weights().iter().enumerate() {
200                        if sj == q || tj == q {
201                            continue;
202                        }
203                        // eta=0 means s->t direction
204                        if sj == v {
205                            terms.push((g_idx(q, t, j, 0), 1));
206                            terms.push((g_idx(q, t, j, 1), -1));
207                        }
208                        if tj == v {
209                            terms.push((g_idx(q, t, j, 0), -1));
210                            terms.push((g_idx(q, t, j, 1), 1));
211                        }
212                    }
213
214                    let rhs = if v == root {
215                        1
216                    } else if v == t {
217                        -1
218                    } else {
219                        0
220                    };
221                    constraints.push(LinearConstraint::eq(terms, rhs));
222                }
223            }
224        }
225
226        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
227            .map_err(Self::target_construction)?;
228        Ok(ReductionBiconnAugToILP {
229            target,
230            num_candidates: p,
231        })
232    }
233}
234
235#[cfg(feature = "example-db")]
236pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
237    use crate::export::SolutionPair;
238    vec![crate::example_db::specs::RuleExampleSpec {
239        id: "biconnectivityaugmentation_to_ilp",
240        build: || {
241            // Path 0-1-2-3, candidates: (0,2,1),(0,3,2),(1,3,1), budget=3
242            let source = BiconnectivityAugmentation::new(
243                SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]),
244                vec![(0, 2, 1), (0, 3, 2), (1, 3, 1)],
245                3,
246            );
247            let reduction: ReductionBiconnAugToILP =
248                crate::rules::ReduceTo::<ILP<bool>>::reduce_to(&source)
249                    .expect("reduction should succeed");
250            let ilp_sol = crate::solvers::ILPSolver::new()
251                .solve(reduction.target_problem())
252                .expect("ILP should be solvable");
253            let extracted = reduction.extract_solution(&ilp_sol).unwrap();
254            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
255                source,
256                SolutionPair {
257                    source_config: serde_json::json!(extracted),
258                    target_config: serde_json::json!(ilp_sol),
259                },
260            )
261        },
262    }]
263}
264
265#[cfg(test)]
266#[path = "../unit_tests/rules/biconnectivityaugmentation_ilp.rs"]
267mod tests;
problemreductions/rules/biconnectivityaugmentation_ilp.rs

problemreductions/rules/
biconnectivityaugmentation_ilp.rs
