Network Optimization Multicommodity Flows

The Multicommodity Flow Problem 1 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) 2 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. 3 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 4 The Multicommodity Flow LP Min ∑ k k c ∑ ij x ij ( i , j )∈A k ⎧ d k if i = sk ⎪ k k − = x x ∑j ij ∑j ji ⎨ −d k if i ∈ tk ⎪ 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 5 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. 6 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 7 On Fractional Flows ‹ In general, multicommodity flow problems have fractional flows, even if all data is integral. ‹ The integer multicommodity flow problem is difficult to solve to optimality. 8 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 9 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. 10 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. 11 A formulation without OD pairs Minimize subject to ∑ ck x k ∑ x ijk ≤ uij (17.1a) 1≤ k ≤ K 1≤ k ≤ K Nx k = b k 0≤ x ≤u k ij k ij for all (i , j ) ∈ A (17.1b) for k = 1, 2, ..., k (17.1c) for all (i , j ) ∈ A for k = 1, 2, ..., k (17.1d) 12 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. 13 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 14 The residual network for commodity 1 $5 1 4 -$5 $1 -$1 -$1 $1 $3 2 $-3 5 $1 $1 3 Set w2,5 = $2 $6 6 There is no negative cost cycle. 15 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. 16 Optimality Conditions: full dualization One can also define node potentials π so that the reduced cost cijπ ,k = cijk + w ij − π ik + π kj ≥ 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. 17 Lagrangian relaxation for multicommodity flows Min ∑ k k c ∑ ij x ij ( i , j )∈A k ⎧ d k if i = sk ⎪ k k ∑j x ij − ∑j x ji = ⎨ −d k if i ∈ tk ⎪ 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 18 Lagrangian relaxation for multicommodity flows Min ∑ k k c ∑ ij x ij ( i , j )∈A k + ∑ ( i , j )∈A w ij (∑ x ijk − uij ) k ⎧ d k if i = sk ⎪ k k ∑j x ij − ∑j x ji = ⎨ −d k if i ∈ tk ⎪ 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. 19 Lagrangian relaxation for multicommodity flows L(w) = Min ∑ k kk k k + w ( x c x − w ( c + w ) x ∑ ∑ ∑ ijij ij ij ij ij ij ij−uuijij ) ( i , j )∈A k ( i , j )∈A ( i , jk)∈A ⎧ d k if i = sk ⎪ k k ∑j x ij − ∑j x ji = ⎨ −d k if i ∈ tk ⎪ 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 Simplify the objective function. 20 Subgradient Optimization for solving the Lagrangian Multiplier Problem 5 units good 1 1 $5 5 units good 1 4 $1 $1 $1 2 3 units good 2 u25 = 5 $1 u32 = 2 $6 3 e.g., set w0 = 0. 5 $1 6 3 units good 2 Choose an initial value w0 of the “tolls” w, and find the optimal solution for L(w). 21 Subgradient Optimization for solving the Lagrangian Multiplier Problem 5 units good 1 1 $5 5 units good 1 4 $1 $1 $1 2 5 $1 $1 3 units good 2 3 $6 6 next: determine the flows, and then determine w1 from w0 3 units good 2 The flow on (2,5) = 8 > u25 = 5. The flow on (3,2) = 3 > u32 = 2. 22 Choosing a search direction r + = max (0, r ) y ij = ∑ x ijk = flow in arc (i,j) k w q +1 ij = [w + θ q ( y ij − uij )] q ij + 1 0 w 25 = [w 25 + θ 0 (8 − 5)]+ = 3θ 0 (y-u)+ is called the search direction. θq is called the step size. 1 0 w 32 = [w 32 + θ 0 (3 − 2)]+ = θ 0 1 1 w = 3 and w So, if we choose θ0 = 1, then 25 32 = 1 Then solve L(w1). 23 Solving L(w1) 5 units good 1 1 $5 5 units good 1 4 $1 $1 If θ1 = 1, then w2 = 0. $4 2 5 $1 $2 3 units good 2 3 $6 6 3 units good 2 2 1 w 25 = [w 25 + θ 1 (0 − 5)]+ = [3 − 5θ 1 ]+ 2 1 w 32 = [w 32 + θ 1(0 − 2)]+ = [1 − 2θ 1 ]+ 24 Comments on the step size ‹ The search direction is a good search direction. ‹ But the step size must be chosen carefully. ‹ Too large a step size and the solution will oscillate and not converge ‹ Too small a step size and the solution will not converge to the optimum. 25 On choosing the step size The step size θq should be chosen so that lim θ q = 0 q →∞ ∞ and ∑θ q =1 q =∞ (1) e.g., take θq = 1/q. Theorem. If the step size is chosen as on the previous slides, and if (θq) satisfies (1), then the wq converges to the optimum for the Lagrangian dual. 26 The optimal multipliers and flows. 5 units good 1 1 $5 5 units good 1 4 $1 $1 $1 2 u25 = 5 3 units good 2 lim w q →∞ q 32 =1 1 x14 =2 5 2 2 2 x32 = x25 = x56 =2 $1 $1 u32 = 2 $6 3 1 1 1 x12 = x25 = x54 =3 6 2 x36 =1 3 units good 2 q lim w 25 =2 q →∞ 27 Suppose that w32 = 1.001 and w25 = 2.001 5 units good 1 1 $5 5 units good 1 4 $1 $1 1 x14 =5 $3.001 2 5 $1 $2.001 3 units good 2 2 x36 =3 3 $6 6 3 units good 2 Conclusion: Near Optimal Multipliers do not always lead to near optimal (or even feasible) flows. 28 Summary of MCF ‹ Applications ‹ Optimality Conditions ‹ Lagrangian Relaxation z subgradient optimization ‹ Next Lecture: Column Generation and more 29