15 082J and 6 855J and ESD 78J November 30 2010 The Multicommodity Flow Problem Lecture overview Notation A small illustrative example Some applications of multicommodity flows Optimality conditions A Lagrangian relaxation algorithm 2 On the Multicommodity Flow Problem O D version K origin destination pairs of nodes s1 t1 s2 t2 sK tK Network G N A dk amount of flow that must be sent from sk to tk uij capacity on i j shared by all commodities cijk cost of sending 1 unit of commodity k in i j x ijk flow of commodity k in i j 3 A Linear Multicommodity Flow Problem 5 units good 1 1 5 5 units good 1 4 1 1 1 2 5 u25 5 1 1 2 units good 2 3 6 6 2 units good 2 Quick exercise determine the optimal multicommodity flow 4 A Linear Multicommodity Flow Problem 5 units good 1 1 5 5 units good 1 4 1 1 1 2 1 1 2 units good 2 3 1 1 1 x12 x25 x54 3 5 u25 5 6 6 2 2 2 x32 x25 x56 2 1 x14 2 2 units good 2 5 The Multicommodity Flow LP Min k k c ij x ij i j A k d k if i sk k k x x d k if i t k ij ji j j 0 otherwise k x ij uij for all i j A k x ijk 0 Supply demand constraints Bundle constraints i j A k K 6 Assumptions for now Homogeneous goods Each unit flow of commodity k on i j uses up one unit of capacity on i j No congestion Cost is linear in the flow on i j until capacity is totally used up Fractional flows Flows are permitted to be fractional OD pairs Usually a commodity has a single origin and single destination 7 Application areas Type of Network Nodes Arcs Flow Communic Networks O D pairs for messages Transmission lines message routing Computer Networks storage dev or computers Transmission lines data messages Railway Networks yard and junction pts Tracks Trains Distribution Networks plants warehouses highways railway tracks etc trucks trains etc 8 Internet Traffic Fact The internet protocal in most use today was developed in 1981 9 On Fractional Flows In general linear multicommodity flow problems have fractional flows even if all data is integral The integer multicommodity flow problem is difficult to solve to optimality 10 A fractional multicommodity flow 1 unit of flow must be sent from si to ti for i 1 2 3 uij 1 for all arcs cij 0 except as listed s1 t3 2 2 1 t1 s3 2 3 s2 t2 2 11 A fractional multicommodity flow 1 unit of flow must be sent from si to ti for i 1 2 3 uij 1 for all arcs cij 0 except as listed s1 t3 2 2 1 t1 s3 2 3 s2 t2 2 Optimal solution send unit of flow in each of these 15 arcs Total cost 3 12 Decomposition based approaches Price directed decomposition Focus on prices or tolls on the arcs Then solve the problem while ignoring the capacities on arcs Resource directive decomposition Allocate flow capacity among commodities and solve Simplex based approaches Try to speed up the simplex method by exploiting the structure of the MCF problem 13 A formulation without OD pairs Minimize k k c x 17 1a 1 k K subject to k x ij uij for all i j A 17 1b for k 1 2 k 17 1c 1 k K Nx k b k k ij 0 x u k ij for all i j A for k 1 2 k 17 1d 14 Optimality Conditions Partial Dualization Theorem The multicommodity flow x xk is an optimal multicommodity flow for 17 if there exists non negative prices w wij on the arcs so that the following is true k x k ij uij 1 If w ij 0 then 2 The flow xk is optimal for the k th commodity if ck is replaced by cw k where cijw k cijk w ij Recall xk is optimal for the k th commodity if there is no negative cost cycle in the kth residual network 15 A Linear Multicommodity Flow Problem 5 units good 1 1 5 5 units good 1 4 1 1 1 2 1 1 2 units good 2 Set w2 5 2 3 1 1 1 x12 x25 x54 3 5 u25 5 6 2 2 2 x32 x25 x56 2 6 1 x14 2 2 units good 2 Create the residual networks 16 The residual network for commodity 1 5 1 1 4 1 5 1 1 3 2 3 5 1 1 3 Set w2 5 2 6 6 There is no negative cost cycle 17 The residual network for commodity 2 5 1 4 1 1 3 2 3 Set w2 5 2 3 1 1 5 1 1 6 6 There is no negative cost cycle 18 Optimality Conditions full dualization One can also define node potentials so that the reduced cost cijp k cijk w ij pik pkj 0 for all i j A and k 1 K This combines optimality conditions for min cost flows with the partial dualization optimality conditions for multicommodity flows 19 Mental Break According to NPD Fashion World what percentage of lingerie is returned to the store 50 What is the average life span for a taste bud 10 days Charles Osborne set the record for the longest case of the hiccups How long did they last 68 years An outside source estimated that Osborne hiccupped 430 million times over the 68 year period He also fathered 8 children during this time period 20 Mental Break Outside a barber s shop there is often a pole with red and white stripes What is the significance of the red stripes It represents the bloody bandages used in blood letting wrapped around a pole How many digestive glands are in the human stomach Around 35 million What is the surface area of a pair of human lungs Around 70 meters2 Approximately the same size as a tennis court 21 Lagrangian relaxation for multicommodity flows Min k k c ij x ij i j A k d k if i sk k k x ij x ji d k if i t k j j 0 otherwise k x ij uij for all i j A k x ijk 0 Supply demand constraints Bundle constraints i j A k K 22 Lagrangian relaxation for multicommodity flows Min k k c ij x ij i j A k w ij x ijk uij i j A k d k if i sk k k x ij x ji d k if i t k j j 0 otherwise k x ij uij for all i j A k x ijk 0 Supply demand constraints Bundle constraints i j A k K Penalize the bundle constraints Relax the bundle constraints 23 Lagrangian relaxation for multicommodity flows L w Min kk k k c x c w …