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

problemreductions/models/graph/
minimum_edge_cost_flow.rs
