Network Design - Chapter 5: Optimization Background for Network Design - University of Pittsburgh

Nội dung text: Network Design - Chapter 5: Optimization Background for Network Design - University of Pittsburgh

1. Optimization Background for Network Design David Tipper Associate Professor Department of Information Science and Telecommunications University of Pittsburgh tipper@tele.pitt.edu Slides 5 Network Design Tools • Optimization formulation to try and minimize cost – Metro and WANS Designed using computer aid tools – User provides set of traffic demands, geographic locations, and performance requirements TelcomTelcom 2110 2120 Spring 2 2006 2 1
2. Network Design Tools • Variety of tools available – WANDL, VPISystems, OPNET, RSOFT, etc. – trend is to develop tools for internal use only make money on consulting TelcomTelcom 2110 2120 Spring 3 2006 3 Optimization Review • Optimization Techniques – Seek to find maximum or minimum of a objective function – Set of unknown decision variables – Constraints limit the possible values for the variables • Definition – “A Mathematical Programming Model is a mathematical decision model for planning (programming) decisions that optimize an objective function and satisfy limitations imposed by mathematical constraints.” 1 1 T.W. Knowles, Management Science: Building and Using Models, Irwin, 1989. TelcomTelcom 2110 2120 Spring 4 2006 4 2
3. Types of Optimization Problems TelcomTelcom 2110 2120 Spring 5 2006 5 Simple Continuous Optimization •If Unconstrained – objective function F(X) is continuous function of x and x is continuous – Find MAX/MIN of F(x) by differentiation (set derivative = 0) – Determine if MAX or MIN by second derivative – If multi-dimensional – calculate gradient – use numerical gradient search methods – Newton's method gives rise to a wide and important class of algorithms that require computation of the gradient vector ∂φ ∂∂φφ ∇=++φ(,x yz ,) xˆˆ y zˆ ∂x ∂∂yz TelcomTelcom 2110 2120 Spring 6 2006 6 3
4. Constrained Optimization • General Symbolic Model Maximize (or minimize): f (x1, x2 Kxn ) Objective Subject to: g112( xx,K xn ) {≤≥= , ,} b 1 g212(){}xx,K xn ≤≥= , , b 2 Constraints gmn( xx12,K x) {≤≥= ,,} b m wherex1, x2 Kxn are the decision variables TelcomTelcom 2110 2120 Spring 7 2006 7 Mathematical Programming • Types of Mathematical Programs: – Linear Programs (LP): the objective and constraint functions are linear and the decision variables are continuous. – Integer (Linear) Programs (IP): one or more of the decision variables are restricted to integer values only and the functions are linear. • Pure IP: all decision variables are integer. • Mixed IP (MIP): some decision variables are integer, others are continuous. • 1/0 MIP: some or all decision variables are further restricted to be valued either “1” or “0”. – Nonlinear Programs: one or more of the functions is not linear. TelcomTelcom 2110 2120 Spring 8 2006 8 4
5. Linear Programming • General Symbolic Form Maximize: c1x1 + c2 x2 +Kcn xn Objective ax+++ ax ax ≤≥= ,, b Subject to: 11 1 12 2K 1nn { } 1 ax+++≤≥= ax ax {} ,, b 21 1 22 2K 2nn 2 Constraints axmm11+++≤≥= ax 2 2 K ax mnn { ,,} b m 0,≤=xjj 1,,K n Bounds where aij,bj ,cj are the model parameters. Maximize : c T x TelcomTelcom 2110 2120 Spring 9 2006 9 Linear Programming • Can be written in matrix formulation T Maximize: c x Objective Subject to: Ax = b Constraints Bounds 0 ≤ xj ∀ j where c, A, b are parameters TelcomTelcom 2110 2120 Spring 10 2006 10 5
6. Linear Programming • General Restrictions – All decision variables must be nonnegative x ≥ 0. – Constant terms cannot appear on the LHS of aj constraint. – No variable can appear on the RHS of a constraint. – No variable can appear more than once in a function, i.e. objective or constraint. • Steps for Formulating LP Models – Construct a verbal model. – Define the decision variables. – Construct the math model. • Feasible solution - set of all points satisfying all LP’s constraints and sign restrictions Optimal solution to an LP – a point in the feasible region with the largest objective function TelcomTelcom 2110 2120 Spring 11 2006 11 Formulating LP Problems •An example 2 – A steel company must decide how to allocate production time on a rolling mill. The mill takes unfinished slabs of steel as input and can produce either of two products: bands and coils. The products come off the mill at different rates and also have different profit-abilities: Tons/hour Profit/ton Bands 200 $25 Coils 140 $30 – The weekly production that can be justified based on current and forecast orders are: Maximum tons: Bands 6,000 Coils 4,000 2 from, R. Fourer, D. Gay, B. Kernighan, AMPL, Boyd & Fraser, 1993, pp. 2-10. TelcomTelcom 2110 2120 Spring 12 2006 12 6
7. Formulating LP Problems •Example (cont’d) – The question facing the company is: If 40 hours of production time are available, how many tons of bands and coils should be produced to bring in the greatest total profit? • Constructing the Verbal model – Put the objective and constraints into words. – For constraints, use the form {a verbal description of the LHS} {a relationship} {an RHS constant} Maximize: total profit Subject to: total number of production hours ≤ 40 tons of bands produced ≤ 6,000 tons of coils produced ≤ 4,000 TelcomTelcom 2110 2120 Spring 13 2006 13 Formulating LP Problems • Definine the Decision Variables – XB number of tons of bands produced. – XC number of tons of coils produced. • Construct the Symbolic Model Maximize: 25X B + 30X C Subject to: (1 200)X B + (1 140)X C ≤ 40 0 ≤ X B ≤ 6000 0 ≤ X C ≤ 4000 TelcomTelcom 2110 2120 Spring 14 2006 14 7
8. Solving LP Problems • Graphical Solution Method Coils Coils Constraints 220K Profit 6000 6000 Hours 192K XC XC 4000 4000 Optimal solution 2000 2000 Feasible region 120K Bands 0 Bands 0 0 2000 4000 6000 8000 0 2000 4000 6000 8000 XB XB Optimal Solution: XB = 6000, XC = 1400 Profit = 25*6000 + 30*1400 = $192,000 TelcomTelcom 2110 2120 Spring 15 2006 15 Solving LP Problems • 4 Possible Outcomes Unique Optimal Solution Alternate Optimal Solutions No Feasible Solution Unbounded Optimal Solution TelcomTelcom 2110 2120 Spring 16 2006 16 8
9. Solving LP Problems • In general problem is too complex for graphical solution • Simplex method – Efficient algorithm to solve LP problems by performing matrix operations on the LP Tableau – Developed by George Dantzig (1947) – Can be used to solve small LP problems by hand – Equivalent to checking corner points • For large problems interior point methods used which make steps through the middle of the feasible space in checking corner points. • Many software packages implement LP – General math/stats packages: Matlab, MS Excel, Maple, etc. – Specialized optimization packages : Lindo, AMPL/CPLEX, Minos, etc. Telcom 2120 17 Simplex Method • Find a basic feasible solution (maybe slack variable with base variable set to zero), move from corner to corner via swapping columns and eliminating slack variables. • Algorithm 1. Find a basic feasible solution and form tableau 2. Repeat 1. If call coefficients in objective row => 0 stop 2. Else, pick column with most negative coefficient 3. Pick row with least positive ratio of rhs/(column value) 4. Normalize Row so pivot value =one 5. Use Gaussian elimination to remove make rest of column zero Telcom 2120 18 9
10. LP Example • Two types of leather belts: deluxe and regular, each requires 1 sq. yard of leather • Each week: only 40 sq yard leather & 60 hrs of labor skill available • Regular belt: 1 hr labor -> $3 profit Deluxe belt: 2 hr labor -> $4 profit •Variable: x1 = # deluxe belts produced/wk x2 = # regular belts produced/wk • LP: maximize profit z = 4x1 + 3x2 s.t. x1 + x2 = 0 TelcomTelcom 2110 2120 Spring 19 2006 20 Simplex method for standard Max problem • From previous problem: maximize profit z = 4x1 + 3x2 subject to x1 + x2 = 0 • Step1: Convert LP to standard form – Add slack variable to each inequality constraint – Turn constraints to equations z - 4x1 -3x2 = 0 s.t. x1 + x2 + s1 = 40 2x1+ x2 + s2 = 60 TelcomTelcom 2110 2120 Spring 20 2006 1 10
11. Simplex method for standard Max problem • Step2: Write down the simplex tableau – Start with NBV = {x1, x2} and BV = {z, s1, s2} z x1 x2 s1 s2 rhs BV 1 -4 -3 0 0 0 z = 0 0 1 1 1 0 40 s1 = 40 0 2 1 0 1 60 s2 = 60 • Step3: Choose entering variable and do test ratio – entering variable: x1 (increase x1 one unit -> z increases 4 units) – Pivot row: row2 z x1 x2 s1 s2 rhs BV ratio Row 0: 1 -4 -3 0 0 0 z = 0 Row 1: 0 1 1 1 0 40 s1 = 40 x1 z increases one unit) – Pivot row: row1 z x1 x2 s1 s2 rhs BV ratio Row 0: 1 0 -1 0 2 120 z = 120 Row 1: 0 0 0.5 1 -0.5 10 s1 = 10 x2 <= 20 Row 2: 0 1 0.5 0 0.5 30 x1 = 30 x2 <= 60 TelcomTelcom 2110 2120 Spring 22 2006 3 11
12. Simplex method for standard Max problem • Optimal solution is reached – No new entering variable is found – x1 = 20, x2 = 20 with maximum profit at z = 4(20) + 3(20) = $140 per week Same Solution as graphical approach z x1 x2 s1 s2 rhs BV ratio 1 0 0 2 1 140 z = 140 0 0 1 2 -1 20 x2 = 20 0 1 0 -1 1 20 x1 = 20 TelcomTelcom 2110 2120 Spring 23 2006 3 Solving LP problems •Simplex method – Easy to use but to solve large problems need to use computer • AMPL and CPLEX – AMPL: modeling language (and software) for designing large and complex LP/IP problems. – CPLEX: software package (“solver”) to solve large and complex LP/IP problems. TelcomTelcom 2110 2120 Spring 26 2006 17 12
13. Example: Simplex Algorithm • Look at the LP problem (slide 14) solved graphically: Maximize: 25X B + 30X C Subject to: (1 200)X B + (1 140)X C ≤ 40 0 ≤ X B ≤ 6000 0 ≤ X C ≤ 4000 • Adding slack variables and covert LP to standard form Maximize: Z = 25XXB + 30 C Subject to: (1 200) XXSBC+ ( 1 140) +=1 40 XSB + 2 = 6000 XSC + 3 = 4000 XXSSSBC,,,,123≥ 0 TelcomTelcom 2110 2120 Spring 27 2006 18 Simple AMPL Example • Typing AMPL’s description into a file – prod0.mod var XB; var XC; maximize Profit: 25*XB + 30*XC; subject to Time: (1/200) * XB + (1/140) * XC <= 40; subject to B_limit: 0 <= XB <= 6000; subject to C_limit: 0 <= XC <= 4000; • Call AMPL commands: ampl: model prod0.mod ampl: solve; MINOS 5.5: optimal solution found 2 iterations, objective 192000 ampl: display XB, XC; XB = 6000 XC = 1400 ampl: quit TelcomTelcom 2110 2120 Spring 28 2006 19 13
14. Matlab Example • Look at the LP problem (slide 14) solved graphically: Maximize: 25X B + 30X C Subject to: (1 200)X B + (1 140)X C ≤ 40 0 ≤ X B ≤ 6000 0 ≤ X C ≤ 4000 In Matlab formulate LP problems as >> f = [-25 -30]; >>A = [1/200 1/140; 1 0; 0 1]; Minimize fx >> b = [40 6000 4000]; s.t. Ax > b = b'; >> [x,fval]=linprog(f,A,b) Optimization terminated. x = 1.0e+003 * 6.0000 1.4000 fval = -1.9200e+005 TelcomTelcom 2110 2120 Spring 29 2006 18 Integer Programming • Many problems in Network Design involve variables that are restricted to Integer Values – problems with such constraints are called Integer Programs • Consider previous LP Example (slides 12-14) – Assume that orders for bands and coils are placed (and filled) in 1,000s of pounds only. – Although feasible region is greatly reduced, problem becomes much more difficult. • New Symbolic Model – Let the new decision variables be the number of 1000 pound “units” or orders of bands and coils. Maximize: 25000X B′ + 30000X C′ Subject to: (1000 200)X B′ + (1000 140)X C′ ≤ 40 0 ≤ X B′ ≤ 6, integer 0 ≤ X C′ ≤ 4, integer TelcomTelcom 2110 2120 Spring 30 2006 23 14
15. Integer Programming • Graphical Solution Method Coils X’C 6 $185K Optimal integer solution ($185K) 4 2 Feasible integer solutions 0 Bands 0 2468 X’B TelcomTelcom 2110 2120 Spring 31 2006 24 Solving IP Problems • Branch-and-Bound Procedure – The solution space consists of a tree of LP subproblems, in which each integer variable is either fixed or its integrality constraint is “relaxed.” – The root node of the tree is the LP relaxation of the problem, i.e. all integer variables are relaxed. – The relaxation can result in an all integer solution, or a fractional solution (some decision variables are non-integer). – If the solution of the relaxation has fractional-valued integer variables, a fractional variable is selected for branching and two new subproblems are generated, each with more restrictive bounds on the branching variable. – The subproblems can result in an all integer solution, an infeasible problem or another fractional solution. – If the solution is fractional, the process is repeated. – Branches are “fathomed” if the subproblem is infeasible, the objective value is worse than the current best integer solution or the subproblem gives an integer solution. TelcomTelcom 2110 2120 Spring 32 2006 25 15
16. Solving MIP Problems • Branch-and-Bound Tree (Example) SP1:Bounds Solution 0 Z = $192K 2 XB=6, XC=1 => Z = $180K 0 Bands 0 Bands 02 4 6 8 02 4 6 8 XB XB TelcomTelcom 2110 2120 Spring 34 2006 27 16
17. Branch-and-Bound (cont’d) • Subproblem3: 0 Z = $188.57K XB=5, XC=2.1 => Z = $188K 2 2 0 Bands 0 02 4 6 8 02 4 6 8 X XB B TelcomTelcom 2110 2120 Spring 35 2006 28 Branch-and-Bound (cont’d) • Subproblem5: 0 Z = $185K XB=3.7, XC=3 => Z = $182.5K 2 2 0 Bands 0 02 4 6 8 02 4 6 8 X XB B TelcomTelcom 2110 2120 Spring 36 2006 29 17
18. Branch-and-Bound (cont’d) • Subproblem7: 6<=XB<=6 2<=XC<=4 Coils 6 XC 4 NO Feasible Solution 2 0 Bands 02 4 6 8 XB TelcomTelcom 2110 2120 Spring 37 2006 30 Algebraic Expression of LP/IP Problems • Why use it? – Most LP/IP problems are quite large and it becomes very cumbersome to describe them by explicitly giving each linear function, equality, and inequality in full. – It is desirable to model problems in a more general fashion (e.g. give an IP for optimally designing a mesh-restorable network in general as opposed to doing so for a specific network). – Formulate with Matrix Vector or Sum format TelcomTelcom 2110 2120 Spring 38 2006 31 18
19. Algebraic Expression of LP/IP Problems • Basic Production Model (Revisited) Original Model Algebraic Model Problem name: prob.lp Given: P, a set of products a = tons per hour of product j, for each j ∈ P Maximize j 25 XB + 30 XC b = hours available at the mill c = profit per ton of product j, for each j ∈ P Subject To j j ∈ P 0.005 XB + 0.007143 XC <= 40 u j = maximum tons of product j, for each Define variables: X = tons of product j to be made, for each j ∈ P Bounds j 0 <= XB <= 6000 0 <= XC <= 4000 Maximize: ∑c j X j j∈P End Subject to: ∑ (1 a j )X j ≤ b j∈P 0 ≤ X j ≤ u j , ∀j ∈ P TelcomTelcom 2110 2120 Spring 39 2006 32 AMPL model • Basic AMPL model (revisited) -prod0.mod set P; param a {j in P}; param b; param c {j in P}; param u {j in P}; var X {j in P}; maximize Total_Profit: sum {j in P} c[j] * X[j]; subject to Time: sum {j in P} (1/a[j]) * X[j] <= b; subject to Limit {j in P}: 0 <= X[j] <= u[j]; •model data–prod0.dat set P := bands coils; param: a c u := bands 200 25 6000 coils 140 30 4000; param b := 40; TelcomTelcom 2110 2120 Spring 40 2006 33 19
20. Network Design Optimization Formulations • Optimization Based Formulations widely used as a starting point in network design tools • Good Reference is M. Pioro and D. Medhi book Routing, Flow and Capacity Design in Communication and Computer Networks • Consider a couple of simple examples – Max Flow Assignment (routing problem) – Telephone Capacity Assignment Telcom 2120 41 Network Flow LP Formulations Example: LP to find max flow between nodes 1-5 20 2 10 Edge capacities: 4 1 2 5 8 3 20 5 Define directional flow variables: x42 2 x12 x 4 24 “trans-shipment nodes” 1 x 32 x source 23 x45 x13 3 5 sink x35 Source: W. D. Grover, ECE 681, UofA, Fall 2004 Telcom 2120 42 20
21. Network Flow LP Formulations (2) “transportation problem” or “arc-flow” approach To maximize (1 → 5) flow : /* using lp_solve syntax */ max: x12 + x13 ; /* (or x35 + x45) */ subject to constraints: c1: x12 + x13 = x45 + x35 ; /* source = sink */ c2: x12 + x32 - x23 + x42 - x24 = 0 ; /* node 2 trans-shipment*/ c3: x13 + x23 - x32 - x35 = 0 ; /* node 3 trans-shipment*/ c4: x24 - x45 - x42 = 0 ; /* node 4 trans-shipment*/ x42 x 2 12 4 x24 1 x 32 x 23 x45 x13 3 5 x35 Source: W. D. Grover, ECE 681, UofA, Fall 2004 Telcom 2120 43 Network Flow LP Formulations (3) “transportation problem” or “arc-flow” approach Continued Also subject to (capacity constraints): x12 < 20 ; 20 2 10 4 x13 < 8 ; 1 2 x24 < 10 ; 5 8 3 5 x42 < 10 ; 20 x23 < 2 ; x x 2 42 12 4 x32 < 2 ; x24 1 x32 x x35 < 20 ; 23 x45 x13 x45 < 5 ; 3 5 x35 Source: W. D. Grover, ECE 681, UofA, Fall 2004 Telcom 2120 44 21
22. Network Flow LP Formulations (4) “transportation problem” or “arc-flow” approach Symbolically max ∑ x1i 1,iE∈ s.t. ∑ x1ii= ∑ x 5 1,iE∈∈ 5, iE ∑ xxiNij=∀∈−∑ ji {{1,5}} ijE,,∈∈ ijE 0 ≤ x ≤∀∈sijE Where: ij ij E = set of edges that exist N = set of nodes sij = spare capacity on edge ij (= sji) Source: W. D. Grover, ECE 681, UofA, Fall 2004 Telcom 2120 45 Network Flow LP Formulations Alternate approach: “flow assignment to routes” or “arc-path” approach Symbolically max ∑ fi iP∈ 15 k s.t. ∑ fii⋅δ ≤∀∈skE k iP∈ 15 fi ≥∀∈0 iP15 Where: E = set of edges that exist (indexed by k) P 15= set of “eligible” distinct routes between nodes 1 and 5 (source-sink) sk = spare capacity on edge k k th δ i = 1 if the i distinct route crosses span k. Zero otherwise Source: W. D. Grover, ECE 681, UofA, Fall 2004 Telcom 2120 46 22
23. Network Flow LP Formulations (6) “flow assignment to routes” or “arc-path” approach - example Identify all distinct routes between source- sink (set P15) f1 2 f4 4 2 4 1 1 f2 3 5 3 5 f3 Route associated Route associated flow variable flow variable 1-2-4-5 f1 1-3-5 f3 1-2-3-5 f2 1-3-2-4-5 f4 Source: W. D. Grover, ECE 681, UofA, Fall 2004 Telcom 2120 47 Network Flow LP Formulations (7) “flow assignment to routes” or “arc-path” approach - example (2) To maximize (1 -> 5) flow : max: f1 + f2 + f3 + f4 ; subject to constraints: c1: f1 + f2 <= 20 ; /* link 12 capacity */ c2: f4 + f3 <= 8 ; /* link 13 capacity */ c3: f4 + f2 <= 2 ; /* link 23 capacity */ c4: f1 + f4 <= 10 ; /* link 24 */ f1 20 2 10 f4 4 2 4 1 20 10 2 1 2 5 f2 8 3 5 5 20 8 3 5 f3 20 Source: W. D. Grover, ECE 681, UofA, Fall 2004 Telcom 2120 48 23
24. Network Flow LP Formulations (8) “flow assignment to routes” or “arc-path” approach - example (2) What are the remaining constraints ? : - for link 3-5 ?: c5: f3 + f2 <= 20; /*link 35 capacity */ - for link 4-5 ? c6: f4 + f1 <= 5; /*link 45 capacity */ (note this makes prior constraint f4 + f1<=10 redundant ) f1 f4 20 2 10 2 4 20 10 4 1 1 2 5 2 5 f2 8 3 5 20 8 3 5 f3 20 Source: W. D. Grover, ECE 681, UofA, Fall 2004 Telcom 2120 49 Network Flow LP Formulations (9) “flow assignment to routes” or “arc-path” approach - example (3) • Note that the k “indicator” parameters do not appear explicitly in the δ i executable model. • Really they just represent our knowledge of the topology and the routes being considered. • Implicitly above, we only wrote the flow variables that had non-zero coefficients. 12 Examples: δ = 1 (flow1 crosses span 12) Hence f1 is in the first constraint 1 δ 35 = 1 (flow3 crosses span 35) 3 Hence f3 is in the fifth constraint, etc. Source: W. D. Grover, ECE 681, UofA, Fall 2004 Telcom 2120 50 24
25. Sonet/STM Design Problem Telcom 2120 51 Complexity - Solving Design Problems • Real world Network Design problems are quite large (have many variables and constraints) – Graph Theory and Optimization Based algorithms for network design are complex – when can one use a technique? • Complexity of an algorithm usually denotes O(.) which denotes the order of time growth in the algorithm as a function of problem variables – Dijkstra’s Algorithm for SPT O(N2) where N is number of nodes in graph – Prim’s Algorithm for MST O(E log(N)) where N is # nodes, E # edges • Problems that can be solved by a deterministic algorithm in a polynomial time complexity denoted P that is O(Nk) • Problems that can not be solved with P complexity denoted NP and don’t scale well – Linear Programming Problems have P complexity – Integer Programming Problems have NP complexity • Still Branch and Bound can be used for small problems ! • In general for NP problems use Sub-optimal algorithms (meta-heuristics) – Simulated annealing – Genetic algorithms – Tabu search Telcom 2120 52 25