[Rule] MinimumCostMaximumFlow to MinimumCostCirculation

[zhangjieqingithub]

Source

MinimumCostMaximumFlow

Source model issue: #1029

Target

MinimumCostCirculation

Target model issue: #1030

Motivation

This is the clean graph-flow companion rule for the CellRouter-aligned MinimumCostMaximumFlow model.

It avoids the fixed-demand ambiguity of ordinary MinimumCostFlow and avoids needing a broad linear-programming hub as the first connection. The rule is also a standard textbook equivalence: min-cost max-flow can be solved as min-cost circulation by adding one return arc from the sink to the source with sufficiently negative cost.

Reference

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

The notes state that min-cost max-flow and min-cost circulation are equivalent and describe adding a sufficiently negative-cost arc from t back to s.

Reduction Algorithm

Let the source instance be a MinimumCostMaximumFlow instance with:

• directed multigraph G = (V,E),
• source s,
• sink t,
• capacities u_e >= 0,
• nonnegative costs c_e >= 0.

Construct a MinimumCostCirculation instance G' = (V,E') as follows.

1. Keep every original arc e in E with the same capacity u_e and cost c_e.

2. Define an upper bound on any feasible s-t flow value:
   U = sum_{e in delta^+(s)} u_e.

3. Define a sufficiently large priority constant:
   B = 1 + sum_{e in E} c_e.

4. Add one new return arc e* = (t,s) with:

   • capacity U,
   • cost -B.

5. Solve the resulting minimum-cost circulation instance.

6. Recover the source flow by discarding the return arc and reading the circulation values on the original arcs:
   f_e = g_e for every original arc e in E.

The amount of flow sent in the source instance equals the circulation value on the return arc:
|f| = g_{e*}.

Correctness Argument

Any feasible s-t flow of value F in the source instance lifts to a feasible circulation in G' by setting the return-arc flow to F. Conservation is restored because the return arc carries exactly the net sink inflow back to the source.

Conversely, any feasible circulation in G' projects to a feasible s-t flow on the original arcs by deleting the return arc. The projected flow has value equal to the amount sent on (t,s).

It remains to show that the objective enforces lexicographic optimization. The added return arc contributes -B * F to the circulation cost, where F is the projected flow value. Since all original arc costs are nonnegative, any useful s-t flow can be decomposed into simple s-t paths plus nonnegative-cost cycles. Every simple s-t path has cost at most sum_{e in E} c_e, which is strictly less than B. Thus each additional positive amount of feasible path flow paired with the return arc has negative reduced cost, so the circulation optimum pushes the return-arc flow as large as possible. Once the maximum flow value is fixed, the return-arc contribution is constant, so minimizing circulation cost is exactly minimizing the original flow cost.

Thus an optimal circulation projects to a maximum-value s-t flow of minimum cost.

Size Overhead

Let:

• n = num_vertices,
• m = num_arcs.

Target metric	Formula
num_vertices	n
num_arcs	m + 1

The construction preserves all original vertices and arcs and adds exactly one new arc.

Validation Method

Use closed-loop validation on small hand-solvable instances:

• solve the source MinimumCostMaximumFlow instance by direct enumeration or a small LP,
• reduce it to MinimumCostCirculation,
• solve the circulation instance,
• delete the return arc,
• verify that the projected flow is feasible, has maximum value, and has minimum cost among maximum-value flows.

Test cases should include:

• a cheaper submaximum flow that must be rejected because value has priority,
• parallel arcs with different costs,
• a saturated source cut,
• zero-capacity arcs,
• a case where some original arcs are unused despite low cost because they do not help reach the sink.

Example

Use the model example with vertices {s, a, b, t} and arcs:

Arc	Capacity	Cost
s -> a	2	1
s -> b	1	0
a -> b	1	0
a -> t	1	1
b -> t	2	2

The maximum possible source-to-sink flow value is 3, and the minimum cost among value-3 flows is 7.

For the reduction:

• U = 2 + 1 = 3, using the capacities of arcs leaving s,
• B = 1 + (1 + 0 + 0 + 1 + 2) = 5,
• add return arc t -> s with capacity 3 and cost -5.

The target circulation uses:

• original arc flows equal to the optimal source flow,
• return-arc flow g(t,s) = 3.

So the target objective is:
7 + 3*(-5) = -8.

A cheaper-looking source flow of value 2 with original cost 4 would lift to circulation cost:
4 + 2*(-5) = -6,
which is worse than -8. This shows the negative return arc enforces maximum flow value before cost minimization.

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