Makeup 3:30–5 on 10/15 1 Min-Cost Flow Many different max-flows in a graph. How compare? • cost c(e)tosendaunitofflow on edge e • find max-flow minimizing � 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 bottle-neck 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. • each path costs at most nC (C =max cost) • cost of flow at most mU C 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 nega-tive cost arcs. • reduction to min-cost flow: add disconnected s, t. • reduction from min-cost flow: – add s-t 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 1– 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 (note: diff of two equal capacity flows is a circulation) – so find circulation q in Gf . – q + f is a flow in G (note: flow+circulation=flow of same capacity) – cost is c(q)+ c(f ) – so adding min-cost q in Gf yields min-cost flow Deciding optimality: • given a max-flow. How decide optimal? • by above, optimal if 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 Gf • converse too: if negative cost cycle, have negative cost circulation. So min-cost< 0. half a lecture 2 Min-Cost Flows 2.1 Optimality Criteria 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 widget supply at source s, infinite demand for widgets at source t 2• let seller at s, buyer at t set prices for stuff • creates “market” where prices get set at all vertices • price p(v) for widget at vertex v • costs reflect shipping charges When is a set of prices “stable”? • suppose have p(v),p(w),c(vw) such that p(w) ≥ p(v)+ c(vw) • then shipper can make money by buying at v, shipping to w, and selling. • reduced cost cp(vw)= c(vw)+ p(v) − p(w) • reduced costs reflect “true cost” of shipping on edge • merchant will want to ship if reduced cost negative. • this will increase demand at v, raise price: so prices wrong! • what stops him? no residual capacity! • 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 Claim: A circulation/flow is optimal if there exists a feasible price function on its residual graph. • first: price function implies feasible • recall: optimal iff no negative cost cycles in residual graph • suppose have feasible price function • so no negative reduced-cost edges • 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 • then residual graph has no negative cycles. How find prices? 3 – attach vertex s with 0-cost edges to everywhere – compute shortest residual paths from s – well defined because no negative cycles – 0-edges guaranteed finite price at all vertices (this why didn’t do paths from s) • define p(v)= d(s,v) • (note: yields residual cost of shipping a unit from s) • note p(w) ≤ p(v)+ c(vw) • thus cp(vw) ≥ 0 everywhere, as desired. • note: given min-cost flow, can verify optimality via one shortest path computation! • note: Using this computation, all edges on shortest paths from shave reduced cost exactly 0 (useful for later). Complementary Slackness: • 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 optimal-ity condition. • complementary slackness implies optimal, since no residual negative re-duced 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 4• 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. 3 Algorithms 3.1 Cycle Canceling Algorithm (Klein) Cycle canceling algorithm: • start with any max-flow (or min-cost circulation problem) • find a negative cost cycle •