problemreductions/rules/
directedtwocommodityintegralflow_ilp.rs

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

problemreductions/rules/
directedtwocommodityintegralflow_ilp.rs
