problemreductions/models/graph/
minimum_edge_cost_flow.rs

1//! Minimum Edge-Cost Flow problem implementation.
2//!
3//! Given a directed graph G = (V, A) with arc capacities c(a) and prices p(a),
4//! a source s, a sink t, and a flow requirement R, find an integral flow of
5//! value at least R that minimizes the total edge cost — the sum of prices of
6//! arcs carrying nonzero flow.
7//!
8//! This is NP-hard: it generalizes Minimum-Weight Satisfiability via reduction
9//! from Minimum Edge-Cost Flow on DAGs (Amaldi et al., 2011).
10
11use crate::registry::{FieldInfo, ProblemSchemaEntry};
12use crate::topology::DirectedGraph;
13use crate::traits::Problem;
14use serde::{Deserialize, Serialize};
15
16inventory::submit! {
17    ProblemSchemaEntry {
18        name: "MinimumEdgeCostFlow",
19        display_name: "Minimum Edge-Cost Flow",
20        aliases: &["MECF"],
21        dimensions: &[],
22        module_path: module_path!(),
23        description: "Integral flow minimizing the number of arcs with nonzero flow (weighted by price)",
24        fields: &[
25            FieldInfo { name: "graph", type_name: "DirectedGraph", description: "Directed graph G = (V, A)" },
26            FieldInfo { name: "prices", type_name: "Vec<i64>", description: "Price p(a) for each arc" },
27            FieldInfo { name: "capacities", type_name: "Vec<i64>", description: "Capacity c(a) for each arc" },
28            FieldInfo { name: "source", type_name: "usize", description: "Source vertex s" },
29            FieldInfo { name: "sink", type_name: "usize", description: "Sink vertex t" },
30            FieldInfo { name: "required_flow", type_name: "i64", description: "Flow requirement R" },
31        ],
32    }
33}
34
35/// Minimum Edge-Cost Flow problem.
36///
37/// Given a directed graph G = (V, A) with arc capacities c(a) and prices p(a),
38/// source s, sink t, and flow requirement R, find an integral flow f: A -> Z_0^+
39/// of value at least R minimizing the total edge cost sum_{a: f(a)>0} p(a).
40///
41/// # Variables
42///
43/// |A| variables: variable a ranges over {0, ..., c(a)} representing the flow
44/// on arc a.
45///
46/// # Example
47///
48/// ```
49/// use problemreductions::models::graph::MinimumEdgeCostFlow;
50/// use problemreductions::topology::DirectedGraph;
51/// use problemreductions::{Problem, Solver, BruteForce};
52///
53/// // 5-vertex network: s=0, t=4, R=3
54/// let graph = DirectedGraph::new(5, vec![
55///     (0, 1), (0, 2), (0, 3), (1, 4), (2, 4), (3, 4),
56/// ]);
57/// let problem = MinimumEdgeCostFlow::new(
58///     graph,
59///     vec![3, 1, 2, 0, 0, 0], // prices
60///     vec![2, 2, 2, 2, 2, 2], // capacities
61///     0, 4, 3,
62/// );
63/// let solver = BruteForce::new();
64/// let witness = solver.find_witness(&problem).unwrap();
65/// assert_eq!(problem.evaluate(&witness), problemreductions::types::Min(Some(3)));
66/// ```
67#[derive(Debug, Clone, Serialize, Deserialize)]
68pub struct MinimumEdgeCostFlow {
69    /// The directed graph G = (V, A).
70    graph: DirectedGraph,
71    /// Price p(a) for each arc.
72    prices: Vec<i64>,
73    /// Capacity c(a) for each arc.
74    capacities: Vec<i64>,
75    /// Source vertex s.
76    source: usize,
77    /// Sink vertex t.
78    sink: usize,
79    /// Flow requirement R.
80    required_flow: i64,
81}
82
83impl MinimumEdgeCostFlow {
84    /// Create a new Minimum Edge-Cost Flow problem.
85    ///
86    /// # Arguments
87    ///
88    /// * `graph` - Directed graph G = (V, A)
89    /// * `prices` - Price p(a) for each arc (one per arc)
90    /// * `capacities` - Capacity c(a) for each arc (one per arc, all non-negative)
91    /// * `source` - Source vertex index
92    /// * `sink` - Sink vertex index
93    /// * `required_flow` - Minimum flow requirement R
94    ///
95    /// # Panics
96    ///
97    /// Panics if:
98    /// - `prices.len() != graph.num_arcs()`
99    /// - `capacities.len() != graph.num_arcs()`
100    /// - `source >= graph.num_vertices()`
101    /// - `sink >= graph.num_vertices()`
102    /// - `source == sink`
103    /// - Any capacity is negative
104    pub fn new(
105        graph: DirectedGraph,
106        prices: Vec<i64>,
107        capacities: Vec<i64>,
108        source: usize,
109        sink: usize,
110        required_flow: i64,
111    ) -> Self {
112        let n = graph.num_vertices();
113        let m = graph.num_arcs();
114        assert_eq!(
115            prices.len(),
116            m,
117            "prices length ({}) must match num_arcs ({m})",
118            prices.len()
119        );
120        assert_eq!(
121            capacities.len(),
122            m,
123            "capacities length ({}) must match num_arcs ({m})",
124            capacities.len()
125        );
126        assert!(source < n, "source ({source}) >= num_vertices ({n})");
127        assert!(sink < n, "sink ({sink}) >= num_vertices ({n})");
128        assert_ne!(source, sink, "source and sink must be distinct");
129        for (i, &c) in capacities.iter().enumerate() {
130            assert!(c >= 0, "capacity[{i}] = {c} is negative");
131        }
132        Self {
133            graph,
134            prices,
135            capacities,
136            source,
137            sink,
138            required_flow,
139        }
140    }
141
142    /// Get a reference to the underlying directed graph.
143    pub fn graph(&self) -> &DirectedGraph {
144        &self.graph
145    }
146
147    /// Get a reference to the prices.
148    pub fn prices(&self) -> &[i64] {
149        &self.prices
150    }
151
152    /// Get a reference to the capacities.
153    pub fn capacities(&self) -> &[i64] {
154        &self.capacities
155    }
156
157    /// Get the source vertex.
158    pub fn source(&self) -> usize {
159        self.source
160    }
161
162    /// Get the sink vertex.
163    pub fn sink(&self) -> usize {
164        self.sink
165    }
166
167    /// Get the flow requirement.
168    pub fn required_flow(&self) -> i64 {
169        self.required_flow
170    }
171
172    /// Get the number of vertices.
173    pub fn num_vertices(&self) -> usize {
174        self.graph.num_vertices()
175    }
176
177    /// Get the number of edges (arcs).
178    pub fn num_edges(&self) -> usize {
179        self.graph.num_arcs()
180    }
181
182    /// Get the maximum capacity across all arcs (0 if empty).
183    pub fn max_capacity(&self) -> i64 {
184        self.capacities.iter().copied().max().unwrap_or(0)
185    }
186
187    /// Get a reference to the edges (arcs).
188    pub fn edges(&self) -> Vec<(usize, usize)> {
189        self.graph.arcs()
190    }
191
192    /// Check whether a flow assignment is feasible.
193    ///
194    /// A flow is feasible if:
195    /// 1. Each arc's flow does not exceed its capacity
196    /// 2. Flow is conserved at every non-terminal vertex
197    /// 3. Net flow into the sink is at least the required flow
198    pub fn is_feasible(&self, config: &[usize]) -> bool {
199        let m = self.graph.num_arcs();
200        if config.len() != m {
201            return false;
202        }
203        let arcs = self.graph.arcs();
204
205        // (1) Capacity constraints
206        for (flow, cap) in config.iter().zip(self.capacities.iter()) {
207            if (*flow as i64) > *cap {
208                return false;
209            }
210        }
211
212        // (2) Flow conservation at non-terminal vertices
213        let n = self.graph.num_vertices();
214        let mut balance = vec![0_i64; n];
215        for (a, &(u, v)) in arcs.iter().enumerate() {
216            let flow = config[a] as i64;
217            balance[u] -= flow;
218            balance[v] += flow;
219        }
220
221        for (v, &bal) in balance.iter().enumerate() {
222            if v != self.source && v != self.sink && bal != 0 {
223                return false;
224            }
225        }
226
227        // (3) Flow requirement: net flow into sink >= R
228        if balance[self.sink] < self.required_flow {
229            return false;
230        }
231
232        true
233    }
234
235    /// Compute the edge cost for a feasible flow: sum of prices of arcs with
236    /// nonzero flow.
237    pub fn edge_cost(&self, config: &[usize]) -> i64 {
238        config
239            .iter()
240            .enumerate()
241            .filter(|(_, &f)| f > 0)
242            .map(|(a, _)| self.prices[a])
243            .sum()
244    }
245}
246
247impl Problem for MinimumEdgeCostFlow {
248    const NAME: &'static str = "MinimumEdgeCostFlow";
249    type Value = crate::types::Min<i64>;
250
251    fn dims(&self) -> Vec<usize> {
252        self.capacities.iter().map(|&c| (c as usize) + 1).collect()
253    }
254
255    fn evaluate(&self, config: &[usize]) -> crate::types::Min<i64> {
256        if self.is_feasible(config) {
257            crate::types::Min(Some(self.edge_cost(config)))
258        } else {
259            crate::types::Min(None)
260        }
261    }
262
263    fn variant() -> Vec<(&'static str, &'static str)> {
264        crate::variant_params![]
265    }
266}
267
268crate::declare_variants! {
269    default MinimumEdgeCostFlow => "(max_capacity + 1)^num_edges",
270}
271
272#[cfg(feature = "example-db")]
273pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
274    vec![crate::example_db::specs::ModelExampleSpec {
275        id: "minimum_edge_cost_flow",
276        instance: Box::new(MinimumEdgeCostFlow::new(
277            crate::topology::DirectedGraph::new(
278                5,
279                vec![(0, 1), (0, 2), (0, 3), (1, 4), (2, 4), (3, 4)],
280            ),
281            vec![3, 1, 2, 0, 0, 0], // prices
282            vec![2, 2, 2, 2, 2, 2], // capacities
283            0,
284            4,
285            3,
286        )),
287        // Optimal: route 1 unit via v2 and 2 units via v3 → cost = 1 + 2 = 3
288        // config = [0, 1, 2, 0, 1, 2]
289        optimal_config: vec![0, 1, 2, 0, 1, 2],
290        optimal_value: serde_json::json!(3),
291    }]
292}
293
294#[cfg(test)]
295#[path = "../../unit_tests/models/graph/minimum_edge_cost_flow.rs"]
296mod tests;
problemreductions/models/graph/minimum_edge_cost_flow.rs

problemreductions/models/graph/
minimum_edge_cost_flow.rs
