Lecture 1 Notes: Formulations

Structure of Class 1 Formula,tionn: Lcc. I Ctcomct,ry: Lcc. 2-4 Simplex l\lcthoi:l: Lcc. 5-8 Duality Thcory: Lc,:. 9-11 Sensitivity .-inalysin: Lei:. 12 Robust Optimization: Lcc. 1 3 Large ncalc ol:,timizat,ion: Lcc. 14-15 Nctmork F l o ~ i s :Lcc. 16-17 The Ellipsi:,ii:l methi:,,$: Lcc. 18-19 Interior 1:)oint mcthoi:ls: Lcc. 20-21 . 2 Scmii:lcfinitc opt,imizatii:,n: Lcc. 22 ~ b.. il ~ c~t cOpt,imizatii:,n: , Lcc. 24-2; Requirements Homcmorkn: 30%) Mii:ltcrm Exam: 30%) Final Exam: 40% Iml:,ortant tic brakcr: cont,ribut,ionst,o ,class Lnc of CPLEX fi:n si:,lving ol:,timiza,tion problems 3 Lecture Outline History of Optimizatio~l Whcrc LOPS Arisc? Examplcs of Fi:,rmulatii:,ns 4 History of Opti~rlization Fermat, 1638: Newton, 1670 mi11 f(r) x : scalar Euler, 1755 Lagrange, 1707 nlin ~ ( s .I. .,. r,") s.t,. (Jk(1.1,. . . : r,")= 0 k = 1 , .. . , 77L Euler, Lagrange Prol:,lcms in in fin it,^ dimcnsii:,ns, iralirulus of variat,ions. 5 5.1 6 6.1 Nonlinear Optirrlizatiovl The general problem What is Linear Optimization? Forlnt~lat,ioli + + mininlizc 31.1 1.2 sul,jcct ti:, 1.1 21.2 21.1 + 1.2 1.1 ~ninimizc sul,jcct ti:, 2 0.1.2 22 23 >0 c'z 2h z20 Az 7 History of LO 7.1 Tlie pre-algorit,hmic period Fonrier, 1826 Mct,hoil for solving synbcm of linear inc,:lualit,ics. de la Val1i.e Poussirl simplcx-like mcthoi:l fin ol,jcct,ivc functii:,n wit,h al:,ii:,lute values. vo11 Nenlnann, 1028 game t,hcory, iluality. Farkas, Minkowski: Caratl~i.odory,1870-1930 Fi:,un,Sa,tionn 7.2 Tlie lnoderll period George Dantzig. 1047 51ml,lcx mcthoil 1950s Applicat,ions. 1960s Large Siralc Opt,imizat,ion. 1970s Complexity thci:,ry. 1979 The cllipsi:,ii:l algi:,rit,hm. 1980s Interior pi,int algi:,rit,hmn. 1990s Scnlidcfinit,c all<\conic ~ ~ t i ~ n i r a t i o n . 2000s Ri:,bust Ol:,timizat,ion. Where do LOPS Arise? 8 . 8.1 Wide Applicabilit,y Transportat,ion Air traffic ci:,nt,ri:,l,Crew schci:luling, >Iovcmcnt i:,f Truck Loails Trar~sportatiollProblem 9 .. . Dat,a 9.1 171 .si supply 9.2 9.2.1 rij plants. ti,? 11 ~snrchouscs of i t h plant, i = 1. . . m i:lcrnnn,S of j t h >iarchousc, j = I . . . 11 Decision Variables Fur~~l~~latiuri = numl:,cr i:,f units t,o send i i j 10 Sorting through LO 11 Invest ~ r ~ e vurlder ~ t taxation .. You have purchnsci:l .5i sharcs Cl~rrrcntprice of stock i is pi i:,f stock i at pricc yi. i = 1, . . . . 11 You cxpcct that the l:,ricc i:,f stock i i:,nc scar fii:,m now will bc ri You ]:,a- a cal:,ital-gains t,ax a t thc rat? of 30% ,311 any capital gains at t,hc t,imc i:,f the sale. You want ti:, raise C ami:,unt of crash aft,cr taxes. You pay 1%) in transaction costs Example: You sell 1.000 shares a t $50 per sharc; you ha,~:cbought them a t $30 per sharc: Vet cash is: SO x 1.000 - 0.30 x (SO - 30) x 1,000 Five invcstmcnt choices .-i. B. C , D.E .-i. C , and D arc a,~:ailal:,lcin 1993. B is availablc in 1994. Cash carns 6% per year. S1.OOO.OOO in 1993. 12.1 C;asli Flowper Dollar Ilivest,ed . Decision Variables 12.2.1 .I, . . . E: amount invcst,cd in Y; millions C'~I,../I~: ami:,unt invcstcd in cash in pcrii:,d t , t = 1.2 , 3 max 1.0GCu.~h3 + 1.00B + 1 . i 5 D + 1.40E s.t. . l + C:+D+ C'udhl 5 1 CIA.S/L~B 5 0.3.1+ l . l C + l.OGC'u.~hl Cil.sI~3 l.OE l . O l + 0.3A + 1.06C'ash2 + + Manufacturing 13 13.1 Data 11 l:,roilucts, m raw nlatcrials a,~:ailal:,lcunits of material i . hi: aij: 13.2 13.2.1 rj = < # units of nlatcrial i proi:luct j needs in ori:lcr Formulat,ion Decision variables amount i:,f pri:,,Suct j pri:,iSucc,S. n max C qis,i j=l ti:, lbc proi:lucc,S. Capacity Exparlsiovi 14 14.1 Data and C;olistraiilt,s Dt: fc,rccast,ccl clcmani:l fi:n electricit,:: a t ::car t Et: cxisti~lgcal:,acity (in oil) nvailablc nt t c,: ci:,st ti:, l:,roclucc 11\I\\' lit: cost ti:, using coal capncity proi:lucc 1MTV using nuclcnr c n p a c i t , ~ No morc than 20% nu,rlca,r Coal plants last 20 ycnri Nuclear plants Inst 15 :7cars 14.2 Decision Variables r,: ami:,unt of yt: nmount i:,f ci:,al cal:,acity brought on lint in ycar t. capncit,:: I:,rought i:,n line in ycnr t. u:,: tot,nl ci:,al cal:,acity in ycar zt: t,otal 15 15.1 t. cnpacit,:: in :;car t . Scheduling Decision variables Hospital ~ i a n t ,ti:, s mnkc >icckl:: night,shift fi:,r its llurscs D , iicmancl fi:n nurses, j = 1. . . T Evcry llursc works 5 clays in a ri:,m Goal: hire mininl~lmnnrnbcr of nurses Decision Variables nurscs startiqg t,hcir week i:,n cia- j rj: # 16 16.1 Revenue Managerrlerlt The indust,ry Deregulation in 1978 - - Clarricrs only allowc~iti:, fly ircrt,ain ri:,utcs. Hcnirc airlincs such as iYi:,rt,h~scst.Eastern, Southwest, ctc. Fares ilct,cr~nincilI:,:: Clivil Acrona,utics Boaril (CAB) lbascil on mileage and othcr ci:,st,s (C.4B no li:,ngcr exists) Post D e r c g l ~ l a t i ~ n anyone ,ran fly, anywhcrc farcs ~ i c t c r m i n c ~ I:,yi carrier (and thc markct) 17 . Revenue Managerrlerlt Huge sunk anil fixcil cost,s Vcry li:,m variablc ci:,st,s pcr passenger ($lO/passcngcr i:,r lcss) Strong cci:,nomically ci:,mpctitivc cnvironmcnt Ncar-pcrfcct infi:,rmat,ion and ncgligil:,lc ci:,st of infi,rmatii:,n Highly pcrishal:,lc invcnt,ory Result: l\lult~il~lc farcs SLII)E26 Revenue Managerrlerlt 18 18.1 . . . Data 11 origins. 11 ilcstinatii:,ns I hub 2 irlasscs (for simplicity), (2-class. Ti-class R c ~ c n u c sT,! ZJ Ca1:)acitics: 1.j.;. i = I .. . . T I ; Expected iicnlancls: 18.2 LO Forillulatioil .. Decision Variables 18.2.1 D:) Q,,: # o f Q-class cu~tomersme accept from i t o j 1;,: # of Y-class cu~tomers accept from i t o j maximize 19 C,0.i. .I. = I , . . . I L zr.,::c2%, +v:,Y;, Revenue Managerrlerlt F\'c c s t i m a t , ~t,hat RVI hns gcncrat,cil $1.4 billion in in,rrcmcntal rcvcnuc fi,r Anlcri,ran Airlines in the last three ycnrs ali:,nc. This is not a i:,nc-time benefit. F\'c c x p r t RM t o gcncrat,c at lcnst $500 millii:,n nnnually for the fi:,rcsccnl:,lc future. .-is me continue t o invest in the cnhanccmcnt of DIV.-i?rlO me cxl:,cct t,o cnpt,urc nn even lnrgcr rcvcnuc premium. 20 20.1 Messages How t,o formulate? 1. Define your ilccision variables clearly. 2. ITrritc ci:,nstraints ani:l ol:,jcctivc funct,ion. What is a good LO for~ril~latiorl? A fi,rmulation with numl:,cr of variaI:,lcs anil const,raint,s,anil t,hc mat,rix A is sparse. a 21.1 22 . . 23 The general proble~ll Convex furlctiorls f :.S+R For all sl.s 2E ,Y + ( l h ) s ? )5 Xf(sl)+(lPA)f(s2) f(As1 ,f (z) ci:,ncavc if f (z)ci:,nvcx. - 0 x 1 the power of LO min .5.t. f (z)= maxi, Az 3b dn z + ci, 24 0x1the power of LO min n.t. Idea: 1x1 = max{s, s ] C t,j Az l.cjl 2b C mi11 qiqi 5.t. Ax 2 b r.i 5 z.? " j 5 zj Message: >Iinimizing Picirc~sisclincnr convex functii:,n ,ran lbc moi:lcllcil I:,y LO