problemreductions/rules/
integralflowbundles_ilp.rs

1//! Reduction from Integral Flow with Bundles to ILP.
2//!
3//! Each directed arc gets one non-negative integer ILP variable. The ILP keeps
4//! the bundle-capacity inequalities, flow-conservation equalities at
5//! nonterminals, and the sink inflow lower bound from the source problem.
6
7use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
8use crate::models::graph::IntegralFlowBundles;
9use crate::reduction;
10use crate::rules::traits::{ReduceTo, ReductionResult};
11
12/// Result of reducing IntegralFlowBundles to ILP.
13#[derive(Debug, Clone)]
14pub struct ReductionIFBToILP {
15    target: ILP<i32>,
16}
17
18impl ReductionResult for ReductionIFBToILP {
19    type Source = IntegralFlowBundles;
20    type Target = ILP<i32>;
21
22    fn target_problem(&self) -> &ILP<i32> {
23        &self.target
24    }
25
26    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
27        target_solution.to_vec()
28    }
29}
30
31#[reduction(
32    overhead = {
33        num_vars = "num_arcs",
34        num_constraints = "num_bundles + num_vertices - 1",
35    }
36)]
37impl ReduceTo<ILP<i32>> for IntegralFlowBundles {
38    type Result = ReductionIFBToILP;
39
40    fn reduce_to(&self) -> Self::Result {
41        let arcs = self.graph().arcs();
42        let mut constraints = Vec::with_capacity(self.num_bundles() + self.num_vertices() - 1);
43
44        for (bundle, &capacity) in self.bundles().iter().zip(self.bundle_capacities()) {
45            let terms = bundle.iter().map(|&arc_index| (arc_index, 1.0)).collect();
46            constraints.push(LinearConstraint::le(terms, capacity as f64));
47        }
48
49        for vertex in 0..self.num_vertices() {
50            if vertex == self.source() || vertex == self.sink() {
51                continue;
52            }
53
54            let mut terms = Vec::new();
55            for (arc_index, (u, v)) in arcs.iter().copied().enumerate() {
56                if vertex == u {
57                    terms.push((arc_index, -1.0));
58                }
59                if vertex == v {
60                    terms.push((arc_index, 1.0));
61                }
62            }
63            constraints.push(LinearConstraint::eq(terms, 0.0));
64        }
65
66        let mut sink_terms = Vec::new();
67        for (arc_index, (u, v)) in arcs.iter().copied().enumerate() {
68            if self.sink() == u {
69                sink_terms.push((arc_index, -1.0));
70            }
71            if self.sink() == v {
72                sink_terms.push((arc_index, 1.0));
73            }
74        }
75        constraints.push(LinearConstraint::ge(sink_terms, self.requirement() as f64));
76
77        ReductionIFBToILP {
78            target: ILP::new(
79                self.num_arcs(),
80                constraints,
81                vec![],
82                ObjectiveSense::Minimize,
83            ),
84        }
85    }
86}
87
88#[cfg(feature = "example-db")]
89pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
90    use crate::topology::DirectedGraph;
91
92    vec![crate::example_db::specs::RuleExampleSpec {
93        id: "integralflowbundles_to_ilp",
94        build: || {
95            let source = IntegralFlowBundles::new(
96                DirectedGraph::new(4, vec![(0, 1), (0, 2), (1, 3), (2, 3), (1, 2), (2, 1)]),
97                0,
98                3,
99                vec![vec![0, 1], vec![2, 5], vec![3, 4]],
100                vec![1, 1, 1],
101                1,
102            );
103            crate::example_db::specs::rule_example_via_ilp::<_, i32>(source)
104        },
105    }]
106}
107
108#[cfg(test)]
109#[path = "../unit_tests/rules/integralflowbundles_ilp.rs"]
110mod tests;
problemreductions/rules/integralflowbundles_ilp.rs

problemreductions/rules/
integralflowbundles_ilp.rs
