problemreductions/rules/
lengthboundeddisjointpaths_ilp.rs

1//! Reduction from LengthBoundedDisjointPaths to ILP.
2//!
3//! Binary flow variables per commodity per directed edge orientation.
4//! Conservation, edge/vertex disjointness, and length bound.
5
6use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
7use crate::models::graph::LengthBoundedDisjointPaths;
8use crate::reduction;
9use crate::rules::traits::{ReduceTo, ReductionResult};
10use crate::topology::{Graph, SimpleGraph};
11use std::collections::VecDeque;
12
13/// Result of reducing LengthBoundedDisjointPaths to ILP.
14///
15/// Variable layout (all binary):
16/// - Flow: `f^k_{e,dir}` at index `k * 2m + 2e + dir`
17/// - Activation: `a_k` at index `J * 2m + k`
18///
19/// Total: `J * (2m + 1)` variables.
20#[derive(Debug, Clone)]
21pub struct ReductionLBDPToILP {
22    target: ILP<bool>,
23    /// Edges in the source graph's order, with their original orientations.
24    edges: Vec<(usize, usize)>,
25    num_vertices: usize,
26    num_paths: usize,
27    source: usize,
28    sink: usize,
29}
30
31impl ReductionResult for ReductionLBDPToILP {
32    type Source = LengthBoundedDisjointPaths<SimpleGraph>;
33    type Target = ILP<bool>;
34
35    fn target_problem(&self) -> &ILP<bool> {
36        &self.target
37    }
38
39    fn extract_solution(
40        &self,
41        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
42    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
43        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
44
45        let m = self.edges.len();
46        let flow_vars_per_k = 2 * m;
47        let activation_offset = self.num_paths * flow_vars_per_k;
48        let mut result = vec![vec![false; m]; self.num_paths];
49        for (k, path) in result.iter_mut().enumerate() {
50            if target_solution[activation_offset + k] == 0 {
51                if target_solution[k * flow_vars_per_k..(k + 1) * flow_vars_per_k]
52                    .iter()
53                    .any(|&flow| flow != 0)
54                {
55                    return Err(crate::rules::ExtractionError::invalid(
56                        "inactive path slot contains flow",
57                    ));
58                }
59                continue;
60            }
61            let mut adjacency = vec![Vec::new(); self.num_vertices];
62            for (e, &(u, v)) in self.edges.iter().enumerate() {
63                if target_solution[k * flow_vars_per_k + 2 * e] == 1 {
64                    adjacency[u].push((v, e));
65                }
66                if target_solution[k * flow_vars_per_k + 2 * e + 1] == 1 {
67                    adjacency[v].push((u, e));
68                }
69            }
70
71            // A unit flow contains an s-t path; BFS excludes any extra circulation.
72            let mut visited = vec![false; self.num_vertices];
73            let mut predecessor = vec![None; self.num_vertices];
74            let mut queue = VecDeque::from([self.source]);
75            visited[self.source] = true;
76            while let Some(u) = queue.pop_front() {
77                if u == self.sink {
78                    break;
79                }
80                for &(v, edge) in &adjacency[u] {
81                    if !visited[v] {
82                        visited[v] = true;
83                        predecessor[v] = Some((u, edge));
84                        queue.push_back(v);
85                    }
86                }
87            }
88            let mut vertex = self.sink;
89            while vertex != self.source {
90                let (previous, edge) = predecessor[vertex].ok_or_else(|| {
91                    crate::rules::ExtractionError::invalid(
92                        "active path flow does not connect source to sink",
93                    )
94                })?;
95                path[edge] = true;
96                vertex = previous;
97            }
98        }
99        Ok(result)
100    }
101}
102
103#[reduction(transform = {
104    exact {
105        num_vars = "max_paths * 2 * num_edges + max_paths",
106    },
107    upper_bound {
108        max_constraint_magnitude_bits = "num_vertices + 1",
109        num_constraints = "max_paths * num_vertices + max_paths * num_edges + max_paths + num_edges + num_vertices + max_paths",
110        num_nonzeros = "(max_paths * 2 * num_edges + max_paths) * (max_paths * num_vertices + max_paths * num_edges + max_paths + num_edges + num_vertices + max_paths)",
111    },
112})]
113impl ReduceTo<ILP<bool>> for LengthBoundedDisjointPaths<SimpleGraph> {
114    type Result = ReductionLBDPToILP;
115
116    #[allow(clippy::needless_range_loop)]
117    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
118        let edges = self.graph().edges();
119
120        let m = edges.len();
121        let n = self.num_vertices();
122        let j = self.max_paths();
123        // A simple path uses at most n-1 edges; cycles never improve the path packing.
124        let max_len = Self::exact_i64(
125            self.max_length().min(n.saturating_sub(1)),
126            "encoding the path-length bound",
127        )?;
128        let s = self.source();
129        let t = self.sink();
130
131        // Variable layout: flow variables + activation variables a_k
132        let overflow = |operation| {
133            crate::rules::ReductionError::integer_overflow::<Self, ILP<bool>>(operation)
134        };
135        let flow_vars_per_k = m
136            .checked_mul(2)
137            .ok_or_else(|| overflow("computing the flow-variable stride"))?;
138        let num_flow = j
139            .checked_mul(flow_vars_per_k)
140            .ok_or_else(|| overflow("computing the flow-variable count"))?;
141        let a_var = |k: usize| num_flow + k;
142        let num_vars = num_flow
143            .checked_add(j)
144            .ok_or_else(|| overflow("computing the ILP variable count"))?;
145
146        let flow_var = |k: usize, e: usize, dir: usize| k * flow_vars_per_k + 2 * e + dir;
147
148        // Build vertex-to-edge adjacency
149        let mut vertex_edges: Vec<Vec<usize>> = vec![Vec::new(); n];
150        for (e, &(u, v)) in edges.iter().enumerate() {
151            vertex_edges[u].push(e);
152            vertex_edges[v].push(e);
153        }
154
155        let mut constraints = Vec::new();
156
157        for k in 0..j {
158            // Flow conservation: outflow - inflow = a_k at source, -a_k at sink, 0 elsewhere
159            for vertex in 0..n {
160                let mut terms = Vec::new();
161                for &e in &vertex_edges[vertex] {
162                    let (eu, _) = edges[e];
163                    if vertex == eu {
164                        terms.push((flow_var(k, e, 0), 1)); // outgoing
165                        terms.push((flow_var(k, e, 1), -1)); // incoming
166                    } else {
167                        terms.push((flow_var(k, e, 1), 1)); // outgoing
168                        terms.push((flow_var(k, e, 0), -1)); // incoming
169                    }
170                }
171                if vertex == s {
172                    // outflow - inflow = a_k  =>  outflow - inflow - a_k = 0
173                    terms.push((a_var(k), -1));
174                    constraints.push(LinearConstraint::eq(terms, 0));
175                } else if vertex == t {
176                    // outflow - inflow = -a_k  =>  outflow - inflow + a_k = 0
177                    terms.push((a_var(k), 1));
178                    constraints.push(LinearConstraint::eq(terms, 0));
179                } else {
180                    constraints.push(LinearConstraint::eq(terms, 0));
181                }
182            }
183
184            // Anti-parallel
185            for e in 0..m {
186                constraints.push(LinearConstraint::le(
187                    vec![(flow_var(k, e, 0), 1), (flow_var(k, e, 1), 1)],
188                    1,
189                ));
190            }
191
192            // Length bound: total flow for commodity k <= max_length * a_k
193            let mut len_terms = Vec::new();
194            for e in 0..m {
195                len_terms.push((flow_var(k, e, 0), 1));
196                len_terms.push((flow_var(k, e, 1), 1));
197            }
198            len_terms.push((a_var(k), -max_len));
199            constraints.push(LinearConstraint::le(len_terms, 0));
200        }
201
202        // Edge disjointness: each edge used by at most one commodity
203        for e in 0..m {
204            let mut terms = Vec::new();
205            for k in 0..j {
206                terms.push((flow_var(k, e, 0), 1));
207                terms.push((flow_var(k, e, 1), 1));
208            }
209            constraints.push(LinearConstraint::le(terms, 1));
210        }
211
212        // Vertex disjointness for non-terminal vertices
213        for v in 0..n {
214            if v == s || v == t {
215                continue;
216            }
217            let mut terms = Vec::new();
218            for k in 0..j {
219                for &e in &vertex_edges[v] {
220                    let (eu, _) = edges[e];
221                    if v == eu {
222                        terms.push((flow_var(k, e, 0), 1));
223                    } else {
224                        terms.push((flow_var(k, e, 1), 1));
225                    }
226                }
227            }
228            constraints.push(LinearConstraint::le(terms, 1));
229        }
230
231        // Objective: maximize number of active path slots
232        let objective: Vec<(usize, i64)> = (0..j).map(|k| (a_var(k), 1)).collect();
233        let target = ILP::new(num_vars, constraints, objective, ObjectiveSense::Maximize)
234            .map_err(Self::target_construction)?;
235
236        Ok(ReductionLBDPToILP {
237            target,
238            edges,
239            num_vertices: n,
240            num_paths: j,
241            source: s,
242            sink: t,
243        })
244    }
245}
246
247#[cfg(feature = "example-db")]
248pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
249    vec![crate::example_db::specs::RuleExampleSpec {
250        id: "lengthboundeddisjointpaths_to_ilp",
251        build: || {
252            // 4-vertex diamond: s=0, t=3, K=2
253            let source = LengthBoundedDisjointPaths::new(
254                SimpleGraph::new(4, vec![(0, 1), (0, 2), (1, 3), (2, 3)]),
255                0,
256                3,
257                2,
258            );
259            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
260        },
261    }]
262}
263
264#[cfg(test)]
265#[path = "../unit_tests/rules/lengthboundeddisjointpaths_ilp.rs"]
266mod tests;
problemreductions/rules/lengthboundeddisjointpaths_ilp.rs

problemreductions/rules/
lengthboundeddisjointpaths_ilp.rs
