problemreductions/rules/
directedtwocommodityintegralflow_ilp.rs

1//! Reduction from DirectedTwoCommodityIntegralFlow to `ILP<i64>`.
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<i64>`.
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<i64>,
28    num_arcs: usize,
29}
30
31impl ReductionResult for ReductionD2CIFToILP {
32    type Source = DirectedTwoCommodityIntegralFlow;
33    type Target = ILP<i64>;
34
35    fn target_problem(&self) -> &ILP<i64> {
36        &self.target
37    }
38
39    /// Extract flow solution: all 2*|A| variables directly encode the flow.
40    fn extract_solution(
41        &self,
42        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
43    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
44        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
45
46        crate::rules::ilp_helpers::decode_usize_values(&target_solution[..2 * self.num_arcs])
47    }
48}
49
50#[reduction(
51    transform = upper_bound {
52        num_vars = "2 * num_arcs",
53        num_constraints = "num_arcs + 2 * num_vertices + 2",
54    },
55    unavailable = {
56        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
57    }
58)]
59impl ReduceTo<ILP<i64>> for DirectedTwoCommodityIntegralFlow {
60    type Result = ReductionD2CIFToILP;
61
62    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
63        let arcs = self.graph().arcs();
64        let m = arcs.len();
65        let n = self.num_vertices();
66        let num_vars = 2 * m;
67
68        let f1 = |a: usize| a;
69        let f2 = |a: usize| m + a;
70
71        let mut constraints = Vec::new();
72
73        // 1. Joint capacity: f1_a + f2_a ≤ cap[a]
74        for a in 0..m {
75            constraints.push(LinearConstraint::le(
76                vec![(f1(a), 1), (f2(a), 1)],
77                self.capacities()[a],
78            ));
79        }
80
81        // 2. Flow conservation away from each commodity's own source and sink
82        for vertex in 0..n {
83            // Commodity 1: Σ_in f1 - Σ_out f1 = 0
84            let mut terms_c1: Option<Vec<(usize, i64)>> = None;
85            // Commodity 2: Σ_in f2 - Σ_out f2 = 0
86            let mut terms_c2: Option<Vec<(usize, i64)>> = None;
87
88            if vertex != self.source_1() && vertex != self.sink_1() {
89                terms_c1 = Some(Vec::new());
90            }
91            if vertex != self.source_2() && vertex != self.sink_2() {
92                terms_c2 = Some(Vec::new());
93            }
94
95            for (a, &(u, v)) in arcs.iter().enumerate() {
96                if vertex == u {
97                    // Arc leaves vertex: outgoing
98                    if let Some(terms) = &mut terms_c1 {
99                        terms.push((f1(a), -1));
100                    }
101                    if let Some(terms) = &mut terms_c2 {
102                        terms.push((f2(a), -1));
103                    }
104                } else if vertex == v {
105                    // Arc enters vertex: incoming
106                    if let Some(terms) = &mut terms_c1 {
107                        terms.push((f1(a), 1));
108                    }
109                    if let Some(terms) = &mut terms_c2 {
110                        terms.push((f2(a), 1));
111                    }
112                }
113            }
114
115            if let Some(terms_c1) = terms_c1.filter(|terms| !terms.is_empty()) {
116                constraints.push(LinearConstraint::eq(terms_c1, 0));
117            }
118            if let Some(terms_c2) = terms_c2.filter(|terms| !terms.is_empty()) {
119                constraints.push(LinearConstraint::eq(terms_c2, 0));
120            }
121        }
122
123        // 3. Net flow into sink_1 ≥ requirement_1
124        let sink_1 = self.sink_1();
125        let mut sink1_terms: Vec<(usize, i64)> = Vec::new();
126        for (a, &(u, v)) in arcs.iter().enumerate() {
127            if v == sink_1 {
128                sink1_terms.push((f1(a), 1));
129            } else if u == sink_1 {
130                sink1_terms.push((f1(a), -1));
131            }
132        }
133        constraints.push(LinearConstraint::ge(sink1_terms, self.requirement_1()));
134
135        // Net flow into sink_2 ≥ requirement_2
136        let sink_2 = self.sink_2();
137        let mut sink2_terms: Vec<(usize, i64)> = Vec::new();
138        for (a, &(u, v)) in arcs.iter().enumerate() {
139            if v == sink_2 {
140                sink2_terms.push((f2(a), 1));
141            } else if u == sink_2 {
142                sink2_terms.push((f2(a), -1));
143            }
144        }
145        constraints.push(LinearConstraint::ge(sink2_terms, self.requirement_2()));
146
147        Ok(ReductionD2CIFToILP {
148            target: ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
149                .map_err(Self::target_construction)?,
150            num_arcs: m,
151        })
152    }
153}
154
155#[cfg(feature = "example-db")]
156pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
157    use crate::topology::DirectedGraph;
158
159    vec![crate::example_db::specs::RuleExampleSpec {
160        id: "directedtwocommodityintegralflow_to_ilp",
161        build: || {
162            // 6-vertex network: s1=0, s2=1, t1=4, t2=5
163            // Arcs: (0,2),(0,3),(1,2),(1,3),(2,4),(2,5),(3,4),(3,5)
164            // f1 routes 0→2→4 (1 unit), f2 routes 1→3→5 (1 unit)
165            let source = DirectedTwoCommodityIntegralFlow::new(
166                DirectedGraph::new(
167                    6,
168                    vec![
169                        (0, 2),
170                        (0, 3),
171                        (1, 2),
172                        (1, 3),
173                        (2, 4),
174                        (2, 5),
175                        (3, 4),
176                        (3, 5),
177                    ],
178                ),
179                vec![1; 8],
180                0,
181                4,
182                1,
183                5,
184                1,
185                1,
186            );
187            crate::example_db::specs::rule_example_via_ilp::<_, i64>(source)
188        },
189    }]
190}
191
192#[cfg(test)]
193#[path = "../unit_tests/rules/directedtwocommodityintegralflow_ilp.rs"]
194mod tests;
problemreductions/rules/directedtwocommodityintegralflow_ilp.rs

problemreductions/rules/
directedtwocommodityintegralflow_ilp.rs
