# Min Cost Flow

Gross flow formulation (otherwise double-count).

Many different max-flows in a graph. How compare?

*cost*\(c(e)\) to send a unit of flow on edge \(e\)(that’s why no \(c\) for max-flow capacity)

find max-flow minimizing \(\sum c(e)f(e)\)

costs may be positive or negative!

note: pushing flow on cost \(c\) edge create residual cost \(-c\) edge.

also easy to find min-cost flow of given value \(v\) less than max (add bottleneck source edge of capacity \(v\))

Clearly, generalizes max-flow. Also shortest path:

How send flow 1 unit of flow?

just use shortest path

more generally, flow decompose into paths and cycles

cost of flow is sum of costs of paths and cycles.

Min-cost circulation:

no source or sink

just find flow satisfying balance everywhere, min-cost

if satisfy balance everywhere, all flow must be going in circles!

more formally: circulation can be decomposed into just cycles.

hard to define in max-flow perspective, but makes sense once allow negative cost arcs.

reduction to min-cost flow: add disconnected \(s\), \(t\).

reduction from min-cost flow:

add \(t\)-\(s\) arc of “infinite” capacity, “infinite” negative cost

of course, circulation will push max possible through this edge

how much can it? max \(s\)-\(t\) flow

so of course, suff to assign capacity equal to max-flow value

see later, sufficient to assign cost \(-nU\) (good for scaling)

another reduction from min-cost flow:

find any old max-flow \(f\)

consider min-cost flow \(f^*\)

difference \(f^*-f\) is a circulation

\(-f\) is sending flow backwards from \(t\) to \(s\)

diff of two equal capacity flows is a circulation

claim feasible in \(G_f = G-f\).

if \(f^*_e-f_e\) positive, have flow \(f^*_e-f_e\) on \(e\)

meanwhile capacity in \(G_f\) is \(u_e-f_e\)

but \(f^*_e<u_e\), done

if \(f^*_e-f_e\) negative, have flow \(f_e-f^*_e\) on \(e'\) (reverse)

meanwhile residual capacity is \(f_e\), greater!

(note \(e'\) is reverse residual arc for \(e\), not the original \(G\) edge reverse to \(e\) (may have different cost, and must be considered entirely separately)

so find circulation \(q\) in \(G_f\).

\(q+f\) is a feasible flow in \(G\) (note: flow+circulation\(=\)flow with same demand)

cost is \(c(q)+c(f)\)

so adding min-cost \(q\) in \(G_f\) yields min-cost flow

## Deciding optimality:

Given a max-flow. How decide optimal?

by above, optimal if the cost of the min-cost residual circulation is 0

suppose not. so have negative cost circulation

decomposes into cycles of flow

one must have negative cost.

so, if \(f\) nonoptimal, negative cost cycles in \(G_f\)

converse too: if negative cost cycle, have negative cost circulation. So min-cost\(<0\).

## Cycle Canceling Algorithm

(Klein)

Cycle canceling algorithm:

start with any max-flow (or min-cost circulation problem)

find a negative cost cycle

push flow around it

analogue of generic augmenting paths under circulation reduction

how many times?

cost decreases by 2 each push

initial cost (in residual graph) 0

final cost at least \(-mCU\) (why?)

so \(mCU\) iterations.

How find negative-cost cycle?

think back to shortest paths

dijkstra only works for positive edges

but Floyd, Bellman-Ford work for negative edges too

**Unless**have negative cost cyclethen, of course, shortest paths undefined

however, Floyd/BF will indentify one negative cycle that is wrecking things.

Floyd \(O(n^3)\), BF \(O(nm)\).

fancy scaling algorithm running in \(O(m\sqrt{n}\log C)\) also known.

So: time bound of \(O(m^2\sqrt{n}CU\log C)\) or \(O(nm^2CU)\) time.

Slow, and not even weakly polynomial! Let’s do better.

Later (homework), you’ll see that cycle canceling is a good idea combined with scaling. But for now, lets take a different approach.

# Prices and Reduced Costs

Recall: flow/circulation optimal iff no residual negative cost cycle.

Reduced-Cost optimality.

another way to decide optimal

based on LP duality (see next week)

given min-cost flow problem

one way to solve: compute opt flow (command economy)

alternative: market economy!

infinite boba tea

*supply*at source \(s\), infinite*demand*for boba at MIT source \(t\)give boba away at \(s\)

at \(t\) will pay for any boba they can get

creates “market” where prices get set at all vertices

*price*\(p(v)\) for widget at vertex \(v\)costs reflect shipping charges

circulation version: boba free everywhere, but possible profit for shipping in circles (government subsidies?)

When is a set of prices “stable”?

suppose have \(p(v),p(w),c(vw)\) such that \(p(w) \ge p(v)+c(vw)\)

then merchant can make money by buying at \(v\), shipping to \(w\), and selling.

*reduced cost*\(c_p(vw) = c(vw)+p(v)-p(w)\)reduced costs reflect “net cost” of moving boba from \(v\) to \(w\)

merchant will want to ship if reduced cost negative.

this will increase demand at \(v\), raise price: so current prices wrong.

what stops him? no residual capacity!

Also, if there is any residual \(s\)-\(t\) capacity, more will get shipped

\(t\) will pay whatever it costs

so prices will rise on \(s\)-\(t\) path until shipping happens

so can only be stable if shipping max-flow

**Definition:**a price function is*feasible*for a (residual) graph if no (residual) arc has negative reduced cost

Important observation: prices don’t affect overall cost:

reduced cycle cost same as original cycle cost

cost of every \(v,w\) path changes by \(p(v)-p(w)\)

negative cost cycles still negative

min-cost paths still min-cost

every flow of same value sees same cost change (path decomposition)

also, all prices can be shifted by a constant without change

**Claim:** A circulation/flow is optimal
iff there exists a feasible price function on its residual graph.

first: price function implies optimal

recall: optimal iff no negative cost cycles in residual graph

suppose have feasible price function

so no negative reduced-cost edges in residual

so no negative cost cycles under reduced costs

thus no negative cost cycles under original costs!

key: cost of cycle unchanged under reduced costs (prices telescope)

converse: suppose have optimal flow/circulation

then residual graph has no negative cycles. How find prices?

what does no negative cycles allow? Shortest paths from source!

i.e., find price of boba if give away at \(s\)

formalizes our market idea

problem: only defines prices on vertices reachable from \(s\)

attach vertex \(s'\) with 0-cost edges to everywhere

(or just add huge-cost arcs from \(s\))

compute shortest residual paths from \(s'\)

well defined because no negative cycles

define \(p(v)=d(s',v)\)

(note: yields reduced cost of shipping a unit from \(s'\))

note \(p(w) \le p(v)+c(vw)\)

thus \(c_p(vw) \ge 0\) everywhere, as desired.

0-edges guaranteed finite price at all vertices (this why didn’t do paths from \(s\))

**note:**given min-cost flow, can verify optimality via one shortest path computation!**note:**Using this computation, all edges on shortest paths from \(s'\) have reduced cost exactly 0 (useful for later).

Feasible prices *certify* a min-cost flow

given prices, checking optimality takes linear time

Price function is a general concept

like min-cut for max-flow

shifts difficult test for global optimum to easier local test

by creating a “bound” that optimum cannot beat

so if you meet it you must be optimum

(later, we’ll see there’s actually a

*number*on the feasible price function that is*equal*to the value of the min cost flow.

# Algorithms

## Shortest Augmenting Path

Idea:

Previously, started with max-flow, made min-cost by cycle canceling

Now, start with empty “min-cost” flow, make optimal by augmenting to maximum

For min-cost, assume starting with no negative cycles

Augment in ways that don’t create them

When reach max-flow, know optimal

Idea: augmenting paths

natural greedy strategy: what augmenting path to use?

Repeatedly augment shortest (min-cost) path (just like max-flow SAP)

Claim: shortest augmenting path doesn’t create negative cycles

Suppose none at start

Suppose shortest augmenting path creates one

only new edges are residual from augmenting path

So cycle includes a residual edge

So is connected to the shortest augmenting path

So insert cycle into SAP at some vertex where they intersect

ie, add “send flow around residual cycle” to augmenting path

Yields a shorter augmenting path

Alternative correctness argument: use price function.

key: price function changes

*value*of paths, but not which is shortest (proof: telescoping)claim: at no time does residual graph have negative cost cycle

proof by induction

if currently true, can compute shortest paths from \(s\) to define (new) prices

result: all edges on shortest \(s\)-\(t\) paths have cost 0

so augmentation is along cost 0 edges

create residual arcs, but only cost 0

so, no negative reduced cost arcs

so, no negative cost cycles. induction proved.

so after \(f\) iterations, have flow value \(f\) of minimum cost.

Wait, why no \(s'\) supersource?

shortest paths from \(s\) assigns a new price to every vertex reachable from \(s\)

new prices don’t affect cycle costs anywhere

some vertices/edges don’t get repriced because not reachable

but then we won’t augment through them

So: if cannot reach, then (by induction) can’t ever reach.

Discarding doesn’t change max-flow or future shortest paths

Alternatively, add a large value to every vertex \(v\) not reachable from \(s\).

Makes edges

*from*\(v\) to anything reachable from \(s\) very positiveAnd nothing goes from \(s\)-reachable to \(v\), so no negative.

Is SAP strongly polynomial for MCF?

no

we had length-1 edges when we did SAP for max-flow

and SAP increased distance to \(n\) to finish, no dependence on numbers

but now our lengths are edge costs—numeric, maybe large

so progress in distance is no longer a number-independent measure

Special case algorithm:

integer capacity edges (or at least small flow),

no negative cost edges.

so mincost circ 0, but min-cost flow maybe not

one unit of flow per (integer) augmentation

Time analysis: \(O(mf\log n)\) for flow of value \(f\)

so \(O(mn\log n)\) for typical unit capacity graph

since

*capacity*of flow at most \(n\).

Note: don’t need explicit prices to run

prices don’t change which paths are shortest

but with good prices, can use Dijkstra’s fast algorithm.

Limitations:

unit capacity

no negative edges

Lets handle negative arcs.

Min-cost circulation

Still unit-cap edges (or at least small flow)

Can’t do shortest paths to eliminate

So, try brute force

saturate all negative arcs

creates excesses, deficits

now, need to send excess back to deficits

find min-cost flow in residual graph

(know one exists, namely saturations)

sum of saturations and flow back is circulation

and, since min cost flow back, min-cost circulation

now, no negative arcs

so shortest augmenting path works

total excess is \(m\)

so \(m\) augmentations send it back

time \(O(m^2\log m)\)

Handle min-cost flow via max-flow plus above min-cost circulation

# Scaling Min-Cost flow

## Capacity Scaling

Scale in capacity bits one at a time. (Edmonds Karp 1972)

min-cost circulation problem

in scaling step, double capacities, possibly add 1

double flow values

changes residual capacities by at most 1

so some negative reduced cost arcs might get capacity 1

how fix? just like unit case

saturate all negative cost arcs (creates excess, deficits)

find min-cost flow to ship excesses to deficits (know one exists)

total excess \(O(m)\)

so \(O(m)\) shortest augmenting paths solve

time \(O(m^2 \log n)\)

\(O(\log U)\) phases

total \(O(m^2 \log n \log U)\).

## Cost Scaling

HW

# Complementary Slackness

Looking ahead to linear programming.

what do merchants do? think about reduced costs.

if reduced cost positive, noone will ship: flow 0 on edge

if negative, will ship: flow equals capacity on edge

if 0, don’t care: flow arbitrary on edge.

flow with these properties has

*complementary slackness:*, another optimality condition.complementary slackness implies optimal, since no residual negative reduced cost arcs

suppose optimal. assign prices so no residual negative cost arcs. implies any negative reduced cost original arc is saturated, any positive reduced cost arc empty (since reverse would have neg cost)

Complementary slackness is on **original
graph**, corresponds to feasible pricing on
**residual graph**

Given feasible price function, can find opt flow easy:

delete positive redued cost arcs (no flow in optimum)

saturate negative arcs

creates excesses/deficits at nodes

ship excesses to deficits on 0-cost arcs

know this can be done, since optimum does

do by creating supersource for excesses, supersink for deficits, finding max-flow on 0 arcs

saw converse: given flow, need to compute optimum distances. So min-cost flow really is max-flow plus shortest paths!

some flow algs use prices implicitly, to prove correctness

others use explicitly, to guide solution.

# Conclusion

Finish remarks on min-cost flow.

Strongly polynomial algorithms exist.

Tardos 1985

minimum mean-cost cycle

reducing \(\epsilon\)-optimality

“fixing” arcs of very high reduced cost

best running running time roughly \(O(m^2)\)

best scaling time (double scaling) \(O(mn \log\log U \log C)\).