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)]
88pub struct MinimumCostCirculation {
89    /// The directed multigraph G = (V, A).
90    graph: DirectedGraph,
91    /// Capacity c(a) for each arc.
92    capacities: Vec<i64>,
93    /// Signed cost a(a) for each arc.
94    costs: Vec<i64>,
95}
96
97impl MinimumCostCirculation {
98    /// Create a new Minimum-Cost Circulation problem.
99    ///
100    /// # Panics
101    ///
102    /// Panics if any of the following holds:
103    /// - `capacities.len() != graph.num_arcs()`
104    /// - `costs.len() != graph.num_arcs()`
105    /// - Any capacity is negative
106    ///
107    /// Note: costs are signed and **may be negative**.
108    pub fn new(graph: DirectedGraph, capacities: Vec<i64>, costs: Vec<i64>) -> Self {
109        let m = graph.num_arcs();
110        assert_eq!(
111            capacities.len(),
112            m,
113            "capacities length ({}) must match num_arcs ({m})",
114            capacities.len()
115        );
116        assert_eq!(
117            costs.len(),
118            m,
119            "costs length ({}) must match num_arcs ({m})",
120            costs.len()
121        );
122        for (i, &c) in capacities.iter().enumerate() {
123            assert!(c >= 0, "capacity[{i}] = {c} is negative");
124        }
125        Self {
126            graph,
127            capacities,
128            costs,
129        }
130    }
131
132    /// Get a reference to the underlying directed graph.
133    pub fn graph(&self) -> &DirectedGraph {
134        &self.graph
135    }
136
137    /// Get a reference to the arc capacities.
138    pub fn capacities(&self) -> &[i64] {
139        &self.capacities
140    }
141
142    /// Get a reference to the arc costs (signed).
143    pub fn costs(&self) -> &[i64] {
144        &self.costs
145    }
146
147    /// Get the number of vertices `|V|`.
148    pub fn num_vertices(&self) -> usize {
149        self.graph.num_vertices()
150    }
151
152    /// Get the number of arcs `|A|`.
153    pub fn num_arcs(&self) -> usize {
154        self.graph.num_arcs()
155    }
156
157    /// Check whether a circulation assignment is feasible.
158    ///
159    /// A circulation is feasible iff
160    /// 1. `config.len() == num_arcs`,
161    /// 2. each `0 <= g(a) <= c(a)`, and
162    /// 3. inflow equals outflow at **every** vertex (no exempt
163    ///    terminals — this is what distinguishes a circulation from a
164    ///    flow).
165    pub fn is_feasible(&self, config: &[usize]) -> Result<bool, crate::traits::EvaluationError> {
166        let m = self.graph.num_arcs();
167        if config.len() != m {
168            return Ok(false);
169        }
170        // (1) Capacity constraints
171        for (flow, cap) in config.iter().zip(self.capacities.iter()) {
172            let flow = i64::try_from(*flow).map_err(|_| {
173                crate::traits::EvaluationError::IntegerOverflow(
174                    "converting circulation configuration value".to_string(),
175                )
176            })?;
177            if flow > *cap {
178                return Ok(false);
179            }
180        }
181        // (2) Flow conservation at every vertex
182        let n = self.graph.num_vertices();
183        let mut balance = vec![0_i64; n];
184        for (a, &(u, v)) in self.graph.arcs().iter().enumerate() {
185            let flow = i64::try_from(config[a]).map_err(|_| {
186                crate::traits::EvaluationError::IntegerOverflow(
187                    "converting circulation configuration value".to_string(),
188                )
189            })?;
190            balance[u] = balance[u].checked_sub(flow).ok_or_else(|| {
191                crate::traits::EvaluationError::IntegerOverflow(
192                    "computing circulation vertex balance".to_string(),
193                )
194            })?;
195            balance[v] = balance[v].checked_add(flow).ok_or_else(|| {
196                crate::traits::EvaluationError::IntegerOverflow(
197                    "computing circulation vertex balance".to_string(),
198                )
199            })?;
200        }
201        Ok(balance.iter().all(|&b| b == 0))
202    }
203
204    /// Compute the total cost `sum_a a(a) * g(a)` of a circulation.
205    pub fn total_cost(&self, config: &[usize]) -> Result<i64, crate::traits::EvaluationError> {
206        let mut total = 0_i64;
207        for (&flow, &cost) in config.iter().zip(self.costs.iter()) {
208            let flow = i64::try_from(flow).map_err(|_| {
209                crate::traits::EvaluationError::IntegerOverflow(
210                    "converting circulation configuration value".to_string(),
211                )
212            })?;
213            let term = flow.checked_mul(cost).ok_or_else(|| {
214                crate::traits::EvaluationError::IntegerOverflow(
215                    "multiplying circulation arc cost".to_string(),
216                )
217            })?;
218            total = total.checked_add(term).ok_or_else(|| {
219                crate::traits::EvaluationError::IntegerOverflow(
220                    "summing circulation costs".to_string(),
221                )
222            })?;
223        }
224        Ok(total)
225    }
226}
227
228impl Problem for MinimumCostCirculation {
229    const NAME: &'static str = "MinimumCostCirculation";
230    type Solution = Vec<usize>;
231    type Value = crate::types::Min<i64>;
232
233    crate::problem_parameters![("num_arcs", num_arcs), ("num_vertices", num_vertices),];
234
235    fn evaluate(
236        &self,
237        config: &Self::Solution,
238    ) -> Result<crate::types::Min<i64>, crate::traits::EvaluationError> {
239        if config.len() != self.graph.num_arcs() {
240            return Err(crate::traits::EvaluationError::InvalidConfiguration(
241                "flow vector length does not match the graph arcs".into(),
242            ));
243        }
244        Ok({
245            if !self.is_feasible(config)? {
246                return Ok(crate::types::Min(None));
247            }
248            crate::types::Min(Some(self.total_cost(config)?))
249        })
250    }
251
252    fn variant() -> Vec<(&'static str, &'static str)> {
253        crate::variant_params![]
254    }
255}
256
257impl crate::solvers::BruteForceProblem for MinimumCostCirculation {
258    fn dimensions(&self) -> Vec<usize> {
259        self.capacities.iter().map(|&c| (c as usize) + 1).collect()
260    }
261}
262
263crate::declare_variants! {
264    default MinimumCostCirculation => "(num_vertices + num_arcs)^6",
265}
266
267crate::register_brute_force! {
268    MinimumCostCirculation,
269}
270
271#[cfg(feature = "example-db")]
272pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
273    // Two competing cycles on V = {0, 1, 2}:
274    //   cycle A: 0->1->0  (cost per unit = 2 + (-3) = -1, capacity 2)
275    //   cycle B: 0->2->0  (cost per unit = 1 + (-4) = -3, capacity 1)
276    // Optimal: push both to capacity.
277    //   arc 0 (0->1) = 2, arc 1 (1->0) = 2, arc 2 (0->2) = 1, arc 3 (2->0) = 1
278    //   cost = 2*2 + 2*(-3) + 1*1 + 1*(-4) = 4 - 6 + 1 - 4 = -5
279    let problem = MinimumCostCirculation::new(
280        crate::topology::DirectedGraph::new(3, vec![(0, 1), (1, 0), (0, 2), (2, 0)]),
281        vec![2, 2, 1, 1],
282        vec![2, -3, 1, -4],
283    );
284    let optimal_config = vec![2, 2, 1, 1];
285    let optimal_value = problem
286        .evaluate(&optimal_config)
287        .expect("canonical example evaluation must succeed");
288    let scalar = match optimal_value {
289        crate::types::Min(Some(v)) => v,
290        crate::types::Min(None) => panic!("canonical example must be feasible"),
291    };
292    vec![crate::example_db::specs::ModelExampleSpec {
293        id: "minimum_cost_circulation",
294        instance: Box::new(problem),
295        optimal_config: serde_json::to_value(optimal_config)
296            .expect("solution serialization must succeed"),
297        optimal_value: serde_json::json!(scalar),
298    }]
299}
300
301#[cfg(test)]
302#[path = "../../unit_tests/models/graph/minimum_cost_circulation.rs"]
303mod tests;
problemreductions/models/graph/minimum_cost_circulation.rs

problemreductions/models/graph/
minimum_cost_circulation.rs
