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