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::{Bounded, IntegerVariable, 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, i64, Bounded>,
15}
16
17impl ReductionResult for ReductionIFHAToILP {
18    type Source = IntegralFlowHomologousArcs;
19    type Target = ILP<i64, i64, Bounded>;
20
21    fn target_problem(&self) -> &ILP<i64, i64, Bounded> {
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_witness(
30            self.target_problem(),
31            target_solution,
32            |value| value.value.is_some(),
33            "target ILP assignment is infeasible",
34        )?;
35
36        crate::rules::ilp_helpers::decode_usize_values(target_solution)
37    }
38}
39
40#[crate::aggregate_reduction(ilp_feasibility)]
41impl crate::rules::AggregateReductionResult for ReductionIFHAToILP {}
42
43// Capacity rows contribute m terms; conservation plus sink balance use at
44// most 2m; each declared homologous pair contributes at most two. Duplicate
45// pairs retain separate rows, while self-loops and (a,a) pairs cancel terms.
46// The clamped requirement has magnitude at most sum(capacities)+1, whose
47// bits are at most h+bit_length(m) <= h+ceil(m/2+1); m=0 is also covered.
48#[reduction(
49    transform = upper_bound {
50        max_constraint_magnitude_bits = "max_capacity_bits + num_arcs / 2 + 1",
51        num_vars = "num_arcs",
52        num_constraints = "num_arcs + num_vertices + num_homologous_pairs",
53        num_nonzeros = "3 * num_arcs + 2 * num_homologous_pairs",
54    },
55)]
56impl ReduceTo<ILP<i64, i64, Bounded>> for IntegralFlowHomologousArcs {
57    type Result = ReductionIFHAToILP;
58
59    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
60        let arcs = self.graph().arcs();
61        let num_vertices = self.num_vertices();
62        let mut constraints = Vec::new();
63
64        // Capacity: f_a <= c_a for each arc
65        for (arc_idx, &capacity) in self.capacities().iter().enumerate() {
66            constraints.push(LinearConstraint::le(vec![(arc_idx, 1)], capacity));
67        }
68
69        // Conservation: sum_{a in delta^-(v)} f_a = sum_{a in delta^+(v)} f_a
70        // for all v in V \ {s, t}
71        for vertex in 0..num_vertices {
72            if vertex == self.source() || vertex == self.sink() {
73                continue;
74            }
75            let mut terms = Vec::new();
76            for (arc_idx, &(u, v)) in arcs.iter().enumerate() {
77                if v == vertex {
78                    terms.push((arc_idx, 1)); // incoming
79                }
80                if u == vertex {
81                    terms.push((arc_idx, -1)); // outgoing
82                }
83            }
84            constraints.push(LinearConstraint::eq(terms, 0));
85        }
86
87        // Homologous equality: f_a = f_b for each pair (a, b)
88        for &(a, b) in self.homologous_pairs() {
89            constraints.push(LinearConstraint::eq(vec![(a, 1), (b, -1)], 0));
90        }
91
92        // Sink inflow requirement: sum_{a in delta^-(t)} f_a - sum_{a in delta^+(t)} f_a >= R
93        let mut sink_terms = Vec::new();
94        for (arc_idx, &(u, v)) in arcs.iter().enumerate() {
95            if v == self.sink() {
96                sink_terms.push((arc_idx, 1)); // incoming
97            }
98            if u == self.sink() {
99                sink_terms.push((arc_idx, -1)); // outgoing
100            }
101        }
102        constraints.push(LinearConstraint::ge(
103            sink_terms,
104            crate::rules::ilp_helpers::bounded_flow_requirement(
105                self.requirement(),
106                self.capacities().iter().copied(),
107            ),
108        ));
109
110        let variables = self
111            .capacities()
112            .iter()
113            .copied()
114            .map(|capacity| IntegerVariable::new(Some(0), Some(capacity)))
115            .collect::<Result<Vec<_>, _>>()
116            .map_err(Self::target_construction)?;
117
118        Ok(ReductionIFHAToILP {
119            target: ILP::with_variables(variables, constraints, vec![], ObjectiveSense::Minimize)
120                .map_err(Self::target_construction)?,
121        })
122    }
123}
124
125#[cfg(feature = "example-db")]
126pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
127    use crate::topology::DirectedGraph;
128
129    vec![crate::example_db::specs::RuleExampleSpec {
130        id: "integralflowhomologousarcs_to_ilp",
131        build: || {
132            let source = IntegralFlowHomologousArcs::new(
133                DirectedGraph::new(4, vec![(0, 1), (0, 2), (1, 3), (2, 3)]),
134                vec![2, 2, 2, 2],
135                0,
136                3,
137                2,
138                vec![(0, 1)],
139            );
140            crate::example_db::specs::rule_example_via_bounded_ilp::<_>(source)
141        },
142    }]
143}
144
145#[cfg(test)]
146#[path = "../unit_tests/rules/integralflowhomologousarcs_ilp.rs"]
147mod tests;
problemreductions/rules/integralflowhomologousarcs_ilp.rs

problemreductions/rules/
integralflowhomologousarcs_ilp.rs
