[Model] MinimumCostCirculation

[zhangjieqingithub]

Motivation

MinimumCostCirculation is the natural graph-flow target for MinimumCostMaximumFlow.

It is useful because it gives an exact companion rule for continuous min-cost max-flow without introducing an overly broad linear-programming hub as the first connection.

Associated rule:

• [Rule] MinimumCostMaximumFlow to MinimumCostCirculation #1031

Definition

Name: MinimumCostCirculation
Reference: MIT 6.854 notes, "Min-cost flow algorithms." https://courses.csail.mit.edu/6.854/21/Scribe/s10-minCostFlowAlg/s10-minCostFlowAlg.html

Let G = (V,E) be a finite directed multigraph with loops and parallel arcs allowed. The instance has:

• finite arc capacities u_e >= 0,
• finite signed arc costs a_e in R.

A feasible circulation is a function
g : E -> R_{>= 0}
such that:

• 0 <= g_e <= u_e for every arc e,
• for every vertex v in V, total inflow at v equals total outflow from v.

The objective is to minimize total circulation cost:
sum_{e in E} a_e g_e.

So this is a minimization problem.

Signed costs are part of the base model because the standard reduction from min-cost max-flow to min-cost circulation uses one sufficiently negative return arc from the sink to the source.

Variables

Let m = |E|.

• Count: m continuous variables
• Per-variable domain: R_{>= 0}
• Meaning: variable g_e is the amount of circulation on arc e

A configuration is feasible iff it satisfies every capacity constraint and flow conservation at every vertex.

Schema (data type)

Type name: MinimumCostCirculation

Recommended variant:

• directed multigraph input,
• continuous nonnegative real flows,
• finite nonnegative real capacities,
• finite signed real costs.

Field	Mathematical type	Description
graph	finite directed multigraph	Directed network; loops and parallel arcs allowed
capacities	E -> R_{>=0}	Finite arc capacity function u
costs	E -> R	Finite signed arc cost function a

Complexity

This problem is polynomial-time solvable as a standard minimum-cost flow problem.

A conservative registry-level expression can be:
(num_vertices + num_arcs)^6

This should be treated as a safe polynomial placeholder, not as a claim of the sharpest known min-cost-flow bound. A sharper strongly-polynomial algorithmic bound may be substituted during implementation if the implementer fixes a specific algorithm and citation.

Extra Remark

The model should allow negative arc costs but finite capacities. With finite capacities, negative-cost cycles do not make the objective unbounded below; they are exactly what the min-cost-max-flow reduction uses to force maximum flow value before cost minimization.

Reduction Rule Crossref

• [Rule] MinimumCostMaximumFlow to MinimumCostCirculation #1031

How to solve

• It can be solved by polynomial-time min-cost-flow algorithms.
• It can be used as the exact target for [Rule] MinimumCostMaximumFlow to MinimumCostCirculation #1031.
• It can also be expressed as a linear program with one continuous variable per arc.

Example Instance

Take vertices {0,1} and arcs:

Arc	Capacity	Cost
0 -> 1	2	3
1 -> 0	1	-5

Expected Outcome

Any positive circulation must send the same amount on both arcs. The bottleneck is the arc 1 -> 0, so the best circulation sends:

• g(0,1) = 1
• g(1,0) = 1

The objective value is:
1*3 + 1*(-5) = -2.

Sending 0 units has cost 0, so the negative-cost feasible circulation is strictly better. This example checks that negative costs are allowed and that capacities bound the amount of circulation.

BibTeX

@misc{MIT6854MinCostFlow,
  author       = {{MIT 6.854 Course Staff}},
  title        = {Min-cost flow algorithms},
  howpublished = {Course notes for Advanced Algorithms, MIT 6.854},
  url          = {https://courses.csail.mit.edu/6.854/21/Scribe/s10-minCostFlowAlg/s10-minCostFlowAlg.html},
  note         = {Accessed 2026-04-10}
}

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	Pass	Problem not yet in pred list; companion [Rule] #1031 provides graph connectivity; concrete motivation as the natural target for MinimumCostMaximumFlow
Non-trivial	Pass	Distinct continuous-flow problem with circulation (no source/sink, conservation everywhere) and signed costs; not a repackaging of any existing model in the catalog
Correctness	Warn	Polynomial-time claim is correct (classical result), but the placeholder (num_vertices + num_arcs)^6 is much looser than known bounds and should be replaced with a real algorithmic bound during implementation
Well-written	Warn	Sections complete; minor concerns about continuous-domain semantics vs. the codebase's discrete dims() convention, and a structurally minimal worked example

Overall: 2 passed, 2 warnings, 0 failed

---

Usefulness

• pred show MinimumCostCirculation returns "Unknown problem", confirming the model is new.
• The issue lists companion [Rule] [Rule] MinimumCostMaximumFlow to MinimumCostCirculation #1031 (MinimumCostMaximumFlow to MinimumCostCirculation) under both "Associated rule" and "Reduction Rule Crossref" — this is a concrete graph connection (not just an "orphan" model).
• "How to solve" lists polynomial min-cost-flow algorithms and an LP formulation. ILP is not claimed as a direct path, so no companion [Rule] X to ILP issue is required.
• Motivation explicitly frames the model as the clean target for the CellRouter-aligned MCMF rule, avoiding the need to introduce a generic LP hub. Pass.

Non-trivial

• Distinct feasibility constraints from anything currently in the catalog: arc capacities + flow conservation at every vertex (no source/sink), continuous nonneg flow, signed arc costs. MinimumEdgeCostFlow (the only cost-bearing flow model in pred list) is discrete and source/sink based — not the same problem.
• MinimumCostMaximumFlow ([Model] MinimumCostMaximumFlow #1029) is conceptually related but lexicographically different (first maximize flow, then minimize cost subject to that). The standard reduction in [Rule] MinimumCostMaximumFlow to MinimumCostCirculation #1031 (add negative-cost s-t back arc) shows the two are not the same instance.
• Genuine optimization problem with non-trivial feasibility (LP polytope with conservation constraints), not a renaming or restriction of existing problems. Pass.

Correctness

Definition. Mathematically well-formed: directed multigraph with loops and parallel arcs allowed, capacities u_e >= 0, signed costs a_e in R, feasible circulation 0 <= g_e <= u_e with flow conservation, minimize sum a_e g_e. Clear separation of input, feasibility, and objective.

Complexity verification. The claim "polynomial-time solvable as a standard minimum-cost flow problem" is well-established literature:

• Goldberg & Tarjan (1989), "Finding minimum-cost circulations by canceling negative cycles," JACM 36(4): 873-886 — O(n m^2 log n) strongly polynomial via min-mean cycle canceling.
• Orlin (1993), "A faster strongly polynomial minimum cost flow algorithm," Operations Research 41(2): 338-350 — O(m^2 log n + m n log^2 n) strongly polynomial; an enhanced bound of O(m log n (m + n log n)) is widely cited.
• Modern interior-point work (Chen, Kyng, Liu, Peng, Probst Gutenberg, Sachdeva, "Maximum Flow and Minimum-Cost Flow in Almost-Linear Time," FOCS 2022) gives nearly linear m^{1+o(1)} bounds.

The user's chosen registry expression (num_vertices + num_arcs)^6 is correctly polynomial but extremely conservative — a real implementation should pick a concrete algorithm and its known bound (e.g., Orlin's m log n (m + n log n)). Issue body already flags this as a placeholder, so this is a Warn, not a Fail.

Negative-cost handling. Issue correctly notes that finite capacities bound the objective even with negative cycles — this is true (feasible polytope is bounded ⇒ objective bounded). Sound.

Reference. The cited MIT 6.854 scribed notes URL is already in docs/paper/references.bib as @misc{mit6854MinCostFlow, ...}. The notes do present min-cost circulation and the equivalence with min-cost max-flow via a return arc. Citation is valid.

NP-hardness is not claimed anywhere in the issue — consistent with the actual classical polynomial complexity. No misclassification.

Well-written

Sections present. Motivation, Name, Reference, Definition, Variables, Schema, Complexity, Extra Remark, Reduction Rule Crossref, How to solve, Example Instance, Expected Outcome, BibTeX — all present and substantive.

Symbol consistency. G = (V, E), m = |E|, u_e, a_e, g_e are defined and used consistently. Schema field names (graph, capacities, costs) match the mathematical objects.

Continuous-domain concern (Warn). The Variables section declares m continuous variables with domain R_{>=0}. The codebase's Problem trait uses discrete dims() -> Vec<usize> for finite configuration spaces, and BruteForce operates over discrete configurations. Implementations of continuous-flow models in this repo (e.g., MinimumEdgeCostFlow) use integer capacities to discretize. The issue does not state how dims() and brute-force solving will be handled. This is an implementation-shape question for the future PR and should be clarified (e.g., "values restricted to [0, u_e] ∩ Z for brute force" or "solved only via LP, no brute force"). Not blocking the model itself.

Example quality (Warn). The worked instance is minimal — 2 vertices, 2 arcs, single cycle. It does have multiple feasible configurations (any f ∈ [0,1] on both arcs, infinitely many in the continuous case, with strictly different objective values from 0 down to -2), so it can in principle catch a wrong-sign or wrong-bottleneck implementation. But it does not exercise:

• multiple competing cycles (which is the heart of min-cost circulation),
• parallel arcs or loops (mentioned as allowed in the model),
• a mix of positive and negative cost arcs across more than one cycle.
  A second example with 3-4 vertices and two competing cycles would make the round-trip much stronger. Worth adding before implementation.

Naming convention. MinimumCostCirculation follows the Minimum... prefix rule per CLAUDE.md. Pass.

Schema vs. reductions. The issue is explicit that MinimumCostCirculation does not claim a direct [Rule] MinimumCostCirculation to ILP path, so no companion ILP issue is required.

Recommendations

• Replace the (num_vertices + num_arcs)^6 placeholder during implementation with a concrete, cited algorithmic bound (e.g., Orlin 1993, O(m log n (m + n log n)); or Goldberg-Tarjan 1989). The complexity string must use concrete numeric values per CLAUDE.md.
• Clarify in the issue or in the implementation PR how the continuous flow domain is handled: integer discretization for brute force, or LP-only solving path? This affects dims() and which solvers can be wired up.
• Strengthen the worked example with one additional 3-4 vertex instance that has two competing cycles (one all-positive-cost, one with a negative-cost arc) so the round-trip test can distinguish a correct circulation from a wrong-cycle selection.
• Consider adding the modern almost-linear-time result (Chen et al., FOCS 2022) as a forward pointer in the issue text — purely informational, not a correctness gate.

[isPANN]

/review-structural — commit 88059c6 (post-impl, code-quality + bug sweep)

Verdict: pass — model is mathematically sound, fully wired, and matches issue #1030; only minor nits.

Issue compliance

• Mathematical definition matches issue: yes — directed multigraph, signed costs, non-negative capacities, conservation at every vertex (no source/sink). Integral-circulation restriction documented in module doc with the same precedent (MinimumEdgeCostFlow, MinimumCostMaximumFlow) and is sound for integer instances by total unimodularity.
• Schema fields match: yes — graph: DirectedGraph, capacities: Vec<i64>, costs: Vec<i64> exactly mirror the issue's Schema table. Min<i64> objective with infeasible → Min(None).
• Canonical example: ok — 3-vertex, 4-arc two-cycle instance with cost = -5 strictly beating all four feasible alternatives (0, -2, -3, -5). Search space 3·3·2·2 = 36 (well under 16-variable rule of thumb when measured in bits). Optimum [2,2,1,1] is unique under conservation g0=g1, g2=g3 and asserted in solver test. The verbatim issue 2-vertex example is also covered by test_minimum_cost_circulation_issue_example_1030.

Findings

• Blockers (correctness): none

  • is_feasible correctly checks (a) length, (b) per-arc capacity g ≤ c (no need for g >= 0 because usize), (c) inflow-outflow balance at every vertex via signed i64 accumulator (no overflow risk on i64 for realistic capacities).
  • evaluate properly gates on feasibility before computing the sum, returning Min(None) on any violation — matches Min<i64> infeasibility semantics.
  • dims() returns vec![c+1; m], exact match for integral domain {0..=c}.
  • Module-level getters (num_vertices, num_arcs) match the names used in ProblemSizeFieldEntry and declare_variants! complexity placeholder.
  • Schema-driven CLI wiring: --arcs (DirectedGraph → arcs via problem_help_flag_name), --capacities, --costs are all in CreateArgs::flag_map, and Vec<i64> parsing in parse_numeric_list_value accepts negative integers, so costs like 2,-3,1,-4 deserialize correctly. MCC alias declared in ProblemSchemaEntry::aliases (consistent with MCMF, MECF).
  • Paper entry: display-name added, problem-def block uses existing mit6854MinCostFlow bib entry, derives example numerics from load-model-example("MinimumCostCirculation") (so paper and example_db stay in lockstep). pred-commands snippet round-trips the canonical instance.
  • Test count: 11 fn test_* — comfortably exceeds the ≥3 minimum; covers creation, feasibility (3 happy paths + 2 infeasible variants + wrong-length), serialization, solver-canonical (uniqueness of [2,2,1,1] asserted), negative-cycle smoke, and the verbatim issue [Model] MinimumCostCirculation #1030 2-vertex instance.
  • No blacklisted auto-generated files in diff.

• Nits (quality/HCI):

  • Commit message lists "evaluate-half-cycle-A (-4)" as one of the 11 tests, but there is no such test in the file (the actual 11 are: creation, evaluate_optimal, evaluate_zero, evaluate_cycle_a_only, evaluate_cycle_b_only, evaluate_infeasible_capacity, evaluate_infeasible_conservation, evaluate_wrong_config_length, solver_canonical, negative_cycle_beats_zero, issue_example_1030, serialization — 12 actually; commit count off-by-one). Cosmetic only.
  • is_feasible casts flow: usize → i64 twice (once for capacity check, once for balance). Single cast at the top of the loop would be marginally cleaner, but current form is clear and correct.
  • The (num_vertices + num_arcs)^6 complexity placeholder is conservative; a sharper bound (e.g., Orlin's strongly-polynomial O(m log n (m + n log n))) could be substituted later but is correctly flagged in the module doc and paper as a placeholder, matching issue guidance.
  • No MCC listing in problem_name.rs because alias resolution flows through the registry's ProblemSchemaEntry::aliases — consistent with how MCMF/MECF work; not a gap.