Network Optimization Multicommodity Flows 2

Multicommodity Flows 2 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 3 units good 2 3 u32 = 2 $6 $1 6 3 units good 2 3 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 4 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. 5 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. 6 Another approach: path-based approach ‹ ‹ ‹ Represent flows from sk to tk as the sum of flows in paths. The resulting LP may have an exponential number of columns Use “column generation” to solve the LP. 7 A Linear Multicommodity Flow Problem 5 units good 1 1 $5 $1 P1 = set of paths from node 1 to node 4. $1 $1 2 5 u25 = 5 $1 3 units good 2 5 units good 1 4 3 P1 = {1-4, 1-2-5-4} u32 = 2 $6 $1 6 P2 = set of paths from node 3 to node 6. 3 units good 2 P2 = {3-6, 3-2-5-6} 8 A path based formulation c(1-4) c(1-2-5-4) c(3-6) c(3-2-5-6) f(P) = flow in path P c(P) = cost of path P = = = = 5 3 6 3 Minimize 5 f(1-4) + 3 f(1-2-5-4) + 6 f(3-6) + 3 f(3-2-5-6) subject to f(1-4) + f(1-2-5-4) = 5 f(3-6) + f(3-2-5-6) = 3 f(1-2-5-4) + f(3-2-5-6) ≤ u25 = 5 f(3-2-5-6) ≤ u32 = 2 f(P) ≥ 0 for all paths P 9 Optimal solution for the path based version 5 units good 1 1 $5 $1 $1 f(1-4) = 2 f(3-6) = 1 $1 f(1-2-5-4) = 3 2 5 u25 = 5 $1 3 units good 2 5 units good 1 4 3 u32 = 2 $6 f(3-2-5-6) = 2 $1 6 3 units good 2 The path based LP can be solved using the simplex method. 10 General formulation for the path based version Let Pk = set of directed paths from sk to tk Let ck(P) = cost of path P ∈ Pk. ⎧1 if (i,j) ∈ P Let δ ij ( P ) = ⎨ ⎩ 0 otherwise Let f(P) = flow on path P. Master Problem Minimize ∑∑ ck ( P ) f ( P ) k P∈P k ∑∑δ k P∈P k ∑ ij ( P ) f ( P ) ≤ uij f (P) = d k for all ( i , j ) ∈ A for k = 1 to K P∈P k f (P) ≥ 0 for P ∈ K ∪ k =1 Pk 11 Minimize ∑∑ ck ( P ) f ( P ) k P∈P k ∑∑δ k P∈P k ∑ ij ( P ) f ( P ) ≤ uij for all ( i , j ) ∈ A f (P) = d k P∈P k f (P) ≥ 0 for P ∈ K ∪ Pk k =1 bundle constraints: one for each capacitated arc. supply demand constraints: one for commodity. variables: one for each path from origin to destination 12 Column Generation Approach: Generate paths as needed Let Sk = subset of Pk = directed paths from sk to tk Let ck(P) = cost of path P ∈ Sk. ⎧1 if (i,j) ∈ P Let δ ij ( P ) = ⎨ ⎩ 0 otherwise Let f(P) = flow on path P. Restricted Master Problem Minimize ∑∑ ck ( P ) f ( P ) k P∈S k ∑∑δ k P∈S k ∑ ij ( P ) f ( P ) ≤ uij f (P) = d k for all ( i , j ) ∈ A for k = 1 to K P∈S k f (P) ≥ 0 for P ∈ K ∪ k =1 Sk 13 Solving the Master Problem 1. 2. 3. Initialize Sk for each k. Solve the restricted master problem for paths in S = ∪k Sk obtaining solution x = (xk). Check to see if x is optimal for the master problem. If not, find new paths to add to S and return to step 2. 14 Towards Optimality conditions for the master and restricted master Restricted Master Problem Minimize ∑∑ ck ( P ) f ( P ) k P∈S k ∑∑δ k P∈S k ∑ ij ( P ) f ( P ) ≤ uij for all ( i , j ) ∈ A f (P) = d k P∈S k f (P) ≥ 0 for P ∈ K ∪ Sk k =1 Let w = (wij) be a set of non-negative tolls on the arcs. c w ,k ij = c + wij k ij c w ,k ( P ) = ∑ ( i , j )∈P cijw ,k 15 Illustration of definitions 5 units good 1 1 $5 $1 Suppose w32 = 1 c w ,2 32 = 1+1 3 units good 2 5 units good 1 4 $1 Suppose w25 = 2.5 $1 2 w25 = 2.5 $1 w32 = 1 $6 3 5 $1 6 w ,2 c25 = 1 + 2.5 = 3.5 3 units good 2 c w ,2 (3 − 2 − 5 − 6) = 2 + 3.5 + 1 = 6.5 16 Optimality conditions for the restricted master A flow f is optimal for the restricted master if it is feasible, and if there is a non-negative vector w of tolls on arc so that the following is true: 1. 2. w ij > 0 ⇒ ∑ ∑δ k P ∈S k ij (P )f (P ) = uij for all (i,j) ∈ A f (P ') > 0 for P' ∈ Sk ⇒ c w ,k (P ') = min (c w ,k (P ) : P ∈ S k ) The tolls w are produced by the LP solution to the restricted master. Optimality for the master problem is the same except that Sk is replaced by Pk. 17 On the optimality conditions f(P’) > 0 P’ sk tk P Suppose that the optimality conditions are not satisfied, and that c(P’) > c(P). The residual network G(xk) has Rev(P’). Rev(P’) + P is a circulation with negative cost. Thus G(xk) has a negative cost cycle. 18 Adding paths or proving optimality Let f be optimal for the restricted master 1. 2. w ij > 0 ⇒ ∑ ∑δ k P ∈S k ij (P )f (P ) = uij for all (i,j) ∈ A f (P ') > 0 for P' ∈ Sk ⇒ c w ,k (P ') = min (c w ,k (P ) : P ∈ S k ) Let Pk be the shortest path from sk to tk using cw,k . If Pk ∈ Sk for each k, then f is optimal for the master problem because condition 1 and condition 2 are both satisfied when we replace Sk by Pk for each k. Otherwise, add Pk to Sk for each k, and solve the new restricted master problem. 19 More on optimality conditions We used partial dualization. That is, we had optimality conditions that used w, but not node potentials. In usual column generation, one would use LP optimality conditions, which are more detailed, but follow the same general approach. 20 Restricted Master Problem 1 c(1-4) c(1-2-5-4) c(3-6) c(3-2-5-6) f(P) = flow in path P c(P) = cost of path P = = = = 5 3 6 3 Minimize 5 f(1-4) + 3 f(1-2-5-4) + 6 f(3-6) + 3 f(3-2-5-6) subject to f(1-4) + f(1-2-5-4) = 5 f(3-6) + f(3-2-5-6) = 3 f(1-2-5-4) + f(3-2-5-6) ≤ u25 = 5 f(3-2-5-6) ≤ u32 = 2 f(P) ≥ 0 for all paths P 21 Optimal solution for restricted master 1 5 units good 1 1 $5 $1 $1 f(3-6) = 3 $1 f(1-4) = 5 2 5 u25 = 5 $1 3 units good 2 5 units good 1 4 3 u32 = 2 $6 w25 = 0; w32 = 0 $1 6 3 units good 2 The unique shortest path for commodity 1 is 1-2-5-4. The unique shortest path for commodity 2 is 3-2-5-6. 22 Restricted Master Problem 2 Suppose we add path 3-2-5-6 to the restricted master f(P) = flow in path P c(1-4) c(1-2-5-4) c(3-6) c(3-2-5-6) = = = = 5 3 6 3 c(P) = cost of path P Minimize 5 f(1-4) + 3 f(1-2-5-4) + 6 f(3-6) + 3 f(3-2-5-6) subject to f(1-4) + f(1-2-5-4) = 5 f(3-6) + f(3-2-5-6) = 3 f(1-2-5-4) + f(3-2-5-6) ≤ u25 = 5 f(3-2-5-6) ≤ u32 = 2 f(P) ≥ 0 for all paths P 23 Optimal solution for restricted master 2 5 units good 1 1 $5 $1 $1 $1 f(1-4) = 5 2 $1 3 u32 = 2 $6 $1 6 f(3-6) = 1 f(3-2-5-6) = 2 5 u25 = 5 3 units good 2 5 units good 1 4 w25 = 0; w32 = 3 3 units good 2 The unique shortest path for commodity 1 is 1-2-5-4. The shortest paths for commodity 2 are 3-2-5-6 and 3-6 24 Restricted Master Problem 3 We next add path 1-2-5-4 to the restricted master f(P) = flow in path P c(1-4) c(1-2-5-4) c(3-6) c(3-2-5-6) = = = = 5 3 6 3 c(P) = cost of path P Minimize 5 f(1-4) + 3 f(1-2-5-4) + 6 f(3-6) + 3 f(3-2-5-6) subject to f(1-4) + f(1-2-5-4) = 5 f(3-6) + f(3-2-5-6) = 3 f(1-2-5-4) + f(3-2-5-6) ≤ u25 = 5 f(3-2-5-6) ≤ u32 = 2 f(P) ≥ 0 for all paths P 25 Optimal solution for the path based version 5 units good 1 1 $5 $1 $1 $1 f(1-4) = 2 2 f(1-2-5-4) = 3 3 u32 = 2 $6 $1 6 f(3-6) = 1 f(3-2-5-6) = 2 5 u25 = 5 $1 3 units good 2 5 units good 1 4 w25 = 2; w32 = 1 3 units good 2 The solution is optimal for the entire problem. 26 Column Generation Added variables Initial variables Constraints Restricted Master Problem (RMP) > trillions of Variables Variables that were never considered 27 Choices in running column generation ‹ Starting columns ‹ How many columns to generate at a time ‹ Which LP solver to use ‹ and more 28 Some running times CPU time in seconds Multicommodity flow times 1600 1400 1200 1000 800 600 400 200 0 Generate one column per iteration Generate several columns per iteration 0 2 4 6 8 10 12 Problem Number 301 nodes, 497 arcs, 1320 commodities. Times are on an IBM RS6000/590. 29 The number of iterations per problem Number of Iterations 12000 Generate one column per iteration 10000 8000 6000 4000 Generate several columns per iteration 2000 0 0 2 4 6 8 10 12 Problem Number 30 Iterations per second Number of iterations per second 35.0 30.0 Generate one column per iteration 25.0 20.0 15.0 10.0 5.0 Generate several columns per iteration 0.0 0 5 10 15 Problem Number 31 Decomposition in LPs ‹ The following slides will generalize our approach here to solving “staircase structure LPs” ‹ Here we relied on the fact that a flow of dk units from sk to tk can be decomposed into the sum of flows along paths. ‹ However, for the more general problem, we will rely on the fact that any feasible solution x in a bounded polyhedron can be expressed as a convex combination of its corner points. 32 Convex Hulls in two dimensions Each feasible point in an LP may be expressed as a convex combination of its corner points. 33 Staircase structure LPs -z x1 x2 x3 x4 xK 1 c1 c2 c3 c4 cK = -z0 0 N 0 0 0 0 = b1 0 0 N 0 0 0 = b2 0 0 0 N 0 0 = b3 0 0 0 0 N 0 = b4 0 0 0 0 0 N = bK 0 A1 A2 A3 A4 AK ≤ u 34 Another view of staircase structures Network flow problem, commodity k=1 Network flow problem, commodity k=2 Network flow problem, commodity k=3 Network flow problem, commodity k=4 Bundle constraints limiting total flow of all commodities to arc capacities 35 On Staircase LPs These staircase structures are superb for trying Lagrangian relaxation. They are also good for Dantzig-Wolfe decomposition. In Dantzig-Wolfe decomposition, we will represent each xk as the convex combination of corner points of {x: Nxk = bk and x ≥ 0} , assuming the polyhedron is bounded. 36 Dantzig Wolfe Decomposition Nx k = b k for k = 1, 2, ..., k (17.1c) Any solution to 17.1c can be expressed as the convex combination of corner points. Make the replacement in the original problem. The new variables are the corner points of 17.1c for each k. The constraints Nxk = bk are all replaced. The remaining constraints are the bundle constraints. 37 Linear MCF Problem Solution ‹ G = (N, A) with K commodities. |N| = n, |A| = m. ‹ A standard solution approach z LP Solver such as CPLEX ‹ Difficulty „ Node-arc formulation: z Constraints: nK +m z Variables: mK „ Path formulation: z Constraints: m + K z Variables: |Paths for ALL commodities| 38 Summary ‹ Multicommodity Flows ‹ Column generation approach z Path-based generalization z Generalization to Dantzig-Wolfe Decomposition ‹ Relies on optimality conditions ‹ Solving restricted master problems 39