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 cycle

• then, 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 positive

  • And 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)\).