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<i64>,
16}
17
18impl ReductionResult for ReductionIFBToILP {
19    type Source = IntegralFlowBundles;
20    type Target = ILP<i64>;
21
22    fn target_problem(&self) -> &ILP<i64> {
23        &self.target
24    }
25
26    fn extract_solution(
27        &self,
28        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
29    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
30        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
31
32        crate::rules::ilp_helpers::decode_usize_values(target_solution)
33    }
34}
35
36#[reduction(
37    transform = exact {
38        num_vars = "num_arcs",
39        num_constraints = "num_bundles + num_vertices - 1",
40    },
41    unavailable = {
42        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
43    }
44)]
45impl ReduceTo<ILP<i64>> for IntegralFlowBundles {
46    type Result = ReductionIFBToILP;
47
48    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
49        let arcs = self.graph().arcs();
50        let mut constraints = Vec::with_capacity(self.num_bundles() + self.num_vertices() - 1);
51
52        for (bundle, &capacity) in self.bundles().iter().zip(self.bundle_capacities()) {
53            let terms = bundle.iter().map(|&arc_index| (arc_index, 1)).collect();
54            constraints.push(LinearConstraint::le(terms, capacity));
55        }
56
57        for vertex in 0..self.num_vertices() {
58            if vertex == self.source() || vertex == self.sink() {
59                continue;
60            }
61
62            let mut terms = Vec::new();
63            for (arc_index, (u, v)) in arcs.iter().copied().enumerate() {
64                if vertex == u {
65                    terms.push((arc_index, -1));
66                }
67                if vertex == v {
68                    terms.push((arc_index, 1));
69                }
70            }
71            constraints.push(LinearConstraint::eq(terms, 0));
72        }
73
74        let mut sink_terms = Vec::new();
75        for (arc_index, (u, v)) in arcs.iter().copied().enumerate() {
76            if self.sink() == u {
77                sink_terms.push((arc_index, -1));
78            }
79            if self.sink() == v {
80                sink_terms.push((arc_index, 1));
81            }
82        }
83        constraints.push(LinearConstraint::ge(sink_terms, self.requirement()));
84
85        Ok(ReductionIFBToILP {
86            target: ILP::new(
87                self.num_arcs(),
88                constraints,
89                vec![],
90                ObjectiveSense::Minimize,
91            )
92            .map_err(Self::target_construction)?,
93        })
94    }
95}
96
97#[cfg(feature = "example-db")]
98pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
99    use crate::topology::DirectedGraph;
100
101    vec![crate::example_db::specs::RuleExampleSpec {
102        id: "integralflowbundles_to_ilp",
103        build: || {
104            let source = IntegralFlowBundles::new(
105                DirectedGraph::new(4, vec![(0, 1), (0, 2), (1, 3), (2, 3), (1, 2), (2, 1)]),
106                0,
107                3,
108                vec![vec![0, 1], vec![2, 5], vec![3, 4]],
109                vec![1, 1, 1],
110                1,
111            );
112            crate::example_db::specs::rule_example_via_ilp::<_, i64>(source)
113        },
114    }]
115}
116
117#[cfg(test)]
118#[path = "../unit_tests/rules/integralflowbundles_ilp.rs"]
119mod tests;
problemreductions/rules/integralflowbundles_ilp.rs

problemreductions/rules/
integralflowbundles_ilp.rs
