problemreductions/rules/
disjointconnectingpaths_ilp.rs

1//! Reduction from DisjointConnectingPaths to ILP.
2//!
3//! Binary flow variables `f^k_{e,dir}` per commodity per directed arc orientation.
4//! Flow conservation and unit vertex capacities enforce vertex-disjoint paths.
5
6use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
7use crate::models::graph::DisjointConnectingPaths;
8use crate::reduction;
9use crate::rules::traits::{ReduceTo, ReductionResult};
10use crate::topology::SimpleGraph;
11use std::collections::VecDeque;
12
13/// Result of reducing DisjointConnectingPaths to ILP.
14///
15/// Variable layout (all binary):
16/// - `f^k_{e,dir}` for each commodity k and each directed orientation of each edge.
17///   For edge index `e` with endpoints `(u,v)`, direction 0 is u->v and direction 1 is v->u.
18///   Index: `k * 2m + 2e + dir` for k in 0..K, e in 0..m, dir in {0,1}.
19///
20/// Total: `K * 2m` variables.
21#[derive(Debug, Clone)]
22pub struct ReductionDCPToILP {
23    target: ILP<bool>,
24    /// Canonical edge list used during construction.
25    edges: Vec<(usize, usize)>,
26    num_vertices: usize,
27    terminal_pairs: Vec<(usize, usize)>,
28    num_edge_vars_per_commodity: usize,
29}
30
31impl ReductionResult for ReductionDCPToILP {
32    type Source = DisjointConnectingPaths<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 mut result = vec![false; self.edges.len()];
46        for (k, &(source, sink)) in self.terminal_pairs.iter().enumerate() {
47            let offset = k * self.num_edge_vars_per_commodity;
48            let mut adjacency = vec![Vec::new(); self.num_vertices];
49            for (edge, &(u, v)) in self.edges.iter().enumerate() {
50                if target_solution[offset + 2 * edge] == 1 {
51                    adjacency[u].push((v, edge));
52                }
53                if target_solution[offset + 2 * edge + 1] == 1 {
54                    adjacency[v].push((u, edge));
55                }
56            }
57            let mut visited = vec![false; self.num_vertices];
58            let mut predecessor = vec![None; self.num_vertices];
59            let mut queue = VecDeque::from([source]);
60            visited[source] = true;
61            while let Some(u) = queue.pop_front() {
62                if u == sink {
63                    break;
64                }
65                for &(v, edge) in &adjacency[u] {
66                    if !visited[v] {
67                        visited[v] = true;
68                        predecessor[v] = Some((u, edge));
69                        queue.push_back(v);
70                    }
71                }
72            }
73            let mut vertex = sink;
74            while vertex != source {
75                let (previous, edge) = predecessor[vertex].ok_or_else(|| {
76                    crate::rules::ExtractionError::invalid(
77                        "commodity flow does not connect its terminal pair",
78                    )
79                })?;
80                result[edge] = true;
81                vertex = previous;
82            }
83        }
84        Ok(result)
85    }
86}
87
88#[reduction(
89    transform = exact {
90        num_vars = "num_pairs * 2 * num_edges",
91        num_constraints = "num_pairs * num_vertices + num_vertices",
92    },
93    unavailable = {
94        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
95    }
96)]
97impl ReduceTo<ILP<bool>> for DisjointConnectingPaths<SimpleGraph> {
98    type Result = ReductionDCPToILP;
99
100    #[allow(clippy::needless_range_loop)]
101    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
102        let edges = self.ordered_edges();
103        let m = edges.len();
104        let n = self.num_vertices();
105        let k_count = self.num_pairs();
106
107        let overflow = |operation| {
108            crate::rules::ReductionError::integer_overflow::<Self, ILP<bool>>(operation)
109        };
110        let num_flow_vars_per_k = m
111            .checked_mul(2)
112            .ok_or_else(|| overflow("computing the flow-variable stride"))?;
113        let num_vars = k_count
114            .checked_mul(num_flow_vars_per_k)
115            .ok_or_else(|| overflow("computing the flow-variable count"))?;
116
117        let flow_var =
118            |k: usize, e: usize, dir: usize| -> usize { k * num_flow_vars_per_k + 2 * e + dir };
119
120        let mut constraints = Vec::new();
121
122        // Build adjacency index: for each vertex, which edges are incident
123        let mut vertex_edges: Vec<Vec<usize>> = vec![Vec::new(); n];
124        for (e, &(u, v)) in edges.iter().enumerate() {
125            vertex_edges[u].push(e);
126            vertex_edges[v].push(e);
127        }
128
129        let mut is_source = vec![false; n];
130        for &(source, _) in self.terminal_pairs() {
131            is_source[source] = true;
132        }
133
134        for (k, &(s_k, t_k)) in self.terminal_pairs().iter().enumerate() {
135            // Flow conservation: outflow - inflow = demand at each vertex
136            for vertex in 0..n {
137                let mut terms = Vec::new();
138                for &e in &vertex_edges[vertex] {
139                    let (eu, _ev) = edges[e];
140                    if vertex == eu {
141                        // vertex is first endpoint: dir=0 is outgoing, dir=1 is incoming
142                        terms.push((flow_var(k, e, 0), 1));
143                        terms.push((flow_var(k, e, 1), -1));
144                    } else {
145                        // vertex is second endpoint: dir=1 is outgoing, dir=0 is incoming
146                        terms.push((flow_var(k, e, 1), 1));
147                        terms.push((flow_var(k, e, 0), -1));
148                    }
149                }
150
151                let demand = if vertex == s_k {
152                    1
153                } else if vertex == t_k {
154                    -1
155                } else {
156                    0
157                };
158                constraints.push(LinearConstraint::eq(terms, demand));
159            }
160        }
161
162        // Incoming flow records vertex use. A source is occupied by its own
163        // commodity even though it has no incoming flow.
164        for v in 0..n {
165            let mut terms = Vec::new();
166            for k in 0..k_count {
167                for &e in &vertex_edges[v] {
168                    let (eu, _ev) = edges[e];
169                    if v == eu {
170                        terms.push((flow_var(k, e, 1), 1));
171                    } else {
172                        terms.push((flow_var(k, e, 0), 1));
173                    }
174                }
175            }
176            constraints.push(LinearConstraint::le(terms, 1 - i64::from(is_source[v])));
177        }
178
179        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
180            .map_err(Self::target_construction)?;
181
182        Ok(ReductionDCPToILP {
183            target,
184            edges,
185            num_vertices: n,
186            terminal_pairs: self.terminal_pairs().to_vec(),
187            num_edge_vars_per_commodity: num_flow_vars_per_k,
188        })
189    }
190}
191
192#[cfg(feature = "example-db")]
193pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
194    vec![crate::example_db::specs::RuleExampleSpec {
195        id: "disjointconnectingpaths_to_ilp",
196        build: || {
197            // 6 vertices, two vertex-disjoint paths
198            let source = DisjointConnectingPaths::new(
199                SimpleGraph::new(6, vec![(0, 1), (1, 2), (3, 4), (4, 5)]),
200                vec![(0, 2), (3, 5)],
201            );
202            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
203        },
204    }]
205}
206
207#[cfg(test)]
208#[path = "../unit_tests/rules/disjointconnectingpaths_ilp.rs"]
209mod tests;
problemreductions/rules/disjointconnectingpaths_ilp.rs

problemreductions/rules/
disjointconnectingpaths_ilp.rs
