Optimization Methods Introduction

Optimization Methods 1 Structure of Class Linear Optimization (LO): Lec. 1-9 Slide 1 Network Flows: Lec. 10-11 Discrete Optimization: Lec. 12-15 Dynamic Optimization: Lec. 16 Nonlinear Optimization (NLO): Lec. 17-25 2 Requirements Slide 2 Homeworks: 30% Midterm Exam: 30% Final Exam: 40% Use of Matlab for solving optimization problems 3 Lecture Outline Slide 3 History of Optimization Where LOPs Arise? Examples of Formulations 4 History of Optimization Fermat, 1638 Newton, 1670 min f (x) x: scalar df (x) = 0 dx 1 Slide 4 Euler, 1755 min f (x1 : : : xn) rf (x) = 0 Lagrange, 1797 min f (x1 : : : xn) s.t. gk (x1 : : : xn) = 0 k = 1 : : : m Euler, Lagrange Problems in innite dimensions, calculus of variations. 5 Nonlinear Optimization 5.1 The general problem min f (x1 : : : xn) s:t: g1(x1 : : : xn)
0 .. . gm (x1 : : : xn)
0: Slide 5 6 What is Linear Optimization? 6.1 Formulation c= 3 1
minimize 3x1 + x2 subject to x1 + 2x2  2 2x1 + x2  3 x1  0 x2  0

  x 2 1 2 1 x = x2 b= 3 A= 2 1 minimize c x subject to Ax  b Slide 6 0 x0 7 History of LO 7.1 The pre-algorithmic period Fourier, 1826 Method for solving system of linear inequalities. de la Vallee Poussin simplex-like method for objective function with absolute values. 2 Slide 7 Kantorovich, Koopmans, 1930s Formulations and solution method. von Neumann, 1928 game theory, duality. Farkas, Minkowski, Caratheodory, 1870-1930 Foundations. 7.2 The modern period George Dantzig, 1947 Simplex method. 1950s Applications. 1960s Large Scale Optimization. 1970s Complexity theory. Khachyan, 1979 The ellipsoid algorithm. Karmakar, 1984 Interior point algorithms. Slide 8 8 Where do LOPs Arise? 8.1 Wide Applicability Slide 9 Transportation Air trac control, Crew scheduling, . . . Movement of Truck Loads Telecommunications Manufacturing Medicine Engineering Typesetting (TEX, LATEX) 9 Transportation Problem 9.1 Data m plants, n warehouses si supply of ith plant, i = 1 : : :m dj demand of jth warehouse, j = 1 : : :n cij : cost of transportation i ! j 3 Slide 10 9.2 Decision Variables 9.2.1 Formulation xij = number of units to send i ! j m X n X min cij xij i=1 j =1 m X s:t: xij = dj i=1 n X xij = si j =1 xij  0 Slide 11 j = 1 : : :n i = 1 : : :m 10 Sorting through LO Given n numbers c1 c2 : : : cn The order statistic c(1) c(2) : : : c(n): c(1)
c(2)
: : :
c(n)  P Use LO to nd ki=1 c(i) . n X min ci xi i=1 n X s:t: xi = k i=1 0
xi
1 i = 1 : : : n 11 Investment under taxation You have purchased si shares of stock i at price qi, i = 1 : : : n. Current price of stock i is pi You expect that the price of stock i one year from now will be ri. You pay a capital-gains tax at the rate of 30% on any capital gains at the time of the sale. You want to raise C amount of cash after taxes. You pay 1% in transaction costs. Example: You sell 1,000 shares at $50 per share you have bought them at $30 per share Net cash is: 50  1 000 ; 0:30  (50 ; 30)  1 000; 0:01  50  1 000 = $43 500: 4 Slide 12 Slide 13 11.1 Formulation n X max i=1 n Slide 14 ri (si ; xi ) X n n X X s:t: pi xi ; 0:30 (pi ; qi)xi ; 0:01 pi xi  C i=1 i=1 i=1 0
xi
si 12 Investment Problem Slide 15 Five investment choices A, B, C, D, E. A, C, and D are available in 1993. B is available in 1994. E is available in 1995. Cash earns 6% per year. $1,000,000 in 1993. 12.1 Cash Flowper Dollar Invested Year: A B C D E 1993 1994 1995 1996 -1.00 +0.30 +1.00 0 0 -1.00 +0.30 +1.00 -1.00 +1.10 0 0 -1.00 0 0 +1.75 0 0 -1.00 +1.40 $500,000 NONE $500,000 NONE $750,000 LIMIT Slide 16 12.2 Formulation 12.2.1 Decision Variables A : : :E: amount invested in $ millions Casht : amount invested in cash in period t, t = 1 2 3 max 1:06Cash3 + 1:00B + 1:75D + 1:40E s:t: A + C + D + Cash1
1 Cash2 + B
0:3A + 1:1C + 1:06Cash1 Cash3 + 1:0E
1:0A + 0:3B + 1:06C ash2 A
0:5 C
0:5 E
0:75 A ::: E  0 5 Slide 17 Solution: A = 0:5M , B = 0, C = 0, D = 0:5M , E = 0:659M , Cash1 = 0, Cash2 = :15M , Cash3 = 0 Objective: 1:7976M 13 Manufacturing 13.1 Data Slide 18 n products, m raw materials cj : prot of product j bi : available units of material i. aij : # units of material i product j needs in order to be produced. 13.2 Formulation 13.2.1 Decision variables Slide 19 xj = amount of product j produced. n X max cj xj j =1 s:t: a11x1 +    + a1nxn
b1 .. . am1 x1 +    + amn xn
bm xj  0 j = 1 : : :n 14 Capacity Expansion 14.1 Data and Constraints Dt : forecasted demand for electricity at year t Et : existing capacity (in oil) available at t ct : cost to produce 1MW using coal capacity nt : cost to produce 1MW using nuclear capacity No more than 20% nuclear Coal plants last 20 years Nuclear plants last 15 years 6 Slide 20 14.2 Decision Variables Slide 21 14.3 Formulation Slide 22 xt : amount of coal capacity brought on line in year t. yt : amount of nuclear capacity brought on line in year t. wt : total coal capacity in year t. zt : total nuclear capacity in year t. T P min ct xt + ntyt t=1 Pt s:t: w = t s=max(0 t;19) Pt xs t = 1 : : :T ys t = 1 : : :T zt = s=max(0 t 14) wt + zt + Et  Dt zt
0:2(wt + zt + Et) xt yt wt zt  0: ; 15 Scheduling 15.1 Decision variables Slide 23 Hospital wants to make weekly nightshift for its nurses Dj demand for nurses, j = 1 : : : 7 Every nurse works 5 days in a row Goal: hire minimum number of nurses Decision Variables xj : # nurses starting their week on day j 15.2 Formulation P7 x min 7 j =1 s:t: x1+ x1 + x1 + x1 + x1 + xj  0 Slide 24 x2 x2 + x2 + x2 + x2 + x3 x3 + x3 + x3 + x3 + x4 + x5 + x6 + x5 + x6 + x6 + x4 + x4 + x5 x4 + x5 + x6 x4 + x5 + x6 + 7 x7 x7 x7 x7       x7  d1 d2 d3 d4 d5 d6 d7 16 Revenue Management 16.1 The industry Deregulation in 1978 Prior to Deregulation { Carriers only allowed to y certain routes. Hence airlines such as Northwest, Eastern, Southwest, etc. { Fares determined by Civil Aeronautics Board (CAB) based on mileage and other costs (CAB no longer exists) Post Deregulation anyone can y, anywhere fares determined by carrier (and the market) Slide 25 Slide 26 17 Revenue Management 17.1 Economics Huge sunk and xed costs Very low variable costs per passenger ($10/passenger or less) Strong economically competitive environment Near-perfect information and negligible cost of information Highly perishable inventory Result: Multiple fares Slide 27 18 Revenue Management 18.1 Data n origins, n destinations 1 hub 2 classes (for simplicity), Q-class, Y-class Revenues rijQ rijY Capacities: Ci0, i = 1 : : :n C0j , j = 1 : : :n Expected demands: DijQ , DijY 8 Slide 28 18.2 LO Formulation 18.2.1 Decision Variables Slide 29 : # of Q-class customers we accept from i to j : # of Y-class customers we accept from i to j X maximize r Q +r Y � Qij � Yij Q ij subject to X i j n �0 Y ij ij ij (Q + Y ) � C 0 ij ij i X j n �0 (Q + Y ) � C0 ij i 0�Q ij ij Q � Dij j 0�Y ij Y � Dij 19 Revenue Management 19.1 Importance Robert Crandall, former CEO of American Airlines: Slide 30 We estimate that RM has generated $1.4 billion in incremental revenue for American Airlines in the last three years alone. This is not a one-time benet. We expect RM to generate at least $500 million annually for the foreseeable future. As we continue to invest in the enhancement of DINAMO we expect to capture an even larger revenue premium. 20 Messages 20.1 How to formulate? 1. Dene your decision variables clearly. 2. Write constraints and objective function. 3. No systematic method available. What is a good LO formulation? A formulation with a small number of variables and constraints, and the matrix A is sparse. 9 Slide 31 21 Nonlinear Optimization 21.1 The general problem Slide 32 min f (x1 : : : xn) s:t: g1(x1 : : : xn)
0 .. . gm (x1 : : : xn)
0: 22 Convex functions f : S ;! R For all x1 x2 2 S f (x1 + (1 ; )x2 )
f (x1 ) + (1 ; )f (x2 ) Slide 33 f (x) concave if ;f (x) convex. 23 On the power of LO 23.1 LO formulation min f (x) = maxk dk x + ck s:t: Ax  b min z s:t: Ax  b dk x + ck
z 8 k 0
Slide 34 0 24 On the power of LO 24.1 Problems with Idea: jxj = maxfx ;xg j:j P min cj jxj j s:t: Ax  b Pc z min j j s:t: Ax  b xj
zj ;xj
zj Message: Minimizing Piecewise linear convex function can be modelled by LO 10 Slide 35