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::{Bounded, IntegerVariable, LinearConstraint, ObjectiveSense, ILP};
7use crate::models::graph::IntegralFlowWithMultipliers;
8use crate::reduction;
9use crate::rules::ilp_helpers::bounded_flow_requirement;
10use crate::rules::traits::{ReduceTo, ReductionResult};
11
12/// Result of reducing IntegralFlowWithMultipliers to ILP.
13#[derive(Debug, Clone)]
14pub struct ReductionIFWMToILP {
15    target: ILP<i64, i64, Bounded>,
16}
17
18impl ReductionResult for ReductionIFWMToILP {
19    type Source = IntegralFlowWithMultipliers;
20    type Target = ILP<i64, i64, Bounded>;
21
22    fn target_problem(&self) -> &ILP<i64, i64, Bounded> {
23        &self.target
24    }
25
26    fn extract_solution(
27        &self,
28        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
29    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
30        crate::rules::traits::validate_target_witness(
31            self.target_problem(),
32            target_solution,
33            |value| value.value.is_some(),
34            "target ILP assignment is infeasible",
35        )?;
36
37        crate::rules::ilp_helpers::decode_usize_values(target_solution)
38    }
39}
40
41#[crate::aggregate_reduction(ilp_feasibility)]
42impl crate::rules::AggregateReductionResult for ReductionIFWMToILP {}
43
44#[reduction(transform = {
45    exact {
46        num_vars = "num_arcs",
47        num_constraints = "num_arcs + num_vertices - 1",
48    },
49    upper_bound {
50        max_constraint_magnitude_bits = "max_capacity_bits + num_arcs + 1",
51        num_nonzeros = "num_arcs * (num_arcs + num_vertices - 1)",
52    },
53})]
54impl ReduceTo<ILP<i64, i64, Bounded>> for IntegralFlowWithMultipliers {
55    type Result = ReductionIFWMToILP;
56
57    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
58        let arcs = self.graph().arcs();
59        let num_vertices = self.num_vertices();
60        let mut constraints = Vec::new();
61        let total_capacity = self
62            .capacities()
63            .iter()
64            .copied()
65            .fold(0_i64, i64::saturating_add);
66
67        // Capacity: f_a <= c_a for each arc
68        for (arc_idx, &capacity) in self.capacities().iter().enumerate() {
69            constraints.push(LinearConstraint::le(vec![(arc_idx, 1)], capacity));
70        }
71
72        // Multiplier-scaled conservation:
73        // sum_{a in delta^+(v)} f_a = h(v) * sum_{a in delta^-(v)} f_a
74        // for all v in V \ {s, t}
75        // Rewrite: sum_{a in delta^+(v)} f_a - h(v) * sum_{a in delta^-(v)} f_a = 0
76        for vertex in 0..num_vertices {
77            if vertex == self.source() || vertex == self.sink() {
78                continue;
79            }
80            // Outflow cannot exceed the total capacity S. A multiplier above
81            // S forces both integral inflow and outflow to zero, as does S+1.
82            let multiplier = self.multipliers()[vertex].min(total_capacity.saturating_add(1));
83            let mut terms = Vec::new();
84            for (arc_idx, &(u, v)) in arcs.iter().enumerate() {
85                if u == vertex {
86                    terms.push((arc_idx, 1)); // outgoing
87                }
88                if v == vertex {
89                    terms.push((arc_idx, -multiplier)); // incoming scaled by -h(v)
90                }
91            }
92            constraints.push(LinearConstraint::eq(terms, 0));
93        }
94
95        // Sink inflow requirement: sum_{a in delta^-(t)} f_a - sum_{a in delta^+(t)} f_a >= R
96        let mut sink_terms = Vec::new();
97        for (arc_idx, &(u, v)) in arcs.iter().enumerate() {
98            if v == self.sink() {
99                sink_terms.push((arc_idx, 1)); // incoming
100            }
101            if u == self.sink() {
102                sink_terms.push((arc_idx, -1)); // outgoing
103            }
104        }
105        let requirement = bounded_flow_requirement(self.requirement(), [total_capacity]);
106        constraints.push(LinearConstraint::ge(sink_terms, requirement));
107
108        let variables = self
109            .capacities()
110            .iter()
111            .copied()
112            .map(|capacity| IntegerVariable::new(Some(0), Some(capacity)))
113            .collect::<Result<Vec<_>, _>>()
114            .map_err(Self::target_construction)?;
115
116        Ok(ReductionIFWMToILP {
117            target: ILP::with_variables(variables, constraints, vec![], ObjectiveSense::Minimize)
118                .map_err(Self::target_construction)?,
119        })
120    }
121}
122
123#[cfg(feature = "example-db")]
124pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
125    use crate::topology::DirectedGraph;
126
127    vec![crate::example_db::specs::RuleExampleSpec {
128        id: "integralflowwithmultipliers_to_ilp",
129        build: || {
130            // Simple diamond: s=0, t=3, intermediate vertices 1,2 with multiplier 1
131            let source = IntegralFlowWithMultipliers::new(
132                DirectedGraph::new(4, vec![(0, 1), (0, 2), (1, 3), (2, 3)]),
133                0,
134                3,
135                vec![1, 1, 1, 1], // source/sink entries ignored
136                vec![2, 2, 2, 2],
137                2,
138            );
139            crate::example_db::specs::rule_example_via_bounded_ilp::<_>(source)
140        },
141    }]
142}
143
144#[cfg(test)]
145#[path = "../unit_tests/rules/integralflowwithmultipliers_ilp.rs"]
146mod tests;
problemreductions/rules/integralflowwithmultipliers_ilp.rs

problemreductions/rules/
integralflowwithmultipliers_ilp.rs
