problemreductions/rules/
integralflowwithmultipliers_ilp.rs

1//! Reduction from IntegralFlowWithMultipliers to ILP.
2//!
3//! One integer flow variable per arc. Capacity bounds, multiplier-scaled
4//! conservation at non-terminals, and sink inflow requirement.
5
6use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
7use crate::models::graph::IntegralFlowWithMultipliers;
8use crate::reduction;
9use crate::rules::traits::{ReduceTo, ReductionResult};
10
11/// Result of reducing IntegralFlowWithMultipliers to ILP.
12#[derive(Debug, Clone)]
13pub struct ReductionIFWMToILP {
14    target: ILP<i64>,
15}
16
17impl ReductionResult for ReductionIFWMToILP {
18    type Source = IntegralFlowWithMultipliers;
19    type Target = ILP<i64>;
20
21    fn target_problem(&self) -> &ILP<i64> {
22        &self.target
23    }
24
25    fn extract_solution(
26        &self,
27        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
28    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
29        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
30
31        crate::rules::ilp_helpers::decode_usize_values(target_solution)
32    }
33}
34
35#[reduction(
36    transform = exact {
37        num_vars = "num_arcs",
38        num_constraints = "num_arcs + num_vertices - 1",
39    },
40    unavailable = {
41        num_nonzeros = "the exact target parameter is not represented by this reduction's symbolic transform",
42    }
43)]
44impl ReduceTo<ILP<i64>> for IntegralFlowWithMultipliers {
45    type Result = ReductionIFWMToILP;
46
47    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
48        let arcs = self.graph().arcs();
49        let num_arcs = self.num_arcs();
50        let num_vertices = self.num_vertices();
51        let mut constraints = Vec::new();
52
53        // Capacity: f_a <= c_a for each arc
54        for (arc_idx, &capacity) in self.capacities().iter().enumerate() {
55            constraints.push(LinearConstraint::le(vec![(arc_idx, 1)], capacity));
56        }
57
58        // Multiplier-scaled conservation:
59        // sum_{a in delta^+(v)} f_a = h(v) * sum_{a in delta^-(v)} f_a
60        // for all v in V \ {s, t}
61        // Rewrite: sum_{a in delta^+(v)} f_a - h(v) * sum_{a in delta^-(v)} f_a = 0
62        for vertex in 0..num_vertices {
63            if vertex == self.source() || vertex == self.sink() {
64                continue;
65            }
66            let multiplier = self.multipliers()[vertex];
67            let mut terms = Vec::new();
68            for (arc_idx, &(u, v)) in arcs.iter().enumerate() {
69                if u == vertex {
70                    terms.push((arc_idx, 1)); // outgoing
71                }
72                if v == vertex {
73                    terms.push((arc_idx, -multiplier)); // incoming scaled by -h(v)
74                }
75            }
76            constraints.push(LinearConstraint::eq(terms, 0));
77        }
78
79        // Sink inflow requirement: sum_{a in delta^-(t)} f_a - sum_{a in delta^+(t)} f_a >= R
80        let mut sink_terms = Vec::new();
81        for (arc_idx, &(u, v)) in arcs.iter().enumerate() {
82            if v == self.sink() {
83                sink_terms.push((arc_idx, 1)); // incoming
84            }
85            if u == self.sink() {
86                sink_terms.push((arc_idx, -1)); // outgoing
87            }
88        }
89        constraints.push(LinearConstraint::ge(sink_terms, self.requirement()));
90
91        Ok(ReductionIFWMToILP {
92            target: ILP::new(num_arcs, constraints, vec![], ObjectiveSense::Minimize)
93                .map_err(Self::target_construction)?,
94        })
95    }
96}
97
98#[cfg(feature = "example-db")]
99pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
100    use crate::topology::DirectedGraph;
101
102    vec![crate::example_db::specs::RuleExampleSpec {
103        id: "integralflowwithmultipliers_to_ilp",
104        build: || {
105            // Simple diamond: s=0, t=3, intermediate vertices 1,2 with multiplier 1
106            let source = IntegralFlowWithMultipliers::new(
107                DirectedGraph::new(4, vec![(0, 1), (0, 2), (1, 3), (2, 3)]),
108                0,
109                3,
110                vec![1, 1, 1, 1], // source/sink entries ignored
111                vec![2, 2, 2, 2],
112                2,
113            );
114            crate::example_db::specs::rule_example_via_ilp::<_, i64>(source)
115        },
116    }]
117}
118
119#[cfg(test)]
120#[path = "../unit_tests/rules/integralflowwithmultipliers_ilp.rs"]
121mod tests;
problemreductions/rules/integralflowwithmultipliers_ilp.rs

problemreductions/rules/
integralflowwithmultipliers_ilp.rs
