problemreductions/rules/
strongconnectivityaugmentation_ilp.rs

1//! Reduction from StrongConnectivityAugmentation to `ILP<i64>`.
2//!
3//! Select candidate arcs under the budget and certify strong connectivity by
4//! sending flow both from a root to every vertex and back again.
5//! See the paper entry for the full formulation.
6
7use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
8use crate::models::graph::StrongConnectivityAugmentation;
9use crate::reduction;
10use crate::rules::traits::{ReduceTo, ReductionResult};
11
12#[derive(Debug, Clone)]
13pub struct ReductionSCAToILP {
14    target: ILP<i64>,
15    num_candidates: usize,
16}
17
18impl ReductionResult for ReductionSCAToILP {
19    type Source = StrongConnectivityAugmentation<i64>;
20    type Target = ILP<i64>;
21
22    fn target_problem(&self) -> &ILP<i64> {
23        &self.target
24    }
25
26    fn extract_solution(
27        &self,
28        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
29    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
30        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
31
32        Ok(target_solution[..self.num_candidates]
33            .iter()
34            .map(|&value| value == 1)
35            .collect())
36    }
37}
38
39#[reduction(
40    transform = exact {
41        num_vars = "num_potential_arcs + 2 * num_vertices * (num_arcs + num_potential_arcs)",
42        num_constraints = "1 + 2 * num_vertices * num_potential_arcs + 2 * num_vertices * num_vertices",
43    },
44    unavailable = {
45        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
46    }
47)]
48impl ReduceTo<ILP<i64>> for StrongConnectivityAugmentation<i64> {
49    type Result = ReductionSCAToILP;
50
51    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
52        let n = self.num_vertices();
53        let p = self.num_potential_arcs();
54
55        let base_arcs = self.graph().arcs();
56        let m = base_arcs.len();
57        let root = 0;
58
59        // Variable layout per paper:
60        // y_j:              j                          [0, p)
61        // f^t_i (fwd base): p + t*m + i                [p, p + n*m)
62        // f_bar^t_j (fwd cand): p + n*m + t*p + j      [p+nm, p+nm+np)
63        // g^t_i (bwd base): p + n*(m+p) + t*m + i      [p+n(m+p), p+n(2m+p))
64        // g_bar^t_j (bwd cand): p + n*(2m+p) + t*p + j [p+n(2m+p), p+2n(m+p))
65        let num_vars = p + 2 * n * (m + p);
66        let f_base = |t: usize, i: usize| -> usize { p + t * m + i };
67        let f_cand = |t: usize, j: usize| -> usize { p + n * m + t * p + j };
68        let g_base = |t: usize, i: usize| -> usize { p + n * (m + p) + t * m + i };
69        let g_cand = |t: usize, j: usize| -> usize { p + n * (2 * m + p) + t * p + j };
70
71        let mut constraints = Vec::new();
72
73        // Binary bounds: y_j ≤ 1
74        for j in 0..p {
75            constraints.push(LinearConstraint::le(vec![(j, 1)], 1));
76        }
77
78        // Budget: Σ w_j * y_j ≤ B
79        let budget_terms: Vec<(usize, i64)> = self
80            .candidate_arcs()
81            .iter()
82            .enumerate()
83            .map(|(candidate, &(_, _, weight))| (candidate, weight))
84            .collect();
85        constraints.push(LinearConstraint::le(budget_terms, *self.bound()));
86
87        for t in 0..n {
88            if t == root {
89                // Pin all flow vars to 0 for dummy commodity t = root
90                for i in 0..m {
91                    constraints.push(LinearConstraint::eq(vec![(f_base(t, i), 1)], 0));
92                    constraints.push(LinearConstraint::eq(vec![(g_base(t, i), 1)], 0));
93                }
94                for j in 0..p {
95                    constraints.push(LinearConstraint::eq(vec![(f_cand(t, j), 1)], 0));
96                    constraints.push(LinearConstraint::eq(vec![(g_cand(t, j), 1)], 0));
97                }
98                continue;
99            }
100
101            // Activation: f_bar^t_j ≤ y_j and g_bar^t_j ≤ y_j
102            for j in 0..p {
103                constraints.push(LinearConstraint::le(vec![(f_cand(t, j), 1), (j, -1)], 0));
104                constraints.push(LinearConstraint::le(vec![(g_cand(t, j), 1), (j, -1)], 0));
105            }
106
107            // Forward flow conservation (root → t): for each vertex v
108            for v in 0..n {
109                let mut terms: Vec<(usize, i64)> = Vec::new();
110
111                // Base arcs
112                for (i, &(u_a, v_a)) in base_arcs.iter().enumerate() {
113                    if u_a == v {
114                        terms.push((f_base(t, i), 1)); // outgoing
115                    }
116                    if v_a == v {
117                        terms.push((f_base(t, i), -1)); // incoming
118                    }
119                }
120
121                // Candidate arcs
122                for (j, &(sj, tj, _)) in self.candidate_arcs().iter().enumerate() {
123                    if sj == v {
124                        terms.push((f_cand(t, j), 1)); // outgoing
125                    }
126                    if tj == v {
127                        terms.push((f_cand(t, j), -1)); // incoming
128                    }
129                }
130
131                let rhs = if v == root {
132                    1
133                } else if v == t {
134                    -1
135                } else {
136                    0
137                };
138                constraints.push(LinearConstraint::eq(terms, rhs));
139            }
140
141            // Backward flow conservation (t → root): for each vertex v
142            for v in 0..n {
143                let mut terms: Vec<(usize, i64)> = Vec::new();
144
145                // Base arcs
146                for (i, &(u_a, v_a)) in base_arcs.iter().enumerate() {
147                    if u_a == v {
148                        terms.push((g_base(t, i), 1));
149                    }
150                    if v_a == v {
151                        terms.push((g_base(t, i), -1));
152                    }
153                }
154
155                // Candidate arcs
156                for (j, &(sj, tj, _)) in self.candidate_arcs().iter().enumerate() {
157                    if sj == v {
158                        terms.push((g_cand(t, j), 1));
159                    }
160                    if tj == v {
161                        terms.push((g_cand(t, j), -1));
162                    }
163                }
164
165                let rhs = if v == t {
166                    1 // source of backward flow
167                } else if v == root {
168                    -1 // sink of backward flow
169                } else {
170                    0
171                };
172                constraints.push(LinearConstraint::eq(terms, rhs));
173            }
174        }
175
176        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
177            .map_err(Self::target_construction)?;
178        Ok(ReductionSCAToILP {
179            target,
180            num_candidates: p,
181        })
182    }
183}
184
185#[cfg(feature = "example-db")]
186pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
187    use crate::export::SolutionPair;
188    use crate::topology::DirectedGraph;
189    vec![crate::example_db::specs::RuleExampleSpec {
190        id: "strongconnectivityaugmentation_to_ilp",
191        build: || {
192            // Path 0→1→2, candidates: (2,0,1),(1,0,2), bound=2
193            let source = StrongConnectivityAugmentation::new(
194                DirectedGraph::new(3, vec![(0, 1), (1, 2)]),
195                vec![(2, 0, 1), (1, 0, 2)],
196                2,
197            );
198            let reduction: ReductionSCAToILP =
199                crate::rules::ReduceTo::<ILP<i64>>::reduce_to(&source)
200                    .expect("reduction should succeed");
201            let ilp_sol = crate::solvers::ILPSolver::new()
202                .solve(reduction.target_problem())
203                .expect("ILP should be solvable");
204            let extracted = reduction.extract_solution(&ilp_sol).unwrap();
205            crate::example_db::specs::rule_example_with_witness::<_, ILP<i64>>(
206                source,
207                SolutionPair {
208                    source_config: serde_json::json!(extracted),
209                    target_config: serde_json::json!(ilp_sol),
210                },
211            )
212        },
213    }]
214}
215
216#[cfg(test)]
217#[path = "../unit_tests/rules/strongconnectivityaugmentation_ilp.rs"]
218mod tests;
problemreductions/rules/strongconnectivityaugmentation_ilp.rs

problemreductions/rules/
strongconnectivityaugmentation_ilp.rs
