problemreductions/rules/
minimumedgecostflow_ilp.rs

1//! Reduction from MinimumEdgeCostFlow to ILP<i32>.
2//!
3//! Variables (2m total):
4//!   f_a  (a = 0..m-1)  — integer flow on arc a, domain {0, ..., c(a)}
5//!   y_a  (a = m..2m-1) — binary indicator: y_a = 1 iff f_a > 0
6//!
7//! Constraints:
8//!   f_a ≤ c(a)          — capacity (m constraints)
9//!   f_a ≤ c(a) · y_a    — linking: forces y_a = 1 when f_a > 0 (m constraints)
10//!   y_a ≤ 1             — binary bound on indicators (m constraints)
11//!   conservation at non-terminal vertices (|V|-2 equality constraints)
12//!   net flow into sink ≥ R (1 constraint)
13//!
14//! Total: 3m + |V| - 1 constraints (but we omit redundant capacity since
15//! linking already implies f_a ≤ c(a) when y_a ≤ 1).
16//! Actually we keep all for clarity: 2m + |V| - 1 constraints.
17//!
18//! Objective: minimize Σ p(a) · y_a.
19//! Extraction: first m variables are the flow values.
20
21use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
22use crate::models::graph::MinimumEdgeCostFlow;
23use crate::reduction;
24use crate::rules::traits::{ReduceTo, ReductionResult};
25
26/// Result of reducing MinimumEdgeCostFlow to ILP<i32>.
27///
28/// Variable layout:
29/// - `f_a` at index a for a in 0..num_edges (flow on arc a)
30/// - `y_a` at index num_edges + a for a in 0..num_edges (binary indicator)
31#[derive(Debug, Clone)]
32pub struct ReductionMECFToILP {
33    target: ILP<i32>,
34    num_edges: usize,
35}
36
37impl ReductionResult for ReductionMECFToILP {
38    type Source = MinimumEdgeCostFlow;
39    type Target = ILP<i32>;
40
41    fn target_problem(&self) -> &ILP<i32> {
42        &self.target
43    }
44
45    /// Extract flow solution: first m variables are the flow values.
46    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
47        target_solution[..self.num_edges].to_vec()
48    }
49}
50
51#[reduction(
52    overhead = {
53        num_vars = "2 * num_edges",
54        num_constraints = "2 * num_edges + num_vertices - 1",
55    }
56)]
57impl ReduceTo<ILP<i32>> for MinimumEdgeCostFlow {
58    type Result = ReductionMECFToILP;
59
60    fn reduce_to(&self) -> Self::Result {
61        let arcs = self.graph().arcs();
62        let m = arcs.len();
63        let n = self.num_vertices();
64        let num_vars = 2 * m;
65
66        let f = |a: usize| a; // flow variable index
67        let y = |a: usize| m + a; // indicator variable index
68
69        let mut constraints = Vec::new();
70
71        // 1. Linking: f_a - c(a) * y_a ≤ 0  (forces y_a = 1 when f_a > 0)
72        for a in 0..m {
73            constraints.push(LinearConstraint::le(
74                vec![(f(a), 1.0), (y(a), -(self.capacities()[a] as f64))],
75                0.0,
76            ));
77        }
78
79        // 2. Binary bound: y_a ≤ 1
80        for a in 0..m {
81            constraints.push(LinearConstraint::le(vec![(y(a), 1.0)], 1.0));
82        }
83
84        // 3. Flow conservation at non-terminal vertices
85        for vertex in 0..n {
86            if vertex == self.source() || vertex == self.sink() {
87                continue;
88            }
89
90            let mut terms: Vec<(usize, f64)> = Vec::new();
91            for (a, &(u, v)) in arcs.iter().enumerate() {
92                if vertex == u {
93                    terms.push((f(a), -1.0)); // outgoing
94                } else if vertex == v {
95                    terms.push((f(a), 1.0)); // incoming
96                }
97            }
98
99            if !terms.is_empty() {
100                constraints.push(LinearConstraint::eq(terms, 0.0));
101            }
102        }
103
104        // 4. Flow requirement: net flow into sink ≥ R
105        let sink = self.sink();
106        let mut sink_terms: Vec<(usize, f64)> = Vec::new();
107        for (a, &(u, v)) in arcs.iter().enumerate() {
108            if v == sink {
109                sink_terms.push((f(a), 1.0));
110            } else if u == sink {
111                sink_terms.push((f(a), -1.0));
112            }
113        }
114        constraints.push(LinearConstraint::ge(
115            sink_terms,
116            self.required_flow() as f64,
117        ));
118
119        // Objective: minimize Σ p(a) · y_a
120        let objective: Vec<(usize, f64)> =
121            (0..m).map(|a| (y(a), self.prices()[a] as f64)).collect();
122
123        ReductionMECFToILP {
124            target: ILP::new(num_vars, constraints, objective, ObjectiveSense::Minimize),
125            num_edges: m,
126        }
127    }
128}
129
130#[cfg(feature = "example-db")]
131pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
132    use crate::topology::DirectedGraph;
133
134    vec![crate::example_db::specs::RuleExampleSpec {
135        id: "minimumedgecostflow_to_ilp",
136        build: || {
137            let source = MinimumEdgeCostFlow::new(
138                DirectedGraph::new(5, vec![(0, 1), (0, 2), (0, 3), (1, 4), (2, 4), (3, 4)]),
139                vec![3, 1, 2, 0, 0, 0],
140                vec![2, 2, 2, 2, 2, 2],
141                0,
142                4,
143                3,
144            );
145            crate::example_db::specs::rule_example_via_ilp::<_, i32>(source)
146        },
147    }]
148}
149
150#[cfg(test)]
151#[path = "../unit_tests/rules/minimumedgecostflow_ilp.rs"]
152mod tests;
problemreductions/rules/minimumedgecostflow_ilp.rs

problemreductions/rules/
minimumedgecostflow_ilp.rs
