[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}
}