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<i32>,
15}
16
17impl ReductionResult for ReductionIFWMToILP {
18    type Source = IntegralFlowWithMultipliers;
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 - 1",
34    }
35)]
36impl ReduceTo<ILP<i32>> for IntegralFlowWithMultipliers {
37    type Result = ReductionIFWMToILP;
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        // Multiplier-scaled conservation:
51        // sum_{a in delta^+(v)} f_a = h(v) * sum_{a in delta^-(v)} f_a
52        // for all v in V \ {s, t}
53        // Rewrite: sum_{a in delta^+(v)} f_a - h(v) * sum_{a in delta^-(v)} f_a = 0
54        for vertex in 0..num_vertices {
55            if vertex == self.source() || vertex == self.sink() {
56                continue;
57            }
58            let multiplier = self.multipliers()[vertex] as f64;
59            let mut terms = Vec::new();
60            for (arc_idx, &(u, v)) in arcs.iter().enumerate() {
61                if u == vertex {
62                    terms.push((arc_idx, 1.0)); // outgoing
63                }
64                if v == vertex {
65                    terms.push((arc_idx, -multiplier)); // incoming scaled by -h(v)
66                }
67            }
68            constraints.push(LinearConstraint::eq(terms, 0.0));
69        }
70
71        // Sink inflow requirement: sum_{a in delta^-(t)} f_a - sum_{a in delta^+(t)} f_a >= R
72        let mut sink_terms = Vec::new();
73        for (arc_idx, &(u, v)) in arcs.iter().enumerate() {
74            if v == self.sink() {
75                sink_terms.push((arc_idx, 1.0)); // incoming
76            }
77            if u == self.sink() {
78                sink_terms.push((arc_idx, -1.0)); // outgoing
79            }
80        }
81        constraints.push(LinearConstraint::ge(sink_terms, self.requirement() as f64));
82
83        ReductionIFWMToILP {
84            target: ILP::new(num_arcs, constraints, vec![], ObjectiveSense::Minimize),
85        }
86    }
87}
88
89#[cfg(feature = "example-db")]
90pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
91    use crate::topology::DirectedGraph;
92
93    vec![crate::example_db::specs::RuleExampleSpec {
94        id: "integralflowwithmultipliers_to_ilp",
95        build: || {
96            // Simple diamond: s=0, t=3, intermediate vertices 1,2 with multiplier 1
97            let source = IntegralFlowWithMultipliers::new(
98                DirectedGraph::new(4, vec![(0, 1), (0, 2), (1, 3), (2, 3)]),
99                0,
100                3,
101                vec![1, 1, 1, 1], // source/sink entries ignored
102                vec![2, 2, 2, 2],
103                2,
104            );
105            crate::example_db::specs::rule_example_via_ilp::<_, i32>(source)
106        },
107    }]
108}
109
110#[cfg(test)]
111#[path = "../unit_tests/rules/integralflowwithmultipliers_ilp.rs"]
112mod tests;
problemreductions/rules/integralflowwithmultipliers_ilp.rs

problemreductions/rules/
integralflowwithmultipliers_ilp.rs
