Introduction to Stochastic Programming

1 1 CUSTOM Conference, December 20011 Introduction to Stochastic ProgrammingJohn R. BirgeNorthwestern UniversityCUSTOM Conference, December 20012 Outline Overview Examples Vehicle Allocation Financial planning Manufacturing Methods View ahead2 CUSTOM Conference, December 20013 Overview Stochastic optimization Traditional Small problems Impractical Current Integrate with large-scale optimization ( Stochastic Programming ) Practical examples Expanding rapidlyCUSTOM Conference, December 20014 Vehicle Allocation Decision: How to position empty freight cars?NOW:AB5 cars0 carsDAY 1:DAY 2:ABABDEMAND:DAY 1: B to A:Mean Value=2 DAY 1: A to B:Mean Value=2??223 CUSTOM Conference, December 20015 Maximize:Revenue-Cost MOVE TWO EMPTY CARS FROM A to BNOW:AB5 cars0 carsDAY 1:DAY 2:ABABRESULT:Net 2: A to B; Net 2: B to ATOTAL(MV) = 43122 Parameters: COST: per empty car from A to BREVENUE: per full car from A to B222 Vehicle Allocation: Mean Value SolutionCUSTOM Conference, December 20016 Find: Expected(Revenue-Cost) MOVE TwoEMPTY CARS FROM A to BNOW:AB5 cars0 carsDAY 1:DAY 2:ABABE xpected Value:Net 2: A to B; Net 2: B to A ( 2/3)-1: B to A ( 1/3)TOTAL (EMV): 323 ( )2 Suppose: Demand is Random (Expectationfrom A to B=2) 0 from A to B with prob.

2 1/3 3 from A to B with prob. 2/3 2 ( 2/3)222 ( 1/3)1 Expectation of Mean Value4 CUSTOM Conference, December 20017 Maximize: Expected(Revenue-Cost) MOVE ThreeEMPTY CARS FROM A to BNOW:AB5 cars0 carsDAY 1:DAY 2:ABABE xpected Value:Net 2: A to B; Net 3: B to A ( 2/3) : B to A ( 1/3)TOTAL (RP): Problem23 ( )2 Suppose: Demand is Random (as before)GOAL: A solution to obtain highest expected value3 ( 2/3)233 ( 1/3)1 Stochastic Program SolutionCUSTOM Conference, December 20018 INFORMATION and MODEL VALUE INFORMATION VALUE: FIND Expected Value with Perfect Information or Wait-and-See (WS) solution: Know demand: if 3, send 3 from A to B; If 0, send 0 from A to B: Earn: 2 (AtoB) + (2/3) (3) + (1/3)0= 4 = WS Expected Value of Perfect Information (EVPI): EVPI = WS - RP = 4 - = Value of knowing future demand precisely MODEL VALUE: FIND EMV, RP Value of the Stochastic Solution (VSS): VSS = RP - EMV= - 3 = Value of using the correct optimization model5 CUSTOM Conference, December 20019 INFORMATION/MODEL OBSERVATIONS EVPI and VSS: ALWAYS >= 0 (WS >= RP>= EMV) OFTEN DIFFERENT (WS=RP but RP > EMV and vice versa) FIT CIRCUMSTANCES: COST TO GATHER INFORMATION COST TO BUILD MODEL AND SOLVE PROBLEM MEAN VALUE PROBLEMS: MV IS OPTIMISTIC (MV=4 BUT EMV=3, RP= ) ALWAYS TRUE IF CONVEX AND RANDOM CONSTRAINT PARAMETERS VSS LARGER FOR SKEWED DISTRIBUTIONS/COSTSCUSTOM Conference, December 200110 Stochastic PROGRAM ASSUME:Random demand on AB and BA GOAL:maximize expectedprofits (risk neutral) DECISIONS.

3 Xij- empty from i to j yij(s) - full from i to j in scenario s (RECOURSE) (prob. p(s)) FORMULATION:Max + s=s1,s2 p(s) ( yAB(s) + yBA(s)) +xAA= 5 (Initial)-xAB+ yBA(s) <= 0 (Limit BA)-xAA+ yAB(s) <= 0 (Limit AB)yBA(s) <= DBA(s) (Demand BA)+ yAB(s)<= DAB(s) (Demand AB)xAA, XAB, yAA(s), yAB (s)>=0 EXTENSIONS: Multiple stages;Constraint/objective complexity (Powell et al.)6 CUSTOM Conference, December 200111 Where to Install Capacity for Different Models among Different Plants?A123B Where to add flexibility? (multiple models)Manufacturing CapacityCUSTOM Conference, December 200112 Key: Evaluate Expected Optimal with Installed CapacityMust choose best mix of models assigned to plantsMaximize i Profit (i) Production(i)subject to: MaxSales(i) >= j Production(i at j) i Production(i at j) <= Capacity (i) Production(i at j) <= Capacity (i at j)Production(i at j) >= 0 Transportation Problem Need MaxSales(i) - random - unknown distribution Capacity(i at j) - Decision in First StageRecourse Payoff Evaluation7 CUSTOM Conference, December 200113 Model Data: from Graves/Jordan Vary: Model Lifetimes Longer => More flexibility Start: 1 YearABCDEF123456 OriginalNewSolution ResultsCUSTOM Conference, December 200114 Financial Planning GOAL:Accumulate $G for tuition Y years from now Assume.

4 $ W(0) - initial wealth K - investments concave utility (piecewise linear)GW(Y)UtilityRANDOMNESS:returns r(k,t) - for k in period twhere Y T decision periods8 CUSTOM Conference, December 200115 FORMULATION SCENARIOS: Probability, p( ) Groups, St1, .., StSt at t MULTISTAGE Stochastic NLP FORM:max p( ) ( ) ( ) ( ) ( U(W( , T) ) (for all ): kx(k,1, ) = W(o) (initial) kr(k,t-1, ) x(k,t-1, ) - kx(k,t, ) = 0 , all t >1; kr(k,T-1, ) x(k,T-1, ) - W( , T) = 0, (final);x(k,t, ) >= 0, all k,t;Nonanticipativity:x(k,t, ) - x(k,t, ) = 0 if , Stifor all t, i, , This says decision cannot depend on Conference, December 200116 DATA and SOLUTIONS ASSUME: Y=15 years G=$80,000 T=3 (5 year intervals) k=2 (stock/bonds) Returns (5 year): Scenario A: r(stock) = r(bonds)= Scenario B: r(stock) = r(bonds)= Conference, December 200117 GENERAL MULTISTAGE MODEL FORMULATION:MIN E [ t=1 Tft(xt,xt+1) ] XtxtnonanticipativeP[ ht(xt,xt+1) <= 0 ] >= a (chance constraint)EXAMPLES:Vehicle Allocation: Linear functions, continuous orinteger variablesCapacity: Linear plus integer variablesFinancial Planning: Nonlinear objective, continuous variablesCUSTOM Conference, December 200118 DECOMPOSITION METHODS BENDERS IDEA FORM AN OUTER LINEARIZATION OF t - VALUE FUNCTION AT STAGE t ADD CUTS ON FUNCTION.)

5 TLINEARIZATION AT ITERATION kmin at k : < tnew cutITERATE BETWEEN STAGES UNTIL ALL MIN = t10 CUSTOM Conference, December 200119 DECOMPOSITION IMPLEMENTATION NESTED DECOMPOSITION LINEARIZATION OF VALUE FUNCTION AT EACH STAGE DECISIONS ON WHICH STAGE TO SOLVE, WHICH PROBLEMS AT EACH STAGE LINEAR Programming SOLUTIONS USED OSL/CPLEX FOR LINEAR SUBPROBLEMS USE MINOS FOR NONLINEAR PROBLEMS PARALLEL IMPLEMENTATIONCUSTOM Conference, December 200120 RESULTS SCAGR7 PROBLEM SETLOG (NO. OF VARIABLES)LOG (CPUS)345671234 OSL NESTED :60-80% EFFICIENCY IN SPEEDUPOTHER PROBLEMS: SIMILAR RESULTS ONLY < ORDER OF MAGNITUDE SPEEDUP WITH STORM - TWO-STAGES - LITTLE COMMONALITY IN SUBPROBLEMS- STILL ABLE TO SOLVE ORDER OF MAGNITUDE LARGER PROBLEMS11 CUSTOM Conference, December 200121 View Ahead New Trends Methods for integer variables Power system implementations Vehicle routing Integrating simulation Sampling with optimization On-line optimization Low-discrepancy methodsCUSTOM Conference, December 200122 More Trends Modelinglanguages Ability to build Stochastic programs directly Integrating across systems Using application structure Separation of problem (dimension reduction) Network properties Generalized versions of convexity12 CUSTOM Conference, December 200123 Summary Increasingapplication base Valuefor solving the Stochastic problem Efficientimplementations Opportunitiesfor new results