problemreductions/rules/
directedtwocommodityintegralflow_ilp.rs

1//! Reduction from DirectedTwoCommodityIntegralFlow to ILP<i32>.
2//!
3//! One non-negative integer variable per (commodity, arc):
4//!   f1_a = a             for a in 0..num_arcs  (commodity 1 flow on arc a)
5//!   f2_a = num_arcs + a  for a in 0..num_arcs  (commodity 2 flow on arc a)
6//!
7//! Constraints:
8//! - Joint capacity: f1_a + f2_a ≤ cap[a] for each arc a
9//! - Flow conservation: for each commodity, Σ f_out(v) - Σ f_in(v) = 0 at non-terminals
10//! - Sink requirement: net inflow at sink_k ≥ R_k for each commodity k
11//!
12//! Objective: Minimize 0 (feasibility).
13//! Extraction: Direct 2*|A| variables.
14
15use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
16use crate::models::graph::DirectedTwoCommodityIntegralFlow;
17use crate::reduction;
18use crate::rules::traits::{ReduceTo, ReductionResult};
19
20/// Result of reducing DirectedTwoCommodityIntegralFlow to ILP<i32>.
21///
22/// Variable layout:
23/// - `f1_a` at index a for a in 0..num_arcs (commodity 1)
24/// - `f2_a` at index num_arcs + a for a in 0..num_arcs (commodity 2)
25#[derive(Debug, Clone)]
26pub struct ReductionD2CIFToILP {
27    target: ILP<i32>,
28    num_arcs: usize,
29}
30
31impl ReductionResult for ReductionD2CIFToILP {
32    type Source = DirectedTwoCommodityIntegralFlow;
33    type Target = ILP<i32>;
34
35    fn target_problem(&self) -> &ILP<i32> {
36        &self.target
37    }
38
39    /// Extract flow solution: all 2*|A| variables directly encode the flow.
40    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
41        target_solution[..2 * self.num_arcs].to_vec()
42    }
43}
44
45#[reduction(
46    overhead = {
47        num_vars = "2 * num_arcs",
48        num_constraints = "num_arcs + 2 * num_vertices + 2",
49    }
50)]
51impl ReduceTo<ILP<i32>> for DirectedTwoCommodityIntegralFlow {
52    type Result = ReductionD2CIFToILP;
53
54    fn reduce_to(&self) -> Self::Result {
55        let arcs = self.graph().arcs();
56        let m = arcs.len();
57        let n = self.num_vertices();
58        let num_vars = 2 * m;
59
60        let f1 = |a: usize| a;
61        let f2 = |a: usize| m + a;
62
63        let mut constraints = Vec::new();
64
65        // 1. Joint capacity: f1_a + f2_a ≤ cap[a]
66        for a in 0..m {
67            constraints.push(LinearConstraint::le(
68                vec![(f1(a), 1.0), (f2(a), 1.0)],
69                self.capacities()[a] as f64,
70            ));
71        }
72
73        // 2. Flow conservation away from each commodity's own source and sink
74        for vertex in 0..n {
75            // Commodity 1: Σ_in f1 - Σ_out f1 = 0
76            let mut terms_c1: Option<Vec<(usize, f64)>> = None;
77            // Commodity 2: Σ_in f2 - Σ_out f2 = 0
78            let mut terms_c2: Option<Vec<(usize, f64)>> = None;
79
80            if vertex != self.source_1() && vertex != self.sink_1() {
81                terms_c1 = Some(Vec::new());
82            }
83            if vertex != self.source_2() && vertex != self.sink_2() {
84                terms_c2 = Some(Vec::new());
85            }
86
87            for (a, &(u, v)) in arcs.iter().enumerate() {
88                if vertex == u {
89                    // Arc leaves vertex: outgoing
90                    if let Some(terms) = &mut terms_c1 {
91                        terms.push((f1(a), -1.0));
92                    }
93                    if let Some(terms) = &mut terms_c2 {
94                        terms.push((f2(a), -1.0));
95                    }
96                } else if vertex == v {
97                    // Arc enters vertex: incoming
98                    if let Some(terms) = &mut terms_c1 {
99                        terms.push((f1(a), 1.0));
100                    }
101                    if let Some(terms) = &mut terms_c2 {
102                        terms.push((f2(a), 1.0));
103                    }
104                }
105            }
106
107            if let Some(terms_c1) = terms_c1.filter(|terms| !terms.is_empty()) {
108                constraints.push(LinearConstraint::eq(terms_c1, 0.0));
109            }
110            if let Some(terms_c2) = terms_c2.filter(|terms| !terms.is_empty()) {
111                constraints.push(LinearConstraint::eq(terms_c2, 0.0));
112            }
113        }
114
115        // 3. Net flow into sink_1 ≥ requirement_1
116        let sink_1 = self.sink_1();
117        let mut sink1_terms: Vec<(usize, f64)> = Vec::new();
118        for (a, &(u, v)) in arcs.iter().enumerate() {
119            if v == sink_1 {
120                sink1_terms.push((f1(a), 1.0));
121            } else if u == sink_1 {
122                sink1_terms.push((f1(a), -1.0));
123            }
124        }
125        constraints.push(LinearConstraint::ge(
126            sink1_terms,
127            self.requirement_1() as f64,
128        ));
129
130        // Net flow into sink_2 ≥ requirement_2
131        let sink_2 = self.sink_2();
132        let mut sink2_terms: Vec<(usize, f64)> = Vec::new();
133        for (a, &(u, v)) in arcs.iter().enumerate() {
134            if v == sink_2 {
135                sink2_terms.push((f2(a), 1.0));
136            } else if u == sink_2 {
137                sink2_terms.push((f2(a), -1.0));
138            }
139        }
140        constraints.push(LinearConstraint::ge(
141            sink2_terms,
142            self.requirement_2() as f64,
143        ));
144
145        ReductionD2CIFToILP {
146            target: ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize),
147            num_arcs: m,
148        }
149    }
150}
151
152#[cfg(feature = "example-db")]
153pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
154    use crate::topology::DirectedGraph;
155
156    vec![crate::example_db::specs::RuleExampleSpec {
157        id: "directedtwocommodityintegralflow_to_ilp",
158        build: || {
159            // 6-vertex network: s1=0, s2=1, t1=4, t2=5
160            // Arcs: (0,2),(0,3),(1,2),(1,3),(2,4),(2,5),(3,4),(3,5)
161            // f1 routes 0→2→4 (1 unit), f2 routes 1→3→5 (1 unit)
162            let source = DirectedTwoCommodityIntegralFlow::new(
163                DirectedGraph::new(
164                    6,
165                    vec![
166                        (0, 2),
167                        (0, 3),
168                        (1, 2),
169                        (1, 3),
170                        (2, 4),
171                        (2, 5),
172                        (3, 4),
173                        (3, 5),
174                    ],
175                ),
176                vec![1; 8],
177                0,
178                4,
179                1,
180                5,
181                1,
182                1,
183            );
184            crate::example_db::specs::rule_example_via_ilp::<_, i32>(source)
185        },
186    }]
187}
188
189#[cfg(test)]
190#[path = "../unit_tests/rules/directedtwocommodityintegralflow_ilp.rs"]
191mod tests;
problemreductions/rules/directedtwocommodityintegralflow_ilp.rs

problemreductions/rules/
directedtwocommodityintegralflow_ilp.rs
