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::{Bounded, IntegerVariable, LinearConstraint, ObjectiveSense, ILP};
8use crate::models::graph::IntegralFlowBundles;
9use crate::reduction;
10use crate::rules::ilp_helpers::bounded_flow_requirement;
11use crate::rules::traits::{ReduceTo, ReductionResult};
12
13/// Result of reducing IntegralFlowBundles to ILP.
14#[derive(Debug, Clone)]
15pub struct ReductionIFBToILP {
16    target: ILP<i64, i64, Bounded>,
17}
18
19impl ReductionResult for ReductionIFBToILP {
20    type Source = IntegralFlowBundles;
21    type Target = ILP<i64, i64, Bounded>;
22
23    fn target_problem(&self) -> &ILP<i64, i64, Bounded> {
24        &self.target
25    }
26
27    fn extract_solution(
28        &self,
29        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
30    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
31        crate::rules::traits::validate_target_witness(
32            self.target_problem(),
33            target_solution,
34            |value| value.value.is_some(),
35            "target ILP assignment is infeasible",
36        )?;
37
38        crate::rules::ilp_helpers::decode_usize_values(target_solution)
39    }
40}
41
42#[crate::aggregate_reduction(ilp_feasibility)]
43impl crate::rules::AggregateReductionResult for ReductionIFBToILP {}
44
45#[reduction(transform = {
46    exact {
47        num_vars = "num_arcs",
48        num_constraints = "num_bundles + num_vertices - 1",
49    },
50    upper_bound {
51        max_constraint_magnitude_bits = "max_capacity_bits + num_arcs + 1",
52        num_nonzeros = "num_arcs * (num_bundles + num_vertices - 1)",
53    },
54})]
55impl ReduceTo<ILP<i64, i64, Bounded>> for IntegralFlowBundles {
56    type Result = ReductionIFBToILP;
57
58    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
59        let arcs = self.graph().arcs();
60        let mut constraints = Vec::with_capacity(self.num_bundles() + self.num_vertices() - 1);
61
62        for (bundle, &capacity) in self.bundles().iter().zip(self.bundle_capacities()) {
63            let terms = bundle.iter().map(|&arc_index| (arc_index, 1)).collect();
64            constraints.push(LinearConstraint::le(terms, capacity));
65        }
66
67        for vertex in 0..self.num_vertices() {
68            if vertex == self.source() || vertex == self.sink() {
69                continue;
70            }
71
72            let mut terms = Vec::new();
73            for (arc_index, (u, v)) in arcs.iter().copied().enumerate() {
74                if vertex == u {
75                    terms.push((arc_index, -1));
76                }
77                if vertex == v {
78                    terms.push((arc_index, 1));
79                }
80            }
81            constraints.push(LinearConstraint::eq(terms, 0));
82        }
83
84        let mut sink_terms = Vec::new();
85        for (arc_index, (u, v)) in arcs.iter().copied().enumerate() {
86            if self.sink() == u {
87                sink_terms.push((arc_index, -1));
88            }
89            if self.sink() == v {
90                sink_terms.push((arc_index, 1));
91            }
92        }
93        let upper_bounds = self.arc_upper_bounds();
94        let requirement =
95            bounded_flow_requirement(self.requirement(), upper_bounds.iter().copied());
96        constraints.push(LinearConstraint::ge(sink_terms, requirement));
97
98        let variables = upper_bounds
99            .into_iter()
100            .map(|capacity| IntegerVariable::new(Some(0), Some(capacity)))
101            .collect::<Result<Vec<_>, _>>()
102            .map_err(Self::target_construction)?;
103
104        Ok(ReductionIFBToILP {
105            target: ILP::with_variables(variables, constraints, vec![], ObjectiveSense::Minimize)
106                .map_err(Self::target_construction)?,
107        })
108    }
109}
110
111#[cfg(feature = "example-db")]
112pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
113    use crate::topology::DirectedGraph;
114
115    vec![crate::example_db::specs::RuleExampleSpec {
116        id: "integralflowbundles_to_ilp",
117        build: || {
118            let source = IntegralFlowBundles::new(
119                DirectedGraph::new(4, vec![(0, 1), (0, 2), (1, 3), (2, 3), (1, 2), (2, 1)]),
120                0,
121                3,
122                vec![vec![0, 1], vec![2, 5], vec![3, 4]],
123                vec![1, 1, 1],
124                1,
125            );
126            crate::example_db::specs::rule_example_via_bounded_ilp::<_>(source)
127        },
128    }]
129}
130
131#[cfg(test)]
132#[path = "../unit_tests/rules/integralflowbundles_ilp.rs"]
133mod tests;
problemreductions/rules/integralflowbundles_ilp.rs

problemreductions/rules/
integralflowbundles_ilp.rs
