problemreductions/rules/
biconnectivityaugmentation_ilp.rs

1//! Reduction from BiconnectivityAugmentation to `ILP<i64>`.
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::{IntegerVariable, 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<i64>,
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<i64>,
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<i64>;
52
53    fn target_problem(&self) -> &ILP<i64> {
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        if crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?
62            .value
63            .is_none()
64        {
65            return Err(crate::rules::ExtractionError::invalid(
66                "target ILP assignment is infeasible",
67            ));
68        }
69
70        Ok(target_solution[..self.num_candidates]
71            .iter()
72            .map(|&value| value == 1)
73            .collect())
74    }
75}
76
77#[reduction(
78    transform = upper_bound {
79        num_vars = "num_potential_edges + 2 * num_vertices * (num_vertices + 1) * (num_edges + num_potential_edges)",
80        num_constraints = "1 + num_vertices * (num_vertices + 1) * (2 * num_edges + 4 * num_potential_edges + num_vertices)",
81    },
82    unavailable = {
83        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
84    }
85)]
86impl ReduceTo<ILP<i64>> for BiconnectivityAugmentation<SimpleGraph, i64> {
87    type Result = ReductionBiconnAugToILP;
88
89    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
90        let n = self.num_vertices();
91        let p = self.num_potential_edges();
92
93        let base_edges = self.graph().edges();
94        let m = base_edges.len();
95
96        // q = n certifies the original graph; q < n deletes that vertex.
97        // y_j occupies [0,p), followed by all base-edge and candidate-edge flows.
98        let (candidate_start, num_vars) = ReductionBiconnAugToILP::dimensions(n, m, p)?;
99        let f_idx = |q: usize, t: usize, i: usize, eta: usize| -> usize {
100            p + ((q * n + t) * m + i) * 2 + eta
101        };
102        let g_idx = |q: usize, t: usize, j: usize, eta: usize| -> usize {
103            candidate_start + ((q * n + t) * p + j) * 2 + eta
104        };
105        let mut constraints = Vec::new();
106
107        // Budget constraint: Σ w_j y_j ≤ B
108        let budget_terms: Vec<(usize, i64)> = self
109            .potential_weights()
110            .iter()
111            .enumerate()
112            .map(|(candidate, &(_, _, weight))| (candidate, weight))
113            .collect();
114        constraints.push(LinearConstraint::le(budget_terms, *self.budget()));
115
116        // Include q = n: no endpoint equals n, so no vertex or edge is deleted.
117        for q in 0..=n {
118            let root = if q != 0 { 0 } else { 1 };
119
120            for t in 0..n {
121                // Pin trivial commodities to zero
122                if t == q || t == root {
123                    for i in 0..m {
124                        for eta in 0..2 {
125                            constraints
126                                .push(LinearConstraint::eq(vec![(f_idx(q, t, i, eta), 1)], 0));
127                        }
128                    }
129                    for j in 0..p {
130                        for eta in 0..2 {
131                            constraints
132                                .push(LinearConstraint::eq(vec![(g_idx(q, t, j, eta), 1)], 0));
133                        }
134                    }
135                    continue;
136                }
137
138                // Pin flows on edges incident to deleted vertex q
139                for (i, &(u, v)) in base_edges.iter().enumerate() {
140                    if u == q || v == q {
141                        for eta in 0..2 {
142                            constraints
143                                .push(LinearConstraint::eq(vec![(f_idx(q, t, i, eta), 1)], 0));
144                        }
145                    }
146                }
147                for (j, &(sj, tj, _)) in self.potential_weights().iter().enumerate() {
148                    if sj == q || tj == q {
149                        for eta in 0..2 {
150                            constraints
151                                .push(LinearConstraint::eq(vec![(g_idx(q, t, j, eta), 1)], 0));
152                        }
153                    }
154                }
155
156                // Activation: g^{q,t}_{j,eta} ≤ y_j
157                for j in 0..p {
158                    let &(sj, tj, _) = &self.potential_weights()[j];
159                    if sj == q || tj == q {
160                        continue; // already pinned to 0
161                    }
162                    for eta in 0..2 {
163                        constraints.push(LinearConstraint::le(
164                            vec![(g_idx(q, t, j, eta), 1), (j, -1)],
165                            0,
166                        ));
167                    }
168                }
169
170                // Flow conservation for each surviving vertex v ≠ q
171                for v in 0..n {
172                    if v == q {
173                        continue;
174                    }
175                    let mut terms: Vec<(usize, i64)> = Vec::new();
176
177                    // Base edges
178                    for (i, &(u_e, v_e)) in base_edges.iter().enumerate() {
179                        if u_e == q || v_e == q {
180                            continue;
181                        }
182                        // eta=0 means u->v direction
183                        if u_e == v {
184                            terms.push((f_idx(q, t, i, 0), 1)); // outgoing
185                            terms.push((f_idx(q, t, i, 1), -1)); // incoming
186                        }
187                        if v_e == v {
188                            terms.push((f_idx(q, t, i, 0), -1)); // incoming
189                            terms.push((f_idx(q, t, i, 1), 1)); // outgoing
190                        }
191                    }
192
193                    // Candidate edges
194                    for (j, &(sj, tj, _)) in self.potential_weights().iter().enumerate() {
195                        if sj == q || tj == q {
196                            continue;
197                        }
198                        // eta=0 means s->t direction
199                        if sj == v {
200                            terms.push((g_idx(q, t, j, 0), 1));
201                            terms.push((g_idx(q, t, j, 1), -1));
202                        }
203                        if tj == v {
204                            terms.push((g_idx(q, t, j, 0), -1));
205                            terms.push((g_idx(q, t, j, 1), 1));
206                        }
207                    }
208
209                    let rhs = if v == root {
210                        1
211                    } else if v == t {
212                        -1
213                    } else {
214                        0
215                    };
216                    constraints.push(LinearConstraint::eq(terms, rhs));
217                }
218            }
219        }
220
221        let target = ILP::with_variables(
222            vec![IntegerVariable::binary(); num_vars],
223            constraints,
224            vec![],
225            ObjectiveSense::Minimize,
226        )
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<i64>>::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<i64>>(
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
