DOC PREVIEW
MIT 15 082J - Lecture Notes

This preview shows page 1-2-16-17-18-34-35 out of 35 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 35 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

15.082J and 6.855J and ESD.78JThe Successive Shortest Path Algorithmand the Capacity Scaling Algorithm for the Minimum Cost Flow ProblemOverview of lecture• Quick review of min cost flow and optimality conditions• Pseudoflows • The successive shortest path algorithm• A polynomial time scaling algorithm23The Minimum Cost Flow Problemuij= capacity of arc (i,j).cij= unit cost of shipping flow from node i to node j on (i,j).xij= amount shipped on arc (i,j) Minimize ∑(i,j)∈Acijxij∑jxij- ∑jxji= bifor all i ∈ N.and 0 ≤ xij≤ uij for all (i,j) ∈ A.4The Residual Network G(x)uiji jcijuij - xiji jxijcij-cij81 2$10Suppose x12 = 351 23$10-$10Reducing the flow in (i, j) by 1 is equivalent to sending one unit of flow from j to i. It reduces the cost by cij.5Pseudo-flowsA pseudo-flow is a "flow" vector x such that 0  x  u.Let e(i) denote the excess (deficit) at node i.123 54000402305 -20 -3123 5410205445552 -22 -7Supplies/demands and capacitiesA pseudo-flow and excesses6Pseudo-flows and the residual network123 54000402305-20-3A pseudo-flow and excesses123 54102054 42305-20-3The residual network32The infeasiblity of the pseudo-flow is ∑e(i)>0e(i). e.g., 5.7Reduced Costs in G(x)$31 23$1-$5$3 – π1+ π21 23$1 – π2+ π3-$5 – π3+ π1Let πidenote the node potential for node i.ij ij i jcc  For unit of flow out of node i, subtract πifrom the cost.For unit of flow into node j, add πjto the cost.Optimality ConditionsTheorem. Suppose that x* is flow and π* is a vector of node potential. Then x* and π* are optimal if1. the flow x* is feasible and2. cπ*ij≥ 0 for all (i, j) ∈ G(x*). The second property is often called dual feasibility.8Optimality Conditions9The cycle canceling algorithm starts with a feasible flow and maintains a feasible flow at each iteration. It terminates with dual feasibility.The successive shortest path algorithm starts with (and maintains) an infeasible flow x and node potentials π that are dual feasible. It stops when it obtains a flow that is feasible.It’s main subroutine involves sending flow along a path from a node with excess to a node with deficit.Augmenting paths10123 54102054 42305 -20 -3Capacities and excesses in G(x)32A path P from i to j in G(x) is augmenting ife(i) > 0, e(j) < 0, and ∀ (v, w) ∈ P, cπvw= 0. 123 543804 400Excesses and reduced costs in G(x)0005 -20 -3Augmenting along a path11The capacity of an augmenting path P from node i to node j ismin { e(i), -e(j), min(v,w)∈Prvw}.123 5453The augmenting path with residual capacities.35 -2In this case, the capacity is min {5, 2, 3} = 2To augment along a path P is to send δ units of flow from i to j in P, where δ = capacity(P).Before and after the augmentation12123 54102054 42305 -20 -3Capacities and excesses in G(x)before augmenting on P32123 54102034 44103 00 -3Capacities and excesses in G(x)after augmenting on P142The effect of augmentations13123 543804 400Excesses and reduced costs before the augmentation0005 -20 -32123 543804 400Excesses and reduced costs after the augmentation0003 00 -30Augmentations reduce the infeasiblity by at least 1.Augmentations maintain dual feasibility. Any arc added to G(x) is the reversal of an arc with a reduced cost of 0.14The Successive Shortest Path AlgorithmInitialize with a dual feasible pseudo-flow (x, π) while x is infeasible doselect a node i with e(i) > 0adjust the node potentials so that it remains dual feasible and there is an augmenting path P from node i to a node j with e(j) < 0;(if the adjustment is not possible, then there is no feasible flow for the problem)augment along path Pupdate the residual network and excesses;The SSP AlgorithmThe next steps• Show how to find an initial dual feasible pseudoflow.• Show how to adjust the node potentials• Show that the problem is infeasible if there is no possible adjustment of the node potentials• Proof of finiteness• Proof of correctness of the algorithm15Finding an initial dual feasible pseudoflowLet A’ = {(i, j) : uij= ∞} .We first choose π so that cπij≥ 0 for (i, j) ∈ A’. Step 1. Let C = 1 + max { | cij| : (i, j) ∈ A’}. If there is no directed path from 1 to j in A’, then add arc (1, j) to A’ with cost nC.Step 2. Use a shortest path algorithm to find the shortest path length from 1 to node j in A’. If there is a negative cost cycle, quit. One can send an infinite amount of flow around a negative cost cycle.Step 3. Let π(j) = -d(j) for all j. Step 4. For each arc (i, j) ∈ A\A’ with cπij< 0, let xij= uij.1617Finding an initial dual feasible pseudoflow17A’ = solid lines. They have infinite capacity. The costs are on the arcs.The dotted red line has a capacity of 10. 12 3456-1-1-1-2-28-1-2-20-17The numbers next to nodes are the shortest path distances from node 1. cπij= cij+ d(i) – d(j) 12 34560020870d(2) = -1-2-3-5-700Adjusting node potentialsSelect node i with e(i) > 0.Let d(j) = shortest path from node i to node j in G(x).Replace πjby πj- d(j) for all j ∈ N. 1812 3456000031026Node potentials πj-d(j)and reduced costs-2-4-1-1-112 3456112000025G(x) with reduced costs on arcs and shortest path distances. e(1) > 0. 0241101On Node PotentialsAfter adjusting node potentials, there is an path with 0-reduced cost arcs in G(x) from node i to each other node (assuming that there is a path from node 1). 1912 3456000031026Node potentials πj-d(j)and reduced costs-2-4-1-1-112 345657512551052Excesses and capacities.-2-3-50100Augment along a path from node iSelect a node j with e(j) < 0 that is reachable from node i. Let P be the path from node i to node j.Send min {e(i), -e(j), min {rvw: (v, w) ∈ P} } units in P.2012 345657512551052Excesses and capacities.-2-3-50100Send min {10, 3, 5} units of flow from 1 to 4. Update residual capacities and excesses.12 34-2070234323Proof of finiteness and correctnessFiniteness comes from the fact that the infeasibility is always integer and nonnegative, and it decreases by at least one at each iteration.The algorithm usually terminates a feasible flow (and also with dual feasibility) and is thus optimal.It can also terminate if there is no path from a node i with e(i) > 0 to any node with negative excess. In the latter case, the problem is infeasible.2122Analysis of the Successive Shortest Path AlgorithmEach augmentation reduces the infeasibility by at least 1. Initial infeasibility is at most mUmax+ nbmaxThe time per augmentation is


View Full Document

MIT 15 082J - Lecture Notes

Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?