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, anti-parallel constraints, and vertex disjointness.
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;
11
12/// Result of reducing DisjointConnectingPaths to ILP.
13///
14/// Variable layout (all binary):
15/// - `f^k_{e,dir}` for each commodity k and each directed orientation of each edge.
16///   For edge index `e` with endpoints `(u,v)`, direction 0 is u->v and direction 1 is v->u.
17///   Index: `k * 2m + 2e + dir` for k in 0..K, e in 0..m, dir in {0,1}.
18///
19/// Total: `K * 2m` variables.
20#[derive(Debug, Clone)]
21pub struct ReductionDCPToILP {
22    target: ILP<bool>,
23    /// Canonical edge list used during construction.
24    edges: Vec<(usize, usize)>,
25    num_commodities: usize,
26    num_edge_vars_per_commodity: usize,
27}
28
29impl ReductionResult for ReductionDCPToILP {
30    type Source = DisjointConnectingPaths<SimpleGraph>;
31    type Target = ILP<bool>;
32
33    fn target_problem(&self) -> &ILP<bool> {
34        &self.target
35    }
36
37    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
38        // Mark an edge selected iff some orientation carries flow for some commodity.
39        let m = self.edges.len();
40        let mut result = vec![0usize; m];
41        for k in 0..self.num_commodities {
42            for e in 0..m {
43                let fwd = target_solution[k * self.num_edge_vars_per_commodity + 2 * e];
44                let rev = target_solution[k * self.num_edge_vars_per_commodity + 2 * e + 1];
45                if fwd == 1 || rev == 1 {
46                    result[e] = 1;
47                }
48            }
49        }
50        result
51    }
52}
53
54#[reduction(
55    overhead = {
56        num_vars = "num_pairs * 2 * num_edges",
57        num_constraints = "num_pairs * num_vertices + num_pairs * num_edges + num_edges + num_vertices",
58    }
59)]
60impl ReduceTo<ILP<bool>> for DisjointConnectingPaths<SimpleGraph> {
61    type Result = ReductionDCPToILP;
62
63    #[allow(clippy::needless_range_loop)]
64    fn reduce_to(&self) -> Self::Result {
65        let edges = self.ordered_edges();
66        let m = edges.len();
67        let n = self.num_vertices();
68        let k_count = self.num_pairs();
69
70        // Variable layout: only flow variables, no MTZ ordering needed for binary flow
71        let num_flow_vars_per_k = 2 * m; // f^k_{e,dir}
72        let num_vars = k_count * num_flow_vars_per_k;
73
74        let flow_var =
75            |k: usize, e: usize, dir: usize| -> usize { k * num_flow_vars_per_k + 2 * e + dir };
76
77        let mut constraints = Vec::new();
78
79        // Build adjacency index: for each vertex, which edges are incident
80        let mut vertex_edges: Vec<Vec<usize>> = vec![Vec::new(); n];
81        for (e, &(u, v)) in edges.iter().enumerate() {
82            vertex_edges[u].push(e);
83            vertex_edges[v].push(e);
84        }
85
86        // Identify terminal vertices
87        let mut is_terminal = vec![false; n];
88        for &(s, t) in self.terminal_pairs() {
89            is_terminal[s] = true;
90            is_terminal[t] = true;
91        }
92
93        for (k, &(s_k, t_k)) in self.terminal_pairs().iter().enumerate() {
94            // Flow conservation: outflow - inflow = demand at each vertex
95            for vertex in 0..n {
96                let mut terms = Vec::new();
97                for &e in &vertex_edges[vertex] {
98                    let (eu, _ev) = edges[e];
99                    if vertex == eu {
100                        // vertex is first endpoint: dir=0 is outgoing, dir=1 is incoming
101                        terms.push((flow_var(k, e, 0), 1.0));
102                        terms.push((flow_var(k, e, 1), -1.0));
103                    } else {
104                        // vertex is second endpoint: dir=1 is outgoing, dir=0 is incoming
105                        terms.push((flow_var(k, e, 1), 1.0));
106                        terms.push((flow_var(k, e, 0), -1.0));
107                    }
108                }
109
110                let demand = if vertex == s_k {
111                    1.0
112                } else if vertex == t_k {
113                    -1.0
114                } else {
115                    0.0
116                };
117                constraints.push(LinearConstraint::eq(terms, demand));
118            }
119
120            // Anti-parallel: f^k_{e,0} + f^k_{e,1} <= 1 for each edge
121            for e in 0..m {
122                constraints.push(LinearConstraint::le(
123                    vec![(flow_var(k, e, 0), 1.0), (flow_var(k, e, 1), 1.0)],
124                    1.0,
125                ));
126            }
127        }
128
129        // Edge disjointness: each edge is used by at most one commodity
130        // sum_k (f^k_{e,0} + f^k_{e,1}) <= 1
131        for e in 0..m {
132            let mut terms = Vec::new();
133            for k in 0..k_count {
134                terms.push((flow_var(k, e, 0), 1.0));
135                terms.push((flow_var(k, e, 1), 1.0));
136            }
137            constraints.push(LinearConstraint::le(terms, 1.0));
138        }
139
140        // Vertex disjointness: for each non-terminal vertex v,
141        // sum over all commodities k of (outgoing flow from v) <= 1
142        for v in 0..n {
143            if is_terminal[v] {
144                continue;
145            }
146            let mut terms = Vec::new();
147            for k in 0..k_count {
148                for &e in &vertex_edges[v] {
149                    let (eu, _ev) = edges[e];
150                    if v == eu {
151                        terms.push((flow_var(k, e, 0), 1.0));
152                    } else {
153                        terms.push((flow_var(k, e, 1), 1.0));
154                    }
155                }
156            }
157            constraints.push(LinearConstraint::le(terms, 1.0));
158        }
159
160        let target = ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize);
161
162        ReductionDCPToILP {
163            target,
164            edges,
165            num_commodities: k_count,
166            num_edge_vars_per_commodity: num_flow_vars_per_k,
167        }
168    }
169}
170
171#[cfg(feature = "example-db")]
172pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
173    vec![crate::example_db::specs::RuleExampleSpec {
174        id: "disjointconnectingpaths_to_ilp",
175        build: || {
176            // 6 vertices, two vertex-disjoint paths
177            let source = DisjointConnectingPaths::new(
178                SimpleGraph::new(6, vec![(0, 1), (1, 2), (3, 4), (4, 5)]),
179                vec![(0, 2), (3, 5)],
180            );
181            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
182        },
183    }]
184}
185
186#[cfg(test)]
187#[path = "../unit_tests/rules/disjointconnectingpaths_ilp.rs"]
188mod tests;
problemreductions/rules/disjointconnectingpaths_ilp.rs

problemreductions/rules/
disjointconnectingpaths_ilp.rs
