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 the [`Problem`] trait requires a discrete
25//! configuration space via [`Problem::dims`]. Following the same
26//! precedent as [`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, ProblemSizeFieldEntry};
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        module_path: module_path!(),
47        description: "Integral circulation on a directed multigraph minimizing total signed arc cost",
48        fields: &[
49            FieldInfo { name: "graph", type_name: "DirectedGraph", description: "Directed multigraph G = (V, A); loops and parallel arcs allowed" },
50            FieldInfo { name: "capacities", type_name: "Vec<i64>", description: "Arc capacity c(a) in graph arc order (non-negative)" },
51            FieldInfo { name: "costs", type_name: "Vec<i64>", description: "Signed arc cost a(a) in graph arc order (negative values allowed)" },
52        ],
53    }
54}
55
56inventory::submit! {
57    ProblemSizeFieldEntry {
58        name: "MinimumCostCirculation",
59        fields: &["num_vertices", "num_arcs"],
60    }
61}
62
63/// Minimum-Cost Circulation problem.
64///
65/// # Variables
66///
67/// `|A|` variables: variable `a` ranges over `{0, ..., c(a)}`
68/// representing the integral circulation on arc `a`.
69///
70/// # Example
71///
72/// ```
73/// use problemreductions::models::graph::MinimumCostCirculation;
74/// use problemreductions::topology::DirectedGraph;
75/// use problemreductions::{Problem, Solver, BruteForce};
76///
77/// // Two competing cycles 0->1->0 and 0->2->0; the cheaper-per-unit
78/// // cycle 0->2->0 has lower capacity, but pushing both to capacity is
79/// // optimal.
80/// let graph = DirectedGraph::new(3, vec![
81///     (0, 1), (1, 0), (0, 2), (2, 0),
82/// ]);
83/// let problem = MinimumCostCirculation::new(
84///     graph,
85///     vec![2, 2, 1, 1],   // capacities
86///     vec![2, -3, 1, -4], // costs (signed)
87/// );
88/// let solver = BruteForce::new();
89/// let witness = solver.find_witness(&problem).unwrap();
90/// // Optimal cost = 2*2 + 2*(-3) + 1*1 + 1*(-4) = -5.
91/// assert_eq!(problem.total_cost(&witness), -5);
92/// ```
93#[derive(Debug, Clone, Serialize, Deserialize)]
94pub struct MinimumCostCirculation {
95    /// The directed multigraph G = (V, A).
96    graph: DirectedGraph,
97    /// Capacity c(a) for each arc.
98    capacities: Vec<i64>,
99    /// Signed cost a(a) for each arc.
100    costs: Vec<i64>,
101}
102
103impl MinimumCostCirculation {
104    /// Create a new Minimum-Cost Circulation problem.
105    ///
106    /// # Panics
107    ///
108    /// Panics if any of the following holds:
109    /// - `capacities.len() != graph.num_arcs()`
110    /// - `costs.len() != graph.num_arcs()`
111    /// - Any capacity is negative
112    ///
113    /// Note: costs are signed and **may be negative**.
114    pub fn new(graph: DirectedGraph, capacities: Vec<i64>, costs: Vec<i64>) -> Self {
115        let m = graph.num_arcs();
116        assert_eq!(
117            capacities.len(),
118            m,
119            "capacities length ({}) must match num_arcs ({m})",
120            capacities.len()
121        );
122        assert_eq!(
123            costs.len(),
124            m,
125            "costs length ({}) must match num_arcs ({m})",
126            costs.len()
127        );
128        for (i, &c) in capacities.iter().enumerate() {
129            assert!(c >= 0, "capacity[{i}] = {c} is negative");
130        }
131        Self {
132            graph,
133            capacities,
134            costs,
135        }
136    }
137
138    /// Get a reference to the underlying directed graph.
139    pub fn graph(&self) -> &DirectedGraph {
140        &self.graph
141    }
142
143    /// Get a reference to the arc capacities.
144    pub fn capacities(&self) -> &[i64] {
145        &self.capacities
146    }
147
148    /// Get a reference to the arc costs (signed).
149    pub fn costs(&self) -> &[i64] {
150        &self.costs
151    }
152
153    /// Get the number of vertices `|V|`.
154    pub fn num_vertices(&self) -> usize {
155        self.graph.num_vertices()
156    }
157
158    /// Get the number of arcs `|A|`.
159    pub fn num_arcs(&self) -> usize {
160        self.graph.num_arcs()
161    }
162
163    /// Check whether a circulation assignment is feasible.
164    ///
165    /// A circulation is feasible iff
166    /// 1. `config.len() == num_arcs`,
167    /// 2. each `0 <= g(a) <= c(a)`, and
168    /// 3. inflow equals outflow at **every** vertex (no exempt
169    ///    terminals — this is what distinguishes a circulation from a
170    ///    flow).
171    pub fn is_feasible(&self, config: &[usize]) -> bool {
172        let m = self.graph.num_arcs();
173        if config.len() != m {
174            return false;
175        }
176        // (1) Capacity constraints
177        for (flow, cap) in config.iter().zip(self.capacities.iter()) {
178            if (*flow as i64) > *cap {
179                return false;
180            }
181        }
182        // (2) Flow conservation at every vertex
183        let n = self.graph.num_vertices();
184        let mut balance = vec![0_i64; n];
185        for (a, &(u, v)) in self.graph.arcs().iter().enumerate() {
186            let flow = config[a] as i64;
187            balance[u] -= flow;
188            balance[v] += flow;
189        }
190        balance.iter().all(|&b| b == 0)
191    }
192
193    /// Compute the total cost `sum_a a(a) * g(a)` of a circulation.
194    pub fn total_cost(&self, config: &[usize]) -> i64 {
195        config
196            .iter()
197            .zip(self.costs.iter())
198            .map(|(&g, &c)| (g as i64) * c)
199            .sum()
200    }
201}
202
203impl Problem for MinimumCostCirculation {
204    const NAME: &'static str = "MinimumCostCirculation";
205    type Value = crate::types::Min<i64>;
206
207    fn dims(&self) -> Vec<usize> {
208        self.capacities.iter().map(|&c| (c as usize) + 1).collect()
209    }
210
211    fn evaluate(&self, config: &[usize]) -> crate::types::Min<i64> {
212        if !self.is_feasible(config) {
213            return crate::types::Min(None);
214        }
215        crate::types::Min(Some(self.total_cost(config)))
216    }
217
218    fn variant() -> Vec<(&'static str, &'static str)> {
219        crate::variant_params![]
220    }
221}
222
223crate::declare_variants! {
224    default MinimumCostCirculation => "(num_vertices + num_arcs)^6",
225}
226
227#[cfg(feature = "example-db")]
228pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
229    // Two competing cycles on V = {0, 1, 2}:
230    //   cycle A: 0->1->0  (cost per unit = 2 + (-3) = -1, capacity 2)
231    //   cycle B: 0->2->0  (cost per unit = 1 + (-4) = -3, capacity 1)
232    // Optimal: push both to capacity.
233    //   arc 0 (0->1) = 2, arc 1 (1->0) = 2, arc 2 (0->2) = 1, arc 3 (2->0) = 1
234    //   cost = 2*2 + 2*(-3) + 1*1 + 1*(-4) = 4 - 6 + 1 - 4 = -5
235    let problem = MinimumCostCirculation::new(
236        crate::topology::DirectedGraph::new(3, vec![(0, 1), (1, 0), (0, 2), (2, 0)]),
237        vec![2, 2, 1, 1],
238        vec![2, -3, 1, -4],
239    );
240    let optimal_config = vec![2_usize, 2, 1, 1];
241    let optimal_value = problem.evaluate(&optimal_config);
242    let scalar = match optimal_value {
243        crate::types::Min(Some(v)) => v,
244        crate::types::Min(None) => panic!("canonical example must be feasible"),
245    };
246    vec![crate::example_db::specs::ModelExampleSpec {
247        id: "minimum_cost_circulation",
248        instance: Box::new(problem),
249        optimal_config,
250        optimal_value: serde_json::json!(scalar),
251    }]
252}
253
254#[cfg(test)]
255#[path = "../../unit_tests/models/graph/minimum_cost_circulation.rs"]
256mod tests;
problemreductions/models/graph/minimum_cost_circulation.rs

problemreductions/models/graph/
minimum_cost_circulation.rs
