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_witness(
44            self.target_problem(),
45            target_solution,
46            |value| value.value.is_some(),
47            "target ILP assignment is infeasible",
48        )?;
49
50        let mut result = vec![false; self.edges.len()];
51        for (k, &(source, sink)) in self.terminal_pairs.iter().enumerate() {
52            let offset = k * self.num_edge_vars_per_commodity;
53            let mut adjacency = vec![Vec::new(); self.num_vertices];
54            for (edge, &(u, v)) in self.edges.iter().enumerate() {
55                if target_solution[offset + 2 * edge] == 1 {
56                    adjacency[u].push((v, edge));
57                }
58                if target_solution[offset + 2 * edge + 1] == 1 {
59                    adjacency[v].push((u, edge));
60                }
61            }
62            let mut visited = vec![false; self.num_vertices];
63            let mut predecessor = vec![None; self.num_vertices];
64            let mut queue = VecDeque::from([source]);
65            visited[source] = true;
66            while let Some(u) = queue.pop_front() {
67                if u == sink {
68                    break;
69                }
70                for &(v, edge) in &adjacency[u] {
71                    if !visited[v] {
72                        visited[v] = true;
73                        predecessor[v] = Some((u, edge));
74                        queue.push_back(v);
75                    }
76                }
77            }
78            let mut vertex = sink;
79            while vertex != source {
80                let (previous, edge) = predecessor[vertex].ok_or_else(|| {
81                    crate::rules::ExtractionError::invalid(
82                        "commodity flow does not connect its terminal pair",
83                    )
84                })?;
85                result[edge] = true;
86                vertex = previous;
87            }
88        }
89        Ok(result)
90    }
91}
92
93#[crate::aggregate_reduction(ilp_feasibility)]
94impl crate::rules::AggregateReductionResult for ReductionDCPToILP {}
95
96#[reduction(transform = {
97    exact {
98        num_vars = "num_pairs * 2 * num_edges",
99        num_constraints = "num_pairs * num_vertices + num_vertices",
100    },
101    upper_bound {
102        max_constraint_magnitude_bits = "1",
103        num_nonzeros = "(num_pairs * 2 * num_edges) * (num_pairs * num_vertices + num_vertices)",
104    },
105})]
106impl ReduceTo<ILP<bool>> for DisjointConnectingPaths<SimpleGraph> {
107    type Result = ReductionDCPToILP;
108
109    #[allow(clippy::needless_range_loop)]
110    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
111        let edges = self.ordered_edges();
112        let m = edges.len();
113        let n = self.num_vertices();
114        let k_count = self.num_pairs();
115
116        let overflow = |operation| {
117            crate::rules::ReductionError::integer_overflow::<Self, ILP<bool>>(operation)
118        };
119        let num_flow_vars_per_k = m
120            .checked_mul(2)
121            .ok_or_else(|| overflow("computing the flow-variable stride"))?;
122        let num_vars = k_count
123            .checked_mul(num_flow_vars_per_k)
124            .ok_or_else(|| overflow("computing the flow-variable count"))?;
125
126        let flow_var =
127            |k: usize, e: usize, dir: usize| -> usize { k * num_flow_vars_per_k + 2 * e + dir };
128
129        let mut constraints = Vec::new();
130
131        // Build adjacency index: for each vertex, which edges are incident
132        let mut vertex_edges: Vec<Vec<usize>> = vec![Vec::new(); n];
133        for (e, &(u, v)) in edges.iter().enumerate() {
134            if u == v {
135                continue;
136            }
137            vertex_edges[u].push(e);
138            vertex_edges[v].push(e);
139        }
140
141        let mut is_source = vec![false; n];
142        for &(source, _) in self.terminal_pairs() {
143            is_source[source] = true;
144        }
145
146        for (k, &(s_k, t_k)) in self.terminal_pairs().iter().enumerate() {
147            // Flow conservation: outflow - inflow = demand at each vertex
148            for vertex in 0..n {
149                let mut terms = Vec::new();
150                for &e in &vertex_edges[vertex] {
151                    let (eu, _ev) = edges[e];
152                    if vertex == eu {
153                        // vertex is first endpoint: dir=0 is outgoing, dir=1 is incoming
154                        terms.push((flow_var(k, e, 0), 1));
155                        terms.push((flow_var(k, e, 1), -1));
156                    } else {
157                        // vertex is second endpoint: dir=1 is outgoing, dir=0 is incoming
158                        terms.push((flow_var(k, e, 1), 1));
159                        terms.push((flow_var(k, e, 0), -1));
160                    }
161                }
162
163                let demand = if vertex == s_k {
164                    1
165                } else if vertex == t_k {
166                    -1
167                } else {
168                    0
169                };
170                constraints.push(LinearConstraint::eq(terms, demand));
171            }
172        }
173
174        // Incoming flow records vertex use. A source is occupied by its own
175        // commodity even though it has no incoming flow.
176        for v in 0..n {
177            let mut terms = Vec::new();
178            for k in 0..k_count {
179                for &e in &vertex_edges[v] {
180                    let (eu, _ev) = edges[e];
181                    if v == eu {
182                        terms.push((flow_var(k, e, 1), 1));
183                    } else {
184                        terms.push((flow_var(k, e, 0), 1));
185                    }
186                }
187            }
188            constraints.push(LinearConstraint::le(terms, 1 - i64::from(is_source[v])));
189        }
190
191        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
192            .map_err(Self::target_construction)?;
193
194        Ok(ReductionDCPToILP {
195            target,
196            edges,
197            num_vertices: n,
198            terminal_pairs: self.terminal_pairs().to_vec(),
199            num_edge_vars_per_commodity: num_flow_vars_per_k,
200        })
201    }
202}
203
204#[cfg(feature = "example-db")]
205pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
206    vec![crate::example_db::specs::RuleExampleSpec {
207        id: "disjointconnectingpaths_to_ilp",
208        build: || {
209            // 6 vertices, two vertex-disjoint paths
210            let source = DisjointConnectingPaths::new(
211                SimpleGraph::new(6, vec![(0, 1), (1, 2), (3, 4), (4, 5)]),
212                vec![(0, 2), (3, 5)],
213            );
214            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
215        },
216    }]
217}
218
219#[cfg(test)]
220#[path = "../unit_tests/rules/disjointconnectingpaths_ilp.rs"]
221mod tests;
problemreductions/rules/disjointconnectingpaths_ilp.rs

problemreductions/rules/
disjointconnectingpaths_ilp.rs
