problemreductions/rules/
strongconnectivityaugmentation_ilp.rs

1//! Reduction from StrongConnectivityAugmentation to `ILP<bool>`.
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<bool>,
15    num_candidates: usize,
16}
17
18impl ReductionResult for ReductionSCAToILP {
19    type Source = StrongConnectivityAugmentation<i64>;
20    type Target = ILP<bool>;
21
22    fn target_problem(&self) -> &ILP<bool> {
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_witness(
31            self.target_problem(),
32            target_solution,
33            |value| value.value.is_some(),
34            "target ILP assignment is infeasible",
35        )?;
36
37        Ok(target_solution[..self.num_candidates]
38            .iter()
39            .map(|&value| value == 1)
40            .collect())
41    }
42}
43
44#[crate::aggregate_reduction(ilp_feasibility)]
45impl crate::rules::AggregateReductionResult for ReductionSCAToILP {}
46
47// Candidate bounds and budget use at most 2p terms. Each commodity has
48// 4(m+p) forward/backward conservation terms and 4p activation terms; dummy
49// commodity pins use only 2(m+p). Loop cancellation only reduces this count.
50#[reduction(transform = {
51    exact {
52        max_constraint_magnitude_bits = "max_numeric_magnitude_bits",
53    },
54    upper_bound {
55        num_vars = "num_potential_arcs + 2 * num_vertices * (num_arcs + num_potential_arcs)",
56        num_constraints = "1 + num_potential_arcs + 2 * num_arcs + 2 * num_vertices * num_potential_arcs + 2 * num_vertices * num_vertices",
57        num_nonzeros = "2 * num_potential_arcs + num_vertices * (4 * num_arcs + 8 * num_potential_arcs)",
58    },
59})]
60impl ReduceTo<ILP<bool>> for StrongConnectivityAugmentation<i64> {
61    type Result = ReductionSCAToILP;
62
63    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
64        let n = self.num_vertices();
65        let p = self.num_potential_arcs();
66
67        let base_arcs = self.graph().arcs();
68        let m = base_arcs.len();
69        let root = 0;
70
71        // Variable layout per paper:
72        // y_j:              j                          [0, p)
73        // f^t_i (fwd base): p + t*m + i                [p, p + n*m)
74        // f_bar^t_j (fwd cand): p + n*m + t*p + j      [p+nm, p+nm+np)
75        // g^t_i (bwd base): p + n*(m+p) + t*m + i      [p+n(m+p), p+n(2m+p))
76        // g_bar^t_j (bwd cand): p + n*(2m+p) + t*p + j [p+n(2m+p), p+2n(m+p))
77        let num_vars = p + 2 * n * (m + p);
78        let f_base = |t: usize, i: usize| -> usize { p + t * m + i };
79        let f_cand = |t: usize, j: usize| -> usize { p + n * m + t * p + j };
80        let g_base = |t: usize, i: usize| -> usize { p + n * (m + p) + t * m + i };
81        let g_cand = |t: usize, j: usize| -> usize { p + n * (2 * m + p) + t * p + j };
82
83        let mut constraints = Vec::new();
84
85        // Binary bounds: y_j ≤ 1
86        for j in 0..p {
87            constraints.push(LinearConstraint::le(vec![(j, 1)], 1));
88        }
89
90        // Budget: Σ w_j * y_j ≤ B
91        let budget_terms: Vec<(usize, i64)> = self
92            .candidate_arcs()
93            .iter()
94            .enumerate()
95            .map(|(candidate, &(_, _, weight))| (candidate, weight))
96            .collect();
97        constraints.push(LinearConstraint::le(budget_terms, *self.bound()));
98
99        for t in 0..n {
100            if t == root {
101                // Pin all flow vars to 0 for dummy commodity t = root
102                for i in 0..m {
103                    constraints.push(LinearConstraint::eq(vec![(f_base(t, i), 1)], 0));
104                    constraints.push(LinearConstraint::eq(vec![(g_base(t, i), 1)], 0));
105                }
106                for j in 0..p {
107                    constraints.push(LinearConstraint::eq(vec![(f_cand(t, j), 1)], 0));
108                    constraints.push(LinearConstraint::eq(vec![(g_cand(t, j), 1)], 0));
109                }
110                continue;
111            }
112
113            // Activation: f_bar^t_j ≤ y_j and g_bar^t_j ≤ y_j
114            for j in 0..p {
115                constraints.push(LinearConstraint::le(vec![(f_cand(t, j), 1), (j, -1)], 0));
116                constraints.push(LinearConstraint::le(vec![(g_cand(t, j), 1), (j, -1)], 0));
117            }
118
119            // Forward flow conservation (root → t): for each vertex v
120            for v in 0..n {
121                let mut terms: Vec<(usize, i64)> = Vec::new();
122
123                // Base arcs
124                for (i, &(u_a, v_a)) in base_arcs.iter().enumerate() {
125                    if u_a == v {
126                        terms.push((f_base(t, i), 1)); // outgoing
127                    }
128                    if v_a == v {
129                        terms.push((f_base(t, i), -1)); // incoming
130                    }
131                }
132
133                // Candidate arcs
134                for (j, &(sj, tj, _)) in self.candidate_arcs().iter().enumerate() {
135                    if sj == v {
136                        terms.push((f_cand(t, j), 1)); // outgoing
137                    }
138                    if tj == v {
139                        terms.push((f_cand(t, j), -1)); // incoming
140                    }
141                }
142
143                let rhs = if v == root {
144                    1
145                } else if v == t {
146                    -1
147                } else {
148                    0
149                };
150                constraints.push(LinearConstraint::eq(terms, rhs));
151            }
152
153            // Backward flow conservation (t → root): for each vertex v
154            for v in 0..n {
155                let mut terms: Vec<(usize, i64)> = Vec::new();
156
157                // Base arcs
158                for (i, &(u_a, v_a)) in base_arcs.iter().enumerate() {
159                    if u_a == v {
160                        terms.push((g_base(t, i), 1));
161                    }
162                    if v_a == v {
163                        terms.push((g_base(t, i), -1));
164                    }
165                }
166
167                // Candidate arcs
168                for (j, &(sj, tj, _)) in self.candidate_arcs().iter().enumerate() {
169                    if sj == v {
170                        terms.push((g_cand(t, j), 1));
171                    }
172                    if tj == v {
173                        terms.push((g_cand(t, j), -1));
174                    }
175                }
176
177                let rhs = if v == t {
178                    1 // source of backward flow
179                } else if v == root {
180                    -1 // sink of backward flow
181                } else {
182                    0
183                };
184                constraints.push(LinearConstraint::eq(terms, rhs));
185            }
186        }
187
188        // Each connectivity certificate can be a simple unit-flow path; cycles are unnecessary.
189        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
190            .map_err(Self::target_construction)?;
191        Ok(ReductionSCAToILP {
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    use crate::topology::DirectedGraph;
202    vec![crate::example_db::specs::RuleExampleSpec {
203        id: "strongconnectivityaugmentation_to_ilp",
204        build: || {
205            // Path 0→1→2, candidates: (2,0,1),(1,0,2), bound=2
206            let source = StrongConnectivityAugmentation::new(
207                DirectedGraph::new(3, vec![(0, 1), (1, 2)]),
208                vec![(2, 0, 1), (1, 0, 2)],
209                2,
210            );
211            let reduction: ReductionSCAToILP =
212                crate::rules::ReduceTo::<ILP<bool>>::reduce_to(&source)
213                    .expect("reduction should succeed");
214            let ilp_sol = crate::solvers::ILPSolver::new()
215                .solve(reduction.target_problem())
216                .expect("ILP should be solvable");
217            let extracted = reduction.extract_solution(&ilp_sol).unwrap();
218            crate::example_db::specs::rule_example_with_witness::<_, ILP<bool>>(
219                source,
220                SolutionPair {
221                    source_config: serde_json::json!(extracted),
222                    target_config: serde_json::json!(ilp_sol),
223                },
224            )
225        },
226    }]
227}
228
229#[cfg(test)]
230#[path = "../unit_tests/rules/strongconnectivityaugmentation_ilp.rs"]
231mod tests;
problemreductions/rules/strongconnectivityaugmentation_ilp.rs

problemreductions/rules/
strongconnectivityaugmentation_ilp.rs
