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<i32>,
15}
16
17impl ReductionResult for ReductionIFHAToILP {
18    type Source = IntegralFlowHomologousArcs;
19    type Target = ILP<i32>;
20
21    fn target_problem(&self) -> &ILP<i32> {
22        &self.target
23    }
24
25    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
26        target_solution.to_vec()
27    }
28}
29
30#[reduction(
31    overhead = {
32        num_vars = "num_arcs",
33        num_constraints = "num_arcs + num_vertices - 2 + 1",
34    }
35)]
36impl ReduceTo<ILP<i32>> for IntegralFlowHomologousArcs {
37    type Result = ReductionIFHAToILP;
38
39    fn reduce_to(&self) -> Self::Result {
40        let arcs = self.graph().arcs();
41        let num_arcs = self.num_arcs();
42        let num_vertices = self.num_vertices();
43        let mut constraints = Vec::new();
44
45        // Capacity: f_a <= c_a for each arc
46        for (arc_idx, &capacity) in self.capacities().iter().enumerate() {
47            constraints.push(LinearConstraint::le(vec![(arc_idx, 1.0)], capacity as f64));
48        }
49
50        // Conservation: sum_{a in delta^-(v)} f_a = sum_{a in delta^+(v)} f_a
51        // for all v in V \ {s, t}
52        for vertex in 0..num_vertices {
53            if vertex == self.source() || vertex == self.sink() {
54                continue;
55            }
56            let mut terms = Vec::new();
57            for (arc_idx, &(u, v)) in arcs.iter().enumerate() {
58                if v == vertex {
59                    terms.push((arc_idx, 1.0)); // incoming
60                }
61                if u == vertex {
62                    terms.push((arc_idx, -1.0)); // outgoing
63                }
64            }
65            constraints.push(LinearConstraint::eq(terms, 0.0));
66        }
67
68        // Homologous equality: f_a = f_b for each pair (a, b)
69        for &(a, b) in self.homologous_pairs() {
70            constraints.push(LinearConstraint::eq(vec![(a, 1.0), (b, -1.0)], 0.0));
71        }
72
73        // Sink inflow requirement: sum_{a in delta^-(t)} f_a - sum_{a in delta^+(t)} f_a >= R
74        let mut sink_terms = Vec::new();
75        for (arc_idx, &(u, v)) in arcs.iter().enumerate() {
76            if v == self.sink() {
77                sink_terms.push((arc_idx, 1.0)); // incoming
78            }
79            if u == self.sink() {
80                sink_terms.push((arc_idx, -1.0)); // outgoing
81            }
82        }
83        constraints.push(LinearConstraint::ge(sink_terms, self.requirement() as f64));
84
85        ReductionIFHAToILP {
86            target: ILP::new(num_arcs, constraints, vec![], ObjectiveSense::Minimize),
87        }
88    }
89}
90
91#[cfg(feature = "example-db")]
92pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
93    use crate::topology::DirectedGraph;
94
95    vec![crate::example_db::specs::RuleExampleSpec {
96        id: "integralflowhomologousarcs_to_ilp",
97        build: || {
98            let source = IntegralFlowHomologousArcs::new(
99                DirectedGraph::new(4, vec![(0, 1), (0, 2), (1, 3), (2, 3)]),
100                vec![2, 2, 2, 2],
101                0,
102                3,
103                2,
104                vec![(0, 1)],
105            );
106            crate::example_db::specs::rule_example_via_ilp::<_, i32>(source)
107        },
108    }]
109}
110
111#[cfg(test)]
112#[path = "../unit_tests/rules/integralflowhomologousarcs_ilp.rs"]
113mod tests;
problemreductions/rules/integralflowhomologousarcs_ilp.rs

problemreductions/rules/
integralflowhomologousarcs_ilp.rs
