problemreductions/models/graph/
minimum_cost_circulation.rs

1//! Minimum-Cost Circulation problem implementation.
2//!
3//! Given a directed multigraph `G = (V, A)` with arc capacities `c(a)`
4//! and **signed** arc costs `a(a)`, find a circulation `g` that
5//! minimizes the total cost
6//!
7//! `sum_{a in A} a(a) * g(a)`,
8//!
9//! subject to
10//!
11//! 1. `0 <= g(a) <= c(a)` for every arc `a`, and
12//! 2. inflow equals outflow at **every** vertex `v in V` (there is no
13//!    distinguished source or sink — this is the defining feature of a
14//!    circulation).
15//!
16//! Negative costs are explicitly allowed: with finite capacities every
17//! circulation has bounded cost, and negative-cost cycles are exactly
18//! what the standard reduction from min-cost max-flow uses (a single
19//! sufficiently negative return arc from the sink to the source).
20//!
21//! # Integral-circulation restriction
22//!
23//! The mathematical formulation in issue #1030 uses continuous flows
24//! `g: A -> R_{>= 0}`, but this model's registered reference solver uses a
25//! finite Cartesian space. Following the same precedent as
26//! [`MinimumEdgeCostFlow`](super::MinimumEdgeCostFlow) and
27//! the recently added [`MinimumCostMaximumFlow`](super::MinimumCostMaximumFlow),
28//! we therefore restrict to **integer** circulations: each variable
29//! `g(a)` ranges over `{0, 1, ..., c(a)}`. When capacities and costs are
30//! integral, the standard minimum-cost flow theory (see e.g. the MIT
31//! 6.854 notes, Ahuja-Magnanti-Orlin) guarantees that an integral
32//! optimum exists, so this restriction does not change the optimal value
33//! on integer instances.
34
35use crate::registry::{FieldInfo, ProblemSchemaEntry};
36use crate::topology::DirectedGraph;
37use crate::traits::Problem;
38use serde::{Deserialize, Serialize};
39
40inventory::submit! {
41    ProblemSchemaEntry {
42        name: "MinimumCostCirculation",
43        display_name: "Minimum-Cost Circulation",
44        aliases: &["MCC"],
45        dimensions: &[],
46        category: crate::registry::ProblemCategory::Graph,
47        module_path: module_path!(),
48        description: "Integral circulation on a directed multigraph minimizing total signed arc cost",
49        fields: &[
50            FieldInfo { name: "graph", type_name: "DirectedGraph", description: "Directed multigraph G = (V, A); loops and parallel arcs allowed" },
51            FieldInfo { name: "capacities", type_name: "Vec<i64>", description: "Arc capacity c(a) in graph arc order (non-negative)" },
52            FieldInfo { name: "costs", type_name: "Vec<i64>", description: "Signed arc cost a(a) in graph arc order (negative values allowed)" },
53        ],
54    }
55}
56
57/// Minimum-Cost Circulation problem.
58///
59/// # Variables
60///
61/// `|A|` variables: variable `a` ranges over `{0, ..., c(a)}`
62/// representing the integral circulation on arc `a`.
63///
64/// # Example
65///
66/// ```
67/// use problemreductions::models::graph::MinimumCostCirculation;
68/// use problemreductions::topology::DirectedGraph;
69/// use problemreductions::{Problem, BruteForce};
70///
71/// // Two competing cycles 0->1->0 and 0->2->0; the cheaper-per-unit
72/// // cycle 0->2->0 has lower capacity, but pushing both to capacity is
73/// // optimal.
74/// let graph = DirectedGraph::new(3, vec![
75///     (0, 1), (1, 0), (0, 2), (2, 0),
76/// ]);
77/// let problem = MinimumCostCirculation::new(
78///     graph,
79///     vec![2, 2, 1, 1],   // capacities
80///     vec![2, -3, 1, -4], // costs (signed)
81/// );
82/// let solver = BruteForce::new();
83/// let witness = solver.solve(&problem).unwrap().unwrap();
84/// // Optimal cost = 2*2 + 2*(-3) + 1*1 + 1*(-4) = -5.
85/// assert_eq!(problem.total_cost(&witness).unwrap(), -5);
86/// ```
87#[derive(Debug, Clone, Serialize, Deserialize)]
88#[serde(try_from = "MinimumCostCirculationData")]
89pub struct MinimumCostCirculation {
90    /// The directed multigraph G = (V, A).
91    graph: DirectedGraph,
92    /// Capacity c(a) for each arc.
93    capacities: Vec<i64>,
94    /// Signed cost a(a) for each arc.
95    costs: Vec<i64>,
96}
97
98#[derive(Deserialize)]
99struct MinimumCostCirculationData {
100    graph: DirectedGraph,
101    capacities: Vec<i64>,
102    costs: Vec<i64>,
103}
104
105impl TryFrom<MinimumCostCirculationData> for MinimumCostCirculation {
106    type Error = crate::registry::ConstructionError;
107    fn try_from(data: MinimumCostCirculationData) -> Result<Self, Self::Error> {
108        Self::try_new(data.graph, data.capacities, data.costs)
109    }
110}
111
112impl MinimumCostCirculation {
113    /// Create a new Minimum-Cost Circulation problem.
114    ///
115    /// # Panics
116    ///
117    /// Panics if any of the following holds:
118    /// - `capacities.len() != graph.num_arcs()`
119    /// - `costs.len() != graph.num_arcs()`
120    /// - Any capacity is negative
121    ///
122    /// Note: costs are signed and **may be negative**.
123    pub fn new(graph: DirectedGraph, capacities: Vec<i64>, costs: Vec<i64>) -> Self {
124        Self::try_new(graph, capacities, costs).unwrap_or_else(|error| panic!("{error}"))
125    }
126
127    fn try_new(
128        graph: DirectedGraph,
129        capacities: Vec<i64>,
130        costs: Vec<i64>,
131    ) -> Result<Self, crate::registry::ConstructionError> {
132        let m = graph.num_arcs();
133        if capacities.len() != m {
134            return Err(format!(
135                "capacities length ({}) must match num_arcs ({m})",
136                capacities.len()
137            )
138            .into());
139        }
140        if costs.len() != m {
141            return Err(format!("costs length ({}) must match num_arcs ({m})", costs.len()).into());
142        }
143        for (i, &c) in capacities.iter().enumerate() {
144            if c < 0 {
145                return Err(format!("capacity[{i}] = {c} is negative").into());
146            }
147        }
148        Ok(Self {
149            graph,
150            capacities,
151            costs,
152        })
153    }
154
155    /// Get a reference to the underlying directed graph.
156    pub fn graph(&self) -> &DirectedGraph {
157        &self.graph
158    }
159
160    /// Get a reference to the arc capacities.
161    pub fn capacities(&self) -> &[i64] {
162        &self.capacities
163    }
164
165    /// Get a reference to the arc costs (signed).
166    pub fn costs(&self) -> &[i64] {
167        &self.costs
168    }
169
170    /// Get the number of vertices `|V|`.
171    pub fn num_vertices(&self) -> usize {
172        self.graph.num_vertices()
173    }
174
175    /// Get the number of arcs `|A|`.
176    pub fn num_arcs(&self) -> usize {
177        self.graph.num_arcs()
178    }
179
180    /// Check whether a circulation assignment is feasible.
181    ///
182    /// A circulation is feasible iff
183    /// 1. `config.len() == num_arcs`,
184    /// 2. each `0 <= g(a) <= c(a)`, and
185    /// 3. inflow equals outflow at **every** vertex (no exempt
186    ///    terminals — this is what distinguishes a circulation from a
187    ///    flow).
188    pub fn is_feasible(&self, config: &[usize]) -> Result<bool, crate::traits::EvaluationError> {
189        let m = self.graph.num_arcs();
190        if config.len() != m {
191            return Ok(false);
192        }
193        // (1) Capacity constraints
194        for (flow, cap) in config.iter().zip(self.capacities.iter()) {
195            let flow = i64::try_from(*flow).map_err(|_| {
196                crate::traits::EvaluationError::IntegerOverflow(
197                    "converting circulation configuration value".to_string(),
198                )
199            })?;
200            if flow > *cap {
201                return Ok(false);
202            }
203        }
204        // (2) Flow conservation at every vertex
205        let n = self.graph.num_vertices();
206        let mut balance = vec![0_i64; n];
207        for (a, &(u, v)) in self.graph.arcs().iter().enumerate() {
208            let flow = i64::try_from(config[a]).map_err(|_| {
209                crate::traits::EvaluationError::IntegerOverflow(
210                    "converting circulation configuration value".to_string(),
211                )
212            })?;
213            balance[u] = balance[u].checked_sub(flow).ok_or_else(|| {
214                crate::traits::EvaluationError::IntegerOverflow(
215                    "computing circulation vertex balance".to_string(),
216                )
217            })?;
218            balance[v] = balance[v].checked_add(flow).ok_or_else(|| {
219                crate::traits::EvaluationError::IntegerOverflow(
220                    "computing circulation vertex balance".to_string(),
221                )
222            })?;
223        }
224        Ok(balance.iter().all(|&b| b == 0))
225    }
226
227    /// Compute the total cost `sum_a a(a) * g(a)` of a circulation.
228    pub fn total_cost(&self, config: &[usize]) -> Result<i64, crate::traits::EvaluationError> {
229        let mut total = 0_i64;
230        for (&flow, &cost) in config.iter().zip(self.costs.iter()) {
231            let flow = i64::try_from(flow).map_err(|_| {
232                crate::traits::EvaluationError::IntegerOverflow(
233                    "converting circulation configuration value".to_string(),
234                )
235            })?;
236            let term = flow.checked_mul(cost).ok_or_else(|| {
237                crate::traits::EvaluationError::IntegerOverflow(
238                    "multiplying circulation arc cost".to_string(),
239                )
240            })?;
241            total = total.checked_add(term).ok_or_else(|| {
242                crate::traits::EvaluationError::IntegerOverflow(
243                    "summing circulation costs".to_string(),
244                )
245            })?;
246        }
247        Ok(total)
248    }
249}
250
251impl Problem for MinimumCostCirculation {
252    const NAME: &'static str = "MinimumCostCirculation";
253    type Solution = Vec<usize>;
254    type Value = crate::types::Min<i64>;
255
256    crate::problem_parameters![("num_arcs", num_arcs), ("num_vertices", num_vertices),];
257
258    fn evaluate(
259        &self,
260        config: &Self::Solution,
261    ) -> Result<crate::types::Min<i64>, crate::traits::EvaluationError> {
262        if config.len() != self.graph.num_arcs() {
263            return Err(crate::traits::EvaluationError::InvalidConfiguration(
264                "flow vector length does not match the graph arcs".into(),
265            ));
266        }
267        Ok({
268            if !self.is_feasible(config)? {
269                return Ok(crate::types::Min(None));
270            }
271            crate::types::Min(Some(self.total_cost(config)?))
272        })
273    }
274
275    fn variant() -> Vec<(&'static str, &'static str)> {
276        crate::variant_params![]
277    }
278}
279
280impl crate::solvers::BruteForceProblem for MinimumCostCirculation {
281    fn dimensions(&self) -> Vec<usize> {
282        self.capacities.iter().map(|&c| (c as usize) + 1).collect()
283    }
284}
285
286crate::declare_variants! {
287    default MinimumCostCirculation => "(num_vertices + num_arcs)^6",
288}
289
290crate::register_brute_force! {
291    MinimumCostCirculation,
292}
293
294#[cfg(feature = "example-db")]
295pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
296    // Two competing cycles on V = {0, 1, 2}:
297    //   cycle A: 0->1->0  (cost per unit = 2 + (-3) = -1, capacity 2)
298    //   cycle B: 0->2->0  (cost per unit = 1 + (-4) = -3, capacity 1)
299    // Optimal: push both to capacity.
300    //   arc 0 (0->1) = 2, arc 1 (1->0) = 2, arc 2 (0->2) = 1, arc 3 (2->0) = 1
301    //   cost = 2*2 + 2*(-3) + 1*1 + 1*(-4) = 4 - 6 + 1 - 4 = -5
302    let problem = MinimumCostCirculation::new(
303        crate::topology::DirectedGraph::new(3, vec![(0, 1), (1, 0), (0, 2), (2, 0)]),
304        vec![2, 2, 1, 1],
305        vec![2, -3, 1, -4],
306    );
307    let optimal_config = vec![2, 2, 1, 1];
308    let optimal_value = problem
309        .evaluate(&optimal_config)
310        .expect("canonical example evaluation must succeed");
311    let scalar = match optimal_value {
312        crate::types::Min(Some(v)) => v,
313        crate::types::Min(None) => panic!("canonical example must be feasible"),
314    };
315    vec![crate::example_db::specs::ModelExampleSpec {
316        id: "minimum_cost_circulation",
317        instance: Box::new(problem),
318        optimal_config: serde_json::to_value(optimal_config)
319            .expect("solution serialization must succeed"),
320        optimal_value: serde_json::json!(scalar),
321    }]
322}
323
324#[cfg(test)]
325#[path = "../../unit_tests/models/graph/minimum_cost_circulation.rs"]
326mod tests;
problemreductions/models/graph/minimum_cost_circulation.rs

problemreductions/models/graph/
minimum_cost_circulation.rs
