Non-Linear Programming

Location Problems Basic Concepts of Location Last IP modeling tricks Dispel Misconception Introduce NLP First Heuristic 1 Where to Locate Facilities Rectilinear Location Problems Euclidean Location Problems Location - Allocation Problems 2 Basic Intuition On the line, if the objective is to min … The maximum distance traveled The maximum distance left + right The distance traveled there and back to each customer The item-miles traveled 0 1 4 3 Rectilinear Distance Travel on the streets and avenues Distance = number of blocks East-West + number of blocks North-South Manhattan Metric 4 Rectilinear Distance 9 5 4 5 Locate a facility... To minimize the sum of rectilinear distances Intuition Where? Why? 6 Minimize the sum of Rectilinear distances to customers X Y 9 9 8 3 0 4 4 2 0 5 0 Total 9 3 6 9 6 2 0 0 9 2 0 0 Xdist Ydist - - If Left If Right If Above If Below 9.00 (9.00) (9.00) 9.00 9.00 (9.00) (3.00) 3.00 8.00 (8.00) (6.00) 6.00 3.00 (3.00) (9.00) 9.00 6.00 (6.00) 4.00 (4.00) (2.00) 2.00 4.00 (4.00) 2.00 (2.00) 9.00 (9.00) 5.00 (5.00) (2.00) 2.00 10 9 8 7 6 Y Solver Model Cust. 1 2 3 4 5 6 7 8 9 10 Facility 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 10 X 7 Locate a facility... To minimize the max of rectilinear distances Intuition Where? Why? 8 Models Set Customers; Param X{Customer}; Param Y{Customer}; var Xloc >= 0; var Yloc >= 0; var Xdist{Customer}; var Ydist{Customer}; 9 Constraints DefineXdist1{c in Customer}: Xdist[c] >= X[c]-Xloc; DefineXdist2{c in Customer}: Xdist[c] >= Xloc-X[c]; DefineYdist1{c in Customer}: Ydist[c] >= Y[c]-Yloc; DefineYdist2{c in Customer}: Ydist[c] >= Yloc-Y[c]; 10 Objective Total Distance: sum{c in Customer}(Xdist[c]+Ydist[c]); Maximum Distance? 11 Min the Max! Var Xloc; var Yloc; var Xdist{Customer}>= 0; var Ydist{Customer}>= 0; var dmax; min objective: dmax; s.t. DefineMaxDist{c in Custs}: dmax >= Xdist[c] + Ydist[c]; 12 Min the Max Cont’d DefineXdist1{c in Customer}: Xdist[c] >= X[c]-Xloc; DefineXdist2{c in Customer}: Xdist[c] >= Xloc-X[c]; DefineYdist1{c in Customer}: Ydist[c] >= Y[c]-Yloc; DefineYdist2{c in Customer}: Ydist[c] >= Yloc-Y[c]; 13 Mimimize the Maximum Rectilinear Distance X 9 9 8 3 0 4 4 2 0 5 0 Total Y Max Total Xdist Ydist If Left If Right If Above If Below -9 9 9 0 0 0 0 9 -9 -3 3 3 0 0 0 0 9 -9 6 0 0 0 0 8 -8 -6 6 -9 9 9 0 0 0 0 3 -3 6 0 0 0 0 0 0 -6 6 2 0 0 0 0 4 -4 -2 2 0 0 0 0 0 4 -4 0 0 0 0 0 0 0 0 0 2 -2 9 0 0 0 0 0 0 -9 9 -2 2 2 0 0 0 0 5 -5 0 0 0 1 10 9 8 7 6 Y Solver Model Customer 1 2 3 4 5 6 7 8 9 10 Facility 5 4 3 2 1 0 2 3 4 5 6 7 8 9 10 X 14 Challenge #3 NIMBY…. Maximize the Minimum Distance How did you do it? 15 Cust. 1 2 3 4 5 6 7 8 9 10 Facility X 9 9 8 3 0 4 4 2 0 5 Y Min Total Xdist Ydist Left? Above? If Left If Right If Above If Below 9 0 0 29 -9 11 9 3 0 0 29 -9 17 3 6 0 0 28 -8 14 6 9 0 0 23 -3 11 9 6 0 0 20 0 14 6 2 0 0 24 -4 18 2 0 0 0 24 -4 20 0 0 0 0 22 -2 20 0 9 0 0 20 0 11 9 2 0 0 25 -5 18 2 Total 10 9 8 7 6 Y NIMBY Mimimize the Maximum Rectilinear Distance 5 4 3 2 1 0 0 1 2 3 4 5 X 6 7 8 9 10 Disjunctive Constraints One of Two Constraints holds Ydist = TownY – DumpY Ydist = DumpY – TownY Binary Variable Chooses 1 Ydist ≤ TownY – DumpY + 20*Left Ydist ≤ DumpY – TownY + 20*(1-Left) Only 1 matters (20 is big) Objective drives the right choice These are hard for the solver 17 Outline Rectilinear Location Problems Euclidean Location Problems Location - Allocation Problems 18 Locating a single facility Distance is not linear Distance is a convex function Local Minimum is a global Minimum 19 S21 S19 S17 S15 S13 S11 S9 S7 S5 S3 S1 What kind of function? 20 Where to Put the Facility Total Cost = Σ ckdk(x,y) = Σ ck√(xk- x)2 + (yk- y)2 ∂Total Cost/∂x = Σ ck (xk - x)/dk(x,y) ∂Total Cost/∂x = 0 when x = [Σckxk/dk(x,y)]/[Σck/dk(x,y)] y = [Σckyk/dk(x,y)]/[Σck/dk(x,y)] But dk(x,y) changes with location... 21 Iterative Strategy Start somewhere, e.g., x = [Σckxk]/[Σck] y = [Σckyk]/[Σck] as though dk= 1. Step 1: Calculate values of dk Step 2: Refine values of x and y x = [Σckxk/dk]/[Σck/dk] y = [Σckyk/dk]/[Σck/dk] Repeat Steps 1 and 2. ... 22 Solver Model: Not Linear Facility 4.5 4.283971 4.241999 4.239085 4.239961 4.238616 4.235342 4.23113 4.226679 4.222382 4.21843 4.214899 4.211803 4.209121 4.206817 4.6 4.0907 3.73981 3.486694 3.298874 3.15693 3.048107 2.963646 2.897385 2.844914 2.80302 2.769336 2.742087 2.719928 2.701827 50.88679 50.35772 50.11444 49.9801 49.90163 49.85438 49.82525 49.80693 49.79522 49.78763 49.78265 49.77935 49.77714 49.77565 49.77464 Center of Gravity Better Answer 23 Euclidean Location 5 45.8 4.5 45.6 4 45.4 3.5 3 Distance Location 45.2 2.5 45 2 1.5 44.8 1 44.6 0.5 0 44.4 1 2 3 4 5 6 7 8 Iteration 9 10 11 12 13 14 15 X Y Distance Euclidean Location X Y 9 9 8 3 0 4 4 3 0 5 4.5 4.283971 4.241999 4.239085 4.239961 4.238616 4.235342 4.23113 4.226679 4.222382 4.21843 4.214899 4.211803 4.209121 4.206817 9 1 10 9 6 2 0 0 9 0 4.6 4.0907 3.73981 3.486694 3.298874 3.15693 3.048107 2.963646 2.897385 2.844914 2.80302 2.769336 2.742087 2.719928 2.701827 4.217658 2.805268 d(x,y) 6.293648 5.762812 6.43506 4.648656 4.712749 2.64764 4.627094 4.838388 6.293648 4.627094 50.88679 50.35772 50.11444 49.9801 49.90163 49.85438 49.82525 49.80693 49.79522 49.78763 49.78265 49.77935 49.77714 49.77565 49.77464 1/d(x,y) 0.15889 0.173526 0.155399 0.215116 0.21219 0.377695 0.216118 0.20668 0.15889 0.216118 2.090624 d(x,y) 6.807507 5.638559 6.980594 5.074427 4.690185 2.109897 4.100544 4.287471 6.515646 4.152893 1/d(x,y) 0.146897 0.17735 0.143254 0.197067 0.213211 0.473957 0.24387 0.233238 0.153477 0.240796 2.223116 d(x,y) 7.092825 5.490459 7.301544 5.404827 4.806559 1.75656 3.747632 3.940653 6.757525 3.815855 1/d(x,y) 0.140988 0.182134 0.136957 0.18502 0.208049 0.569294 0.266835 0.253765 0.147983 0.262064 2.35309 d(x,y) 7.284426 5.371216 7.521146 5.65083 4.928139 1.505796 3.494881 3.70032 6.954595 3.568757 1/d(x,y) 0.137279 0.186178 0.132958 0.176965 0.202916 0.664101 0.286133 0.270247 0.14379 0.28021 2.480777 d(x,y) 7.427032 5.286094 7.683943 5.83441 5.027261 1.320854 3.30759 3.524213 7.104936 3.385296 1/d(x,y) 0.134643 0.189176 0.130142 0.171397 0.198915 0.757086 0.302335 0.283751 0.140747 0.295395 2.603587 10 9 8 7 6 Y Customer 1 2 3 4 5 6 7 8 9 10 Facility 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 10 X 25 Moving On Example of Convex Minimization (Nonlinear) Example of a Heuristic: Not guaranteed to give us the best answer, but works well. 26 Locating Several Facilities Fixed Number of Facilities to Consider Single Sourcing Two Questions: Location: Where Allocation: Whom to serve Each is simple Together they are “harder” 27 Iterative Approach Put the facilities somewhere Step 1: Assign the Customers to the Facilities Step 2: Find the best location for each facility given the assignments (see previous method) Repeat Step 1 and Step 2 …. 28 Assign Customers to Facilities Uncapacitated (facilities can be any size) “Greedy”: Assign each customer to closest facility Capacitated Use Optimization: Single-sourcing 29