problemreductions/rules/
integralflowhomologousarcs_ilp.rs

1//! Reduction from IntegralFlowHomologousArcs to ILP.
2//!
3//! One integer flow variable per arc. Capacity bounds, conservation at
4//! non-terminals, homologous-pair equality, and sink inflow requirement.
5
6use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
7use crate::models::graph::IntegralFlowHomologousArcs;
8use crate::reduction;
9use crate::rules::traits::{ReduceTo, ReductionResult};
10
11/// Result of reducing IntegralFlowHomologousArcs to ILP.
12#[derive(Debug, Clone)]
13pub struct ReductionIFHAToILP {
14    target: ILP<i64>,
15}
16
17impl ReductionResult for ReductionIFHAToILP {
18    type Source = IntegralFlowHomologousArcs;
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 = upper_bound {
37        num_vars = "num_arcs",
38        num_constraints = "num_arcs^2 + 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 IntegralFlowHomologousArcs {
45    type Result = ReductionIFHAToILP;
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        // Conservation: sum_{a in delta^-(v)} f_a = sum_{a in delta^+(v)} f_a
59        // for all v in V \ {s, t}
60        for vertex in 0..num_vertices {
61            if vertex == self.source() || vertex == self.sink() {
62                continue;
63            }
64            let mut terms = Vec::new();
65            for (arc_idx, &(u, v)) in arcs.iter().enumerate() {
66                if v == vertex {
67                    terms.push((arc_idx, 1)); // incoming
68                }
69                if u == vertex {
70                    terms.push((arc_idx, -1)); // outgoing
71                }
72            }
73            constraints.push(LinearConstraint::eq(terms, 0));
74        }
75
76        // Homologous equality: f_a = f_b for each pair (a, b)
77        for &(a, b) in self.homologous_pairs() {
78            constraints.push(LinearConstraint::eq(vec![(a, 1), (b, -1)], 0));
79        }
80
81        // Sink inflow requirement: sum_{a in delta^-(t)} f_a - sum_{a in delta^+(t)} f_a >= R
82        let mut sink_terms = Vec::new();
83        for (arc_idx, &(u, v)) in arcs.iter().enumerate() {
84            if v == self.sink() {
85                sink_terms.push((arc_idx, 1)); // incoming
86            }
87            if u == self.sink() {
88                sink_terms.push((arc_idx, -1)); // outgoing
89            }
90        }
91        constraints.push(LinearConstraint::ge(sink_terms, self.requirement()));
92
93        Ok(ReductionIFHAToILP {
94            target: ILP::new(num_arcs, constraints, vec![], ObjectiveSense::Minimize)
95                .map_err(Self::target_construction)?,
96        })
97    }
98}
99
100#[cfg(feature = "example-db")]
101pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
102    use crate::topology::DirectedGraph;
103
104    vec![crate::example_db::specs::RuleExampleSpec {
105        id: "integralflowhomologousarcs_to_ilp",
106        build: || {
107            let source = IntegralFlowHomologousArcs::new(
108                DirectedGraph::new(4, vec![(0, 1), (0, 2), (1, 3), (2, 3)]),
109                vec![2, 2, 2, 2],
110                0,
111                3,
112                2,
113                vec![(0, 1)],
114            );
115            crate::example_db::specs::rule_example_via_ilp::<_, i64>(source)
116        },
117    }]
118}
119
120#[cfg(test)]
121#[path = "../unit_tests/rules/integralflowhomologousarcs_ilp.rs"]
122mod tests;
problemreductions/rules/integralflowhomologousarcs_ilp.rs

problemreductions/rules/
integralflowhomologousarcs_ilp.rs
