DOC PREVIEW
Clemson MTHSC 440 - Lecture

This preview shows page 1-2-21-22 out of 22 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 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 22 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 22 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 22 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

MthSc 440/H440/640: Linear ProgrammingLecture 24Pietro BelottiDept. of Mathematical SciencesClemson UniversityNovember 23, 2010Optimization on graphs1A (undirected) graph is defined as◮a set V of nodes (or vertices)◮a set E of edges◮each edge is a subset containing two nodes of V12345V = {1, 2, 3, 4, 5}E = {{1, 2}, {1, 4}, {2, 4}, {3, 5}}1A good source on Graph Theory is C. Berge, “Graphs”, Elsevier.Directed graphsA directed graph (or digraph) is defined as◮a set V of nodes (or vertices)◮a set A of arcs◮each arc is an ordered pair of nodes of V12345V = {1, 2, 3, 4, 5}A = {(1, 2), (2, 3), (4, 2), (2, 4), (5, 3)}Graphs are useful!. . . because they can model◮road networks◮gas/oil pipelines◮telecommunication networks◮electronic circuitsOptimization problems often arise in the management ofnetwork-like structures.⇒ Variables, constraints, obj. f. related to nodes and edges/arcs.Problem 1: oil pipelineAn oil pipeline pumps oil from an oil well s to an oil refinery t.123st224331Each pipe has its own monthly capacity (in mega-barrels2).Assuming for now an infinite supply of oil at s,⇒ maximize the amount of oil arriving at t each month◮while not exceeding pipe capacities2One mega-barrel = 106barrelsMax-Flow◮The Maximum Flow problem is classical in Optimization◮Can be solved with a very simple and neat algorithm◮We’ll see a Linear Programming model of this problem◮Variables: oil flowing between each node pair◮Constraints: Oil is conserved at intermediate nodes;Constraints: There is a maximum capacity on e ach pipe.◮Objective function: The total oil arriving at t(note: this is exactly the amount of oil that left s)Max-Flow123st224331◮Variables: oil flowing on each arc:xs1, xs2, x12, x13, x2t, x3t◮Constraints: oil is conserved at intermediate nodesi.e. what enters node 1 exits node 1:xs2+ xs1= x12+ x13i.e. what enters node 2 exits node 2: xs2+ x12= x2ti.e. what enters node 3 exits node 3: xs2+ x13= x3t◮Constraints: there is a maximum capacity on e ach pipe,xs1≤ 2, xs2≤ 3, x12≤ 3, x13≤ 4, x2t≤ 2, x3t≤ 1◮Objective function: The total oil at node t: x2t+ x3t◮this should be the same oil that left s: xs1+ xs2Max-Flow: the modelmax x2t+ x3txs1= x12+ x13xs2+ x12= x2tx13= x3t0 ≤ xs1≤ 20 ≤ xs2≤ 30 ≤ x12≤ 30 ≤ x13≤ 40 ≤ x2t≤ 20 ≤ x3t≤ 1Could re-write objective function as max xs1+ xs2Max-Flow in AMPLvar x_s1 >= 0 <= 2;var x_s2 >= 0 <= 3;var x_12 >= 0 <= 3;var x_13 >= 0 <= 4;var x_2t >= 0 <= 2;var x_3t >= 0 <= 1;maximize outflow: x_2t+x_3t; # same as x_s1+x_s2cons_n1: x_s1 = x_12 + x_13;cons_n2: x_s2 + x_12 = x_2t;cons_n3: x_13 = x_3t;How to write a model for any graph? See material on webpage.Max-Flow: the general modelConsider a digraph G = (V, A):◮two nodes s and t of V act as source and destination.◮each arc (i, j) ∈ A has a capacity cij◮Variables: flow on each arc (i, j), call it xijIn general, xijcan be 6= xji(opposite flow)◮Constraints: conservation o f flow at intermediate node i.At an interm. node, what enters will leave∀i ∈ V : s 6= i 6= tPj∈V:(j,i)∈Axji=Pj∈V:(i,j)∈Axij◮Constraints: min and max flo w, 0 ≤ xij≤ cij∀(i, j) ∈ AMax-Flow: the general model◮Objective Function: flow entering t, i.e.,Pj∈V:(j,t)∈Axjt◮(same that leaves s, i.e.Pj∈V:(s,j)∈Axsj)maxPj∈V:(j,t)∈Axjts.t.Pj∈V:(j,i)∈Axji=Pj∈V:(i,j)∈Axij∀i ∈ V : s 6= i 6= t0 ≤ xij≤ cij∀(i, j) ∈ AProblem 2: another oil pipelineABCD4; 102; 123; 152; 184; 21◮Oil company X now uses company Y’s pipeline◮Each month, X wants to pump 5 mega-barrels from A to D,◮Y reserves part of the capacity and charges a cost/flowA→B allows ≤ 4 mega-barrels, cost of 10k$/mega-barrelA→C allows ≤ 2 at a cost of 12B→C allows ≤ 3, cost: 15B→D allows ≤ 2, cost: 18C→D allows ≤ 4, cost: 21⇒ Can the company send oil from A to D?◮How to do it at minimum cost?Minimum cost flowAnother classical problem in Optimization◮Variables: same as in the Max-Flow problem, i.e., quantityof oil flowing on each arc (i.e. between each node pair)◮Constraints: same as in the Max-Flow problem, plus:⋆ the flow leaving node A (= entering node D) has to beequal to 5 mega-barrels◮Objective function: total flow costMin-Cost-FlowABCD4; 102; 123; 152; 184; 21◮Variables: oil flowing on each arc:xAB, xAC, xBC, xBD, xCD◮Constraints: oil does not e vaporate at interm. nodesi.e. what enters B exits B: xs2+ xAB= xBC+ xBDi.e. what enters C exits C: xAC+ xBC= xCD◮Constraints: there is a maximum capacity on e ach pipe,xAB≤ 4, xAC≤ 2, xBC≤ 3, xBD≤ 2, xCD≤ 4◮Constraint: required flow must leave A, i.e., xAB+ xAC= 5◮Objective function: The total pumping cost:10xAB+ 12xAC+ 15xBC+ 18xBD+ 21xCDMin-Cost-Flow: the modelmin 10xAB+ 12xAC+ 15xBC+ 18xBD+ 21xCDxAC+ xAB= xBC+ xBDxAC+ xBC= xCDxAB+ xAC= 50 ≤ xAB≤ 40 ≤ xAC≤ 20 ≤ xBC≤ 30 ≤ xBD≤ 20 ≤ xCD≤ 4Min-Cost-Flow in AMPLvar x_AB >= 0 <= 4;var x_AC >= 0 <= 2;var x_BC >= 0 <= 3;var x_BD >= 0 <= 2;var x_CD >= 0 <= 4;minimize flow_cost: 10*x_AB + 12*x_AC + 15*x_BC+ 18*x_BD + 21*x_CD;cons_nB: x_AB = x_BC + x_BD;cons_nC: x_AC + x_BC = x_CD;outflow: x_AB + x_AC = 5; # same as x_BD + x_CD = 5How to write a model for any graph? See material on webpage.Min-Cost-Flow: the general modelConsider a digraph G = (V, A):◮two nodes s and t of V act as source and destination.◮each arc (i, j) ∈ A has a capacity cijand a cost dij◮a required flow r◮Variables: flow on each arc (i, j), call it xij◮Constraints: conservation o f flow at intermediate node i:At an interm. node, what enters must leave∀i ∈ V : s 6= i 6= tPj∈V:(j,i)∈Axji=Pj∈V:(i,j)∈Axij◮Constraints: min and max flo w, 0 ≤ xij≤ cij∀(i, j) ∈ A◮Constraint: required flow leaves s, i.e.,Pj∈V:(s,j)∈Axsj= r◮Constraint: required flow enters t, i.e.,Pj∈V:(j,t)∈Axjt= r◮Objective Function: cost of flow, i.e.,P(i,j)∈AdijxijMin-Cost-Flow: the general modelLet’s make it more compact: three cases for the flow balan ce.minP(i,j)∈Adijxijs.t.Pj∈V:(j,i)∈Axji−Pj∈V:(i,j)∈Axij= bi∀i ∈ V0 ≤ xij≤ cij∀(i, j) ∈ Awhere b =−r if i = sr if i = t0 otherwiseDual of a min-cost-flow problemThe primal has |V| + |A| constraints and |A| variables:◮One flow conservation constraint for each node i ∈ V◮One upper bound constraint for each arc (i, j) ∈ A◮One variable for each arc (i, j) ∈ ATherefore, the dual has |A| constraints and |V| + |A|


View Full Document

Clemson MTHSC 440 - Lecture

Documents in this Course
Load more
Download Lecture
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 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 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?