problemreductions/rules/
undirectedtwocommodityintegralflow_ilp.rs

1//! Reduction from UndirectedTwoCommodityIntegralFlow to ILP<i32>.
2//!
3//! For each undirected edge {u,v} (indexed by e), we introduce 4 flow variables:
4//!   f1_{uv} = 4*e + 0  (commodity 1 flow u→v)
5//!   f1_{vu} = 4*e + 1  (commodity 1 flow v→u)
6//!   f2_{uv} = 4*e + 2  (commodity 2 flow u→v)
7//!   f2_{vu} = 4*e + 3  (commodity 2 flow v→u)
8//!
9//! Additional binary indicator variables for capacity sharing:
10//!   d1_e = 4*|E| + 2*e     (1 if commodity 1 uses forward direction on edge e)
11//!   d2_e = 4*|E| + 2*e + 1 (1 if commodity 2 uses forward direction on edge e)
12//!
13//! For each edge e with capacity c_e, the joint capacity constraint is:
14//!   max(f1_{uv}, f1_{vu}) + max(f2_{uv}, f2_{vu}) ≤ c_e
15//!
16//! Since this is ILP<i32>, we use direction indicators d1_e, d2_e ∈ {0,1} to linearize:
17//!   f1_{uv} ≤ c_e * d1_e;  f1_{vu} ≤ c_e * (1 - d1_e)
18//!   f2_{uv} ≤ c_e * d2_e;  f2_{vu} ≤ c_e * (1 - d2_e)
19//!   f1_{uv} + f1_{vu} + f2_{uv} + f2_{vu} ≤ c_e  (joint capacity)
20//!
21//! Variable layout (6 variables per edge):
22//!   [0..4*E): f1_{uv}, f1_{vu}, f2_{uv}, f2_{vu} per edge
23//!   [4*E..6*E): d1_e, d2_e per edge
24//!
25//! Constraints per edge (7 per edge) + flow conservation (2 per non-terminal vertex) + net flow (2)
26
27use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
28use crate::models::graph::UndirectedTwoCommodityIntegralFlow;
29use crate::reduction;
30use crate::rules::traits::{ReduceTo, ReductionResult};
31use crate::topology::Graph;
32
33/// Result of reducing UndirectedTwoCommodityIntegralFlow to ILP<i32>.
34///
35/// Variable layout:
36/// - `f1_{uv}` at 4*e + 0, `f1_{vu}` at 4*e + 1 (commodity 1 flows on edge e)
37/// - `f2_{uv}` at 4*e + 2, `f2_{vu}` at 4*e + 3 (commodity 2 flows on edge e)
38/// - `d1_e` at 4*|E| + 2*e, `d2_e` at 4*|E| + 2*e + 1 (direction indicators)
39#[derive(Debug, Clone)]
40pub struct ReductionU2CIFToILP {
41    target: ILP<i32>,
42    num_edges: usize,
43}
44
45impl ReductionResult for ReductionU2CIFToILP {
46    type Source = UndirectedTwoCommodityIntegralFlow;
47    type Target = ILP<i32>;
48
49    fn target_problem(&self) -> &ILP<i32> {
50        &self.target
51    }
52
53    /// Extract flow solution: first 4*|E| variables are the flow values.
54    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
55        target_solution[..4 * self.num_edges].to_vec()
56    }
57}
58
59#[reduction(
60    overhead = {
61        num_vars = "6 * num_edges",
62        num_constraints = "7 * num_edges + 2 * num_nonterminal_vertices + 2",
63    }
64)]
65impl ReduceTo<ILP<i32>> for UndirectedTwoCommodityIntegralFlow {
66    type Result = ReductionU2CIFToILP;
67
68    fn reduce_to(&self) -> Self::Result {
69        let edges = self.graph().edges();
70        let e = edges.len();
71        let n = self.num_vertices();
72        // 4*e flow variables + 2*e direction indicators = 6*e total
73        let num_vars = 6 * e;
74
75        // Variable index helpers
76        let f1_uv = |edge: usize| 4 * edge;
77        let f1_vu = |edge: usize| 4 * edge + 1;
78        let f2_uv = |edge: usize| 4 * edge + 2;
79        let f2_vu = |edge: usize| 4 * edge + 3;
80        let d1 = |edge: usize| 4 * e + 2 * edge;
81        let d2 = |edge: usize| 4 * e + 2 * edge + 1;
82
83        let mut constraints = Vec::with_capacity(7 * e + 2 * self.num_nonterminal_vertices() + 2);
84
85        for (edge_idx, (_u, _v)) in edges.iter().enumerate() {
86            let cap = self.capacities()[edge_idx] as f64;
87
88            // Direction indicators are binary: d1_e ≤ 1, d2_e ≤ 1
89            constraints.push(LinearConstraint::le(vec![(d1(edge_idx), 1.0)], 1.0));
90            constraints.push(LinearConstraint::le(vec![(d2(edge_idx), 1.0)], 1.0));
91
92            // Commodity 1 anti-parallel: f1_{uv} ≤ cap * d1_e
93            // => f1_{uv} - cap * d1_e ≤ 0
94            constraints.push(LinearConstraint::le(
95                vec![(f1_uv(edge_idx), 1.0), (d1(edge_idx), -cap)],
96                0.0,
97            ));
98            // f1_{vu} ≤ cap * (1 - d1_e) => f1_{vu} + cap*d1_e ≤ cap
99            constraints.push(LinearConstraint::le(
100                vec![(f1_vu(edge_idx), 1.0), (d1(edge_idx), cap)],
101                cap,
102            ));
103
104            // Commodity 2 anti-parallel: f2_{uv} ≤ cap * d2_e
105            constraints.push(LinearConstraint::le(
106                vec![(f2_uv(edge_idx), 1.0), (d2(edge_idx), -cap)],
107                0.0,
108            ));
109            // f2_{vu} ≤ cap * (1 - d2_e)
110            constraints.push(LinearConstraint::le(
111                vec![(f2_vu(edge_idx), 1.0), (d2(edge_idx), cap)],
112                cap,
113            ));
114
115            // Joint capacity: f1_{uv} + f1_{vu} + f2_{uv} + f2_{vu} ≤ cap
116            constraints.push(LinearConstraint::le(
117                vec![
118                    (f1_uv(edge_idx), 1.0),
119                    (f1_vu(edge_idx), 1.0),
120                    (f2_uv(edge_idx), 1.0),
121                    (f2_vu(edge_idx), 1.0),
122                ],
123                cap,
124            ));
125        }
126
127        // Flow conservation for each commodity at non-terminal vertices
128        let terminals = [
129            self.source_1(),
130            self.sink_1(),
131            self.source_2(),
132            self.sink_2(),
133        ];
134
135        for vertex in 0..n {
136            if terminals.contains(&vertex) {
137                continue;
138            }
139
140            // Commodity 1 conservation: Σ_in f1 - Σ_out f1 = 0
141            let mut terms_c1: Vec<(usize, f64)> = Vec::new();
142            // Commodity 2 conservation: Σ_in f2 - Σ_out f2 = 0
143            let mut terms_c2: Vec<(usize, f64)> = Vec::new();
144
145            for (edge_idx, &(u, v)) in edges.iter().enumerate() {
146                if vertex == u {
147                    // outgoing from u: f1_{uv} goes out, f1_{vu} comes in
148                    terms_c1.push((f1_uv(edge_idx), -1.0));
149                    terms_c1.push((f1_vu(edge_idx), 1.0));
150                    terms_c2.push((f2_uv(edge_idx), -1.0));
151                    terms_c2.push((f2_vu(edge_idx), 1.0));
152                } else if vertex == v {
153                    // outgoing from v: f1_{vu} goes out, f1_{uv} comes in
154                    terms_c1.push((f1_uv(edge_idx), 1.0));
155                    terms_c1.push((f1_vu(edge_idx), -1.0));
156                    terms_c2.push((f2_uv(edge_idx), 1.0));
157                    terms_c2.push((f2_vu(edge_idx), -1.0));
158                }
159            }
160
161            if !terms_c1.is_empty() {
162                constraints.push(LinearConstraint::eq(terms_c1, 0.0));
163            }
164            if !terms_c2.is_empty() {
165                constraints.push(LinearConstraint::eq(terms_c2, 0.0));
166            }
167        }
168
169        // Net flow into sinks ≥ requirements
170        // Commodity 1: net inflow at sink_1 ≥ requirement_1
171        let sink_1 = self.sink_1();
172        let mut sink1_terms: Vec<(usize, f64)> = Vec::new();
173        for (edge_idx, &(u, v)) in edges.iter().enumerate() {
174            if sink_1 == v {
175                sink1_terms.push((f1_uv(edge_idx), 1.0));
176                sink1_terms.push((f1_vu(edge_idx), -1.0));
177            } else if sink_1 == u {
178                sink1_terms.push((f1_uv(edge_idx), -1.0));
179                sink1_terms.push((f1_vu(edge_idx), 1.0));
180            }
181        }
182        constraints.push(LinearConstraint::ge(
183            sink1_terms,
184            self.requirement_1() as f64,
185        ));
186
187        // Commodity 2: net inflow at sink_2 ≥ requirement_2
188        let sink_2 = self.sink_2();
189        let mut sink2_terms: Vec<(usize, f64)> = Vec::new();
190        for (edge_idx, &(u, v)) in edges.iter().enumerate() {
191            if sink_2 == v {
192                sink2_terms.push((f2_uv(edge_idx), 1.0));
193                sink2_terms.push((f2_vu(edge_idx), -1.0));
194            } else if sink_2 == u {
195                sink2_terms.push((f2_uv(edge_idx), -1.0));
196                sink2_terms.push((f2_vu(edge_idx), 1.0));
197            }
198        }
199        constraints.push(LinearConstraint::ge(
200            sink2_terms,
201            self.requirement_2() as f64,
202        ));
203
204        ReductionU2CIFToILP {
205            target: ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize),
206            num_edges: e,
207        }
208    }
209}
210
211#[cfg(feature = "example-db")]
212pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
213    use crate::export::SolutionPair;
214    use crate::topology::SimpleGraph;
215
216    vec![crate::example_db::specs::RuleExampleSpec {
217        id: "undirectedtwocommodityintegralflow_to_ilp",
218        build: || {
219            // 4-vertex graph: edges (0,2),(1,2),(2,3); capacities [1,1,2]
220            // s1=0, t1=3, s2=1, t2=3, R1=1, R2=1
221            // f1 routes 0→2→3 (1 unit), f2 routes 1→2→3 (1 unit)
222            let source = UndirectedTwoCommodityIntegralFlow::new(
223                SimpleGraph::new(4, vec![(0, 2), (1, 2), (2, 3)]),
224                vec![1, 1, 2],
225                0,
226                3,
227                1,
228                3,
229                1,
230                1,
231            );
232            let reduction: ReductionU2CIFToILP = ReduceTo::<ILP<i32>>::reduce_to(&source);
233            let solver = crate::solvers::ILPSolver::new();
234            let target_config = solver
235                .solve(reduction.target_problem())
236                .expect("canonical example should be feasible");
237            let source_config = reduction.extract_solution(&target_config);
238            crate::example_db::specs::rule_example_with_witness::<_, ILP<i32>>(
239                source,
240                SolutionPair {
241                    source_config,
242                    target_config,
243                },
244            )
245        },
246    }]
247}
248
249#[cfg(test)]
250#[path = "../unit_tests/rules/undirectedtwocommodityintegralflow_ilp.rs"]
251mod tests;
problemreductions/rules/undirectedtwocommodityintegralflow_ilp.rs

problemreductions/rules/
undirectedtwocommodityintegralflow_ilp.rs
