problemreductions/rules/
undirectedtwocommodityintegralflow_ilp.rs

1//! Reduction from UndirectedTwoCommodityIntegralFlow to `ILP<i64>`.
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<i64>`, 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<i64>`.
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<i64>,
42    num_edges: usize,
43}
44
45impl ReductionResult for ReductionU2CIFToILP {
46    type Source = UndirectedTwoCommodityIntegralFlow;
47    type Target = ILP<i64>;
48
49    fn target_problem(&self) -> &ILP<i64> {
50        &self.target
51    }
52
53    /// Extract flow solution: first 4*|E| variables are the flow values.
54    fn extract_solution(
55        &self,
56        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
57    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
58        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
59
60        crate::rules::ilp_helpers::decode_usize_values(&target_solution[..4 * self.num_edges])
61    }
62}
63
64#[reduction(
65    transform = exact {
66        num_vars = "6 * num_edges",
67        num_constraints = "7 * num_edges + num_conservation_constraints + 2",
68    },
69    unavailable = {
70        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
71    }
72)]
73impl ReduceTo<ILP<i64>> for UndirectedTwoCommodityIntegralFlow {
74    type Result = ReductionU2CIFToILP;
75
76    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
77        let edges = self.graph().edges();
78        let e = edges.len();
79        let n = self.num_vertices();
80        // 4*e flow variables + 2*e direction indicators = 6*e total
81        let num_vars = 6 * e;
82        // Variable index helpers
83        let f1_uv = |edge: usize| 4 * edge;
84        let f1_vu = |edge: usize| 4 * edge + 1;
85        let f2_uv = |edge: usize| 4 * edge + 2;
86        let f2_vu = |edge: usize| 4 * edge + 3;
87        let d1 = |edge: usize| 4 * e + 2 * edge;
88        let d2 = |edge: usize| 4 * e + 2 * edge + 1;
89
90        let mut constraints = Vec::with_capacity(7 * e + self.num_conservation_constraints() + 2);
91
92        for (edge_idx, (_u, _v)) in edges.iter().enumerate() {
93            let cap = self.capacities()[edge_idx];
94
95            // Direction indicators are binary: d1_e ≤ 1, d2_e ≤ 1
96            constraints.push(LinearConstraint::le(vec![(d1(edge_idx), 1)], 1));
97            constraints.push(LinearConstraint::le(vec![(d2(edge_idx), 1)], 1));
98
99            // Commodity 1 anti-parallel: f1_{uv} ≤ cap * d1_e
100            // => f1_{uv} - cap * d1_e ≤ 0
101            constraints.push(LinearConstraint::le(
102                vec![(f1_uv(edge_idx), 1), (d1(edge_idx), -cap)],
103                0,
104            ));
105            // f1_{vu} ≤ cap * (1 - d1_e) => f1_{vu} + cap*d1_e ≤ cap
106            constraints.push(LinearConstraint::le(
107                vec![(f1_vu(edge_idx), 1), (d1(edge_idx), cap)],
108                cap,
109            ));
110
111            // Commodity 2 anti-parallel: f2_{uv} ≤ cap * d2_e
112            constraints.push(LinearConstraint::le(
113                vec![(f2_uv(edge_idx), 1), (d2(edge_idx), -cap)],
114                0,
115            ));
116            // f2_{vu} ≤ cap * (1 - d2_e)
117            constraints.push(LinearConstraint::le(
118                vec![(f2_vu(edge_idx), 1), (d2(edge_idx), cap)],
119                cap,
120            ));
121
122            // Joint capacity: f1_{uv} + f1_{vu} + f2_{uv} + f2_{vu} ≤ cap
123            constraints.push(LinearConstraint::le(
124                vec![
125                    (f1_uv(edge_idx), 1),
126                    (f1_vu(edge_idx), 1),
127                    (f2_uv(edge_idx), 1),
128                    (f2_vu(edge_idx), 1),
129                ],
130                cap,
131            ));
132        }
133
134        // Each commodity is conserved at every vertex except its own source and sink.
135        for (commodity, source, sink) in [
136            (1, self.source_1(), self.sink_1()),
137            (2, self.source_2(), self.sink_2()),
138        ] {
139            for vertex in 0..n {
140                if vertex == source || vertex == sink {
141                    continue;
142                }
143
144                let mut terms = Vec::new();
145                for (edge_idx, &(u, v)) in edges.iter().enumerate() {
146                    let (uv, vu) = if commodity == 1 {
147                        (f1_uv(edge_idx), f1_vu(edge_idx))
148                    } else {
149                        (f2_uv(edge_idx), f2_vu(edge_idx))
150                    };
151                    if vertex == u {
152                        terms.push((uv, -1));
153                        terms.push((vu, 1));
154                    } else if vertex == v {
155                        terms.push((uv, 1));
156                        terms.push((vu, -1));
157                    }
158                }
159                constraints.push(LinearConstraint::eq(terms, 0));
160            }
161        }
162
163        // Net flow into sinks ≥ requirements
164        // Commodity 1: net inflow at sink_1 ≥ requirement_1
165        let sink_1 = self.sink_1();
166        let mut sink1_terms: Vec<(usize, i64)> = Vec::new();
167        for (edge_idx, &(u, v)) in edges.iter().enumerate() {
168            if sink_1 == v {
169                sink1_terms.push((f1_uv(edge_idx), 1));
170                sink1_terms.push((f1_vu(edge_idx), -1));
171            } else if sink_1 == u {
172                sink1_terms.push((f1_uv(edge_idx), -1));
173                sink1_terms.push((f1_vu(edge_idx), 1));
174            }
175        }
176        constraints.push(LinearConstraint::ge(sink1_terms, self.requirement_1()));
177
178        // Commodity 2: net inflow at sink_2 ≥ requirement_2
179        let sink_2 = self.sink_2();
180        let mut sink2_terms: Vec<(usize, i64)> = Vec::new();
181        for (edge_idx, &(u, v)) in edges.iter().enumerate() {
182            if sink_2 == v {
183                sink2_terms.push((f2_uv(edge_idx), 1));
184                sink2_terms.push((f2_vu(edge_idx), -1));
185            } else if sink_2 == u {
186                sink2_terms.push((f2_uv(edge_idx), -1));
187                sink2_terms.push((f2_vu(edge_idx), 1));
188            }
189        }
190        constraints.push(LinearConstraint::ge(sink2_terms, self.requirement_2()));
191
192        Ok(ReductionU2CIFToILP {
193            target: ILP::new(num_vars, constraints, vec![], ObjectiveSense::Minimize)
194                .map_err(Self::target_construction)?,
195            num_edges: e,
196        })
197    }
198}
199
200#[cfg(feature = "example-db")]
201pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
202    use crate::export::SolutionPair;
203    use crate::topology::SimpleGraph;
204
205    vec![crate::example_db::specs::RuleExampleSpec {
206        id: "undirectedtwocommodityintegralflow_to_ilp",
207        build: || {
208            // 4-vertex graph: edges (0,2),(1,2),(2,3); capacities [1,1,2]
209            // s1=0, t1=3, s2=1, t2=3, R1=1, R2=1
210            // f1 routes 0→2→3 (1 unit), f2 routes 1→2→3 (1 unit)
211            let source = UndirectedTwoCommodityIntegralFlow::new(
212                SimpleGraph::new(4, vec![(0, 2), (1, 2), (2, 3)]),
213                vec![1, 1, 2],
214                0,
215                3,
216                1,
217                3,
218                1,
219                1,
220            );
221            let reduction: ReductionU2CIFToILP =
222                ReduceTo::<ILP<i64>>::reduce_to(&source).expect("reduction should succeed");
223            let solver = crate::solvers::ILPSolver::new();
224            let target_config = solver
225                .solve(reduction.target_problem())
226                .expect("canonical example should be feasible");
227            let source_config = reduction.extract_solution(&target_config).unwrap();
228            crate::example_db::specs::rule_example_with_witness::<_, ILP<i64>>(
229                source,
230                SolutionPair {
231                    source_config: serde_json::to_value(source_config)
232                        .expect("solution serialization must succeed"),
233                    target_config: serde_json::to_value(target_config)
234                        .expect("solution serialization must succeed"),
235                },
236            )
237        },
238    }]
239}
240
241#[cfg(test)]
242#[path = "../unit_tests/rules/undirectedtwocommodityintegralflow_ilp.rs"]
243mod tests;
problemreductions/rules/undirectedtwocommodityintegralflow_ilp.rs

problemreductions/rules/
undirectedtwocommodityintegralflow_ilp.rs
