Step Decision Rules For Multistage Stochastic Programming .

2y ago
55 Views
3 Downloads
423.92 KB
31 Pages
Last View : 2m ago
Last Download : 2m ago
Upload by : Jerry Bolanos
Transcription

Step decision rules for multistage stochasticprogramming: a heuristic approachJ. Thénié J.-Ph.Vial September 27, 2006AbstractStochastic programming with step decision rules, SPSDR, is an attempt to overcome the curse of computational complexity of multistage stochastic programmingproblems. SPSDR combines several techniques. The first idea is to work with independent experts. Each expert is confronted with a sample of scenarios drawn atrandom from the original stochastic process. The second idea is to have each expertwork with step decision rules. The optimal decision rules of the individual expertsare then averaged to form the final decision rule. The final solution is tested on avery large sample of scenarios. SPSDR is then tested against two alternative methods: regular stochastic programming on a problem with 3 stages and 2 recourses;robust optimization with affinely adjustable recourses on a 12-stage model. The performance of the new method turns out to be competitive on those examples, whileit permits a tighter control on computational complexity than standard stochasticprogramming.Acknowledgements The authors acknowledge the support of Fonds National Suisse dela Recherche Scientifique, grant # 100012-1053091IntroductionMany real-life problems are concerned with sequential decision making under uncertainty.Unfortunately, those problems are difficult. The authors of [22] “. . . argue that multistage problems, even linear [. . . ] with complete recourse, generically are computationallyintractable already when medium-accuracy solutions are sought.” Indeed, the complexity of computing expectations with respect to a multidimensional stochastic process indiscrete time grows exponentially with the dimensionality of the process and the numberof stages. The same authors add the reassuring statement: “Of course, this does notmean that some specific cases of multi-stage stochastic programming problems cannot besolved efficiently. Note that this claim is rather a belief than a statement which we can HEC/Logilab/Department of Management Studies, University of Geneva, 40 Bd du pont d’Arve,CH-1211 Geneva 4, Switzerland.1

rigorously prove.” Other authors [9] argue that multistage stochastic programming is atleast as difficult as hard combinatorial problems. In view of the practical importance ofthe problems to solve, it is not absurd to look for computationally tractable heuristics.Because a heuristic approach does not produce solutions that are provably optimal, onehas to resort to empirical analysis to test the performance of the heuristic.Stochastic programming with step decision rules (SPSDR) is one such heuristic. Itaims to find efficient contingent strategies for convex stochastic control problems, withlinear dynamic constraints and unconstrained state variables. The SPSDR scheme is asfollows. At each stage t, one constructs a partition of the set of scenarios based on pasthistory. The decision rule consists in assigning to a decision variable the same value for allscenarios belonging to the same element of the partition. In general, one associate with ascenario at stage t a multi-dimensional random variable representing past history. In thissetting, a decision rule as described above can be viewed as a step function on the spaceof outcomes of the variable. Hence the name, step decision rule, SDR in short. A decisionrule based on the sole past history meets the non-anticipativity requirement, even thoughthe partition at stage t 1 need not be a refinement of stage t. This property gives morefreedom in the design of the partitions. In particular, the number of contingent variablesin successive stages is not bound to grow in a multiplicative manner as it does on thestandard SP approach. This gives a way to get around the issue of exponential growth ofthe event tree.The main feature of SPSDR is that it applies to any given discrete realizations, orscenarios, of the stochastic process. No preprocessing such as aggregation and scenarioreduction [15] is required. SPSDR works with the original stochastic information, butreplaces the original decision process by a more restrictive one. Thus, instead of approximating the stochastic process by a computationally tractable event tree as in [15], werestrict the original decision process to a sub-optimal but manageable one.The choice of efficient partitions is a critical issue. The first concern is the numberνt of elements in the partition at stage t. Since a decision rule stipulates that the samedecision is to be applied at all sub-scenarios that hit the same element of the partition,one sees that the partition reflects the knowledge or ignorance at t in the decision processinduced by the decision rule. The minimal value νt 1 for all t means total ignorance:the decision to be taken at t is unique, independent of the stochastic process realizations.The problem of finding a good decision rule becomes simple, but the solution is likelyto be inefficient. The maximal value νt N for all t, where N is the total number ofscenarios means perfect foresight: the decision to be taken at stage t is fully adapted tothe realizations. In that case, the problem of finding a good decision rule has N timesthe size of the previous one. Intermediary values for νt reflect partial knowledge, butwe do not require that the partitions be nested. In other words, we allow, in our searchof decision rules, forgetfulness of the past. The intermediary case compromises betweenperfect foresight versus total ignorance and small size versus large size for the decisionrule selection problem.The second concern is to achieve a meaningful partition at each t when the number ofelements νt is given. To do this, we need a measure of quality of a partition. We proceedas follows. We first associate with each element of the partition a realization (or sub2

scenario) of the stochastic process. We call this sub-scenario the reference sub-scenariofor the element of the partition and we attach to it the probability that a scenario hits thiselemental set. This defines a reduced stochastic process. We then introduce a distancebetween the reduced process and the process associated with the full set of sub-scenarios(ending at t). Following [19] and [15], we choose the Kantorovitch functional to measurethis distance. The goal is to find a partition that minimizes this distance; this problem isequivalent to solving a p-median problem.We have no theoretical argument to select the sequence νt : we resort to empiricaltesting. The efficiency of a decision rule is measured by its performance on the full setof original scenarios instead of the small sampled subset that was used to compute therule. At this point, we must give a word of explanation on the way we extend a decisionrule computed on a sub-sample of scenarios to the entire set of scenarios. This is done byextending the partition of the sub-sample to a partition of the original set of scenarios.Each scenario in the original set is assigned to the closest reference sub-scenario in thesense of the chosen distance measure.The concept of linear decision rules, in short LDR, appeared in the early ’60 in thecontext of optimal stochastic control. It has been developed to solve production planningproblems [16] with quadratic objectives. LDR, have been used long ago in the more general context of stochastic programming and chance-constrained programming [12], butsomehow neglected since. They were recently resurrected in [5] in the framework of Robust Optimization under the name of Affinely Adjustable Robust counterpart (AARC).AARC offers a computationally tractable alternative to multi-stage problems with uncertain data. Successful applications of this approach to multistage inventory managementproblems is reported in [1, 4, 6]. These works stimulated investigation of LDR in stochastic programming [22]. With LDR the true decision variables are the coefficients of theaffine functions. They have to be fixed in the initial stage. In that respect, stochasticprogramming with LDR (SPLDR) transforms a multistage SP in an Act-and-See problem, i.e., into a two-stage problem with no recourse. If the initial problem is linear, theSPLDR restriction is also linear and tractable. Unfortunately, it does not seem possible toassess the loss of optimality. The authors of [22] justify the use of LDR with the followingheuristic argument: “The rationale behind restricting affine decision rules is the beliefthat in actual applications it is better to pose a modest and achievable goal rather thanan ambitious goal which we do not know how to achieve”. The concept of step decisionrules seems to be new. As SPLDR, it leads to computationally tractable problems.It is possible to improve SPSDR by taking convex combinations of independent SDR’s.By convexity of the problem, such combination is feasible and expected value of theoutcome is smaller (better) than the same convex combination of the outputs of theindividual SDR’s. It is convenient to view the optimization over a sample of scenarios asthe output of an “expert” facing a problem instance associated with a small size sampleof realizations of the stochastic process. The average solution can be interpreted as theproposal of a pool of experts. The idea of building several decision rules from independentsamples is directly inspired by [18]. A similar use of experts is described in [10, 11] in theframework of machine learning.Our experiments apply to stochastic control problems in the area of inventory man3

agement in the context of supply chain management. Our primary goal is to compare theSPSDR approach to stochastic programming and robust optimization on two problemson which those methods perform well. The first set of experiments compares SPSDR withthe standard stochastic programming (SP) approach on the well-known newsboy problemwith 3 stages. The main conclusion is that SPSDR can produce as good solutions as SP.The second set of experiments deals with the model of retailer-supplier flexible commitments contracts, (RSFC). The model has 12 stages; it is not easily amenable to standardSP but AARC solutions are computed in [4]. On this problem, SPSDR is computationallytractable and can accommodate a variety of objective functions, such as min-max, theexpected shortfall (or conditional value at risk), the total expected costs or criteria mixingrisk measures and expected costs.The paper is organized as follows. Section 2 gives the general formulation of thestochastic control problem. Section 3 discusses an implementation of standard stochastic programming on this class of problems. Section 4 is devoted to the presentation ofstochastic programming with step decision rules. In Section 5, we report the results ofour empirical study on two different problems. The last section is a short conclusion.2The stochastic control problemWe consider the deterministic control problem with horizon Tminφ(x1 , . . . , xT , u1 , . . . , uT 1 )xt At xt 1 Bt ut 1 Ct , t 2, . . . Tgt (u1 , . . . , ut ) 0, t 1, . . . T 1x1 x̄1 .(1a)(1b)(1c)(1d)In that problem, ut and xt are multidimensional real variables, At and Bt are matricesof appropriate dimensions and Ct is a vector. The variable ut is the control and xt isthe state variable. We assume that gt is convex in (u1 , . . . , ut ) and φ is jointly convex in(x1 , . . . , xT ) and (u1 , . . . , uT 1 ), respectively. For the sake of simplicity, we shall use inthe sequel the more restrictive formulation with a separable objectiveφ(x1 , . . . , xT , u1 , . . . , uT 1 ) T 1Xft (xt , ut ) fT (xT ).t 1The problem becomes stochastic when the components of (1) depend on the realization{ξt }Tt 1 of the sequence of random variables {ξ t }Tt 1 . We make a fundamental assumptionon the stochastic processAssumption 1 The stochastic process is independent of the decision process.The stochastic process {ξ t }Tt 1 is endowed with the probability space (Ξ, S, µ), where Ξis the sample space and S is the σ-algebra of measurable events with respect to µ. If thesample space has finite support, S is made of all subsets of the finite set of outcomes. It4

is also convenient to introduce the probability spaces (Ξt , St , µt )Tt 1 of partial realizationsσt (ξ1 , . . . , ξt ). The event spaces St form a nested sequence of subsets of S : S1 S2 . . . , ST .We follow the convention that the selection of the control at t (decision) follows theunfolding of uncertainty at t. We have the sequence[chance move]1 [decision]1 · · · [chance move]t [decision]t . . .If Ξ1 is not a singleton, the decision problem breaks down into independent subproblems.Thus we assume that Ξ1 {ξ1 } is a singleton. The sequential structure of the problemimplies that the decision, i.e., control, at t must be made contingent to the history σt {ξ1 , . . . , ξt }. That is, ut is a function of σt , denoted ut (σt ). In view of the state equation(1b), the state variable xt must also be made contingent to σt . The stochastic version ofthe control problem (1) is thusminT 1XE[ft (xt (σt ), ut (σt ), ξt ) fT (xT (σT ), ξT )](2a)t 1xt (σt ) At (ξt )xt 1 (σt 1 ) Bt (ξt )ut 1 (σt 1 ) Ct (ξt )a.e., t 2, . . . Tgt (u1 (σ1 ), . . . , ut (σt )) 0, a.e, t 1, . . . T 1x1 x̄1 .3(2b)(2c)(2d)Stochastic programmingSo far we only assumed independence of the stochastic process with respect to the decisions. If we further assume finiteness of the sample space, the stochastic control problemcan be formulated as a stochastic programming problem and solved as a standard (largescale) mathematical programming problem.The main problem in sequential decisions under uncertainty is the way uncertaintyunfolds over time. If uncertainty unfolds at once at some stage t, the problem essentiallybecomes a two-stage one and the flavor of sequential decision-making is lost. We areinterested in the case of progressive unfolding: the stochastic programming formulationshould reflect this fact.We distinguish different phases in a stochastic programming approach to a controlproblem. We review them quickly.Phase 0: Statistical analysis and samplingIn sequential decision making under uncertainty, it is often the case that the underlyingstochastic process is best described in continuous time and space whereas the decisionprocess is in discrete time. Multi-stage stochastic programming starts with a statisticalpre-processing phase consisting in identifying the stochastic process and estimating itsparameters. The next operation consists in sampling scenarios using the distribution ofthe estimated process. If the underlying process is continuous the scenarios obtained in5

that manner are almost surely all different as from stage 2 and look like a fan. Thisrepresentation does not capture the progressive unfolding of uncertainty over time and isnot fit, as such, to model the decision process.Phase 1: Scenario reduction and aggregationA multi-period decision process associated with a fan of scenarios is essentially a twostage problem. The usual remedy consists in building a new discrete time/discrete valuesstochastic process that “best” approximates the fan of scenarios. This new process isrepresented by a tree, that unfolds with time. If the tree gradually “opens up” with time,as shown in Figure 1, the decision process based on that tree better captures the adaptivenature of the decisions. It is shown in the literature that under suitable assumptions,one can build a balanced tree with the property that the optimal solution of the problembased on that tree provides an estimate of the optimal value of the original problem.j pp pp pp pp pp pp pujp p pppupp pppp pppp pppp pppp pppp pp ppppppppppp pp pp pp pujp p p p p p p p p p pjjp p pp pp pp pp p pupppppppjp p p p p j p p p p p p p p p p p p p p jpp pp pp pp pp pp pp pp pp pp pp pup p p p"pp pp pp pp pp ppp p pup"ppppppppppjj pp pp pp pp pp pp pujppppp "p"jp pbp p p p p j pp pp pp pp pp pp pp pujppppp j@ pbJp pbpp pp pppp pppp pppp pppp pp ppp p pupppppppppppppppp pp pp pp puppppp j p p p p p p p p pJ@ bjjpp p p p p p p pp ppppppJ @ pp upjJ @ j p p p p p p p p p p p p p p p jpp pp pp pp pp pp pp pp pp pp pp pupppppuppppppppppJ jj pp pp pp pp pp pp pp pujJjt 1t 2t 3t 4Figure 1: A balanced tree approximating a fanThis phase is described as a scenario reduction and aggregation scheme. We referto the literature [15] for a detailed description of a scenario reduction and aggregationscheme. To measure the quality of an approximation, some papers use the so-calledKantorovitch functional [19, 15]. We postpone the definition of this distance measure tothe next section.Phase 2: Formulating and solving the deterministic equivalentIn this phase, one adapt the decision process to the balanced tree generated in the previous phase. This operation consists in making the controls, the state variables andthe constraints at stage t contingent to each individual stage-t-node in the event tree.This produces a new problem, the so-called deterministic equivalent, whose formulationinvolves many more variables and constraints than the deterministic version. This operation is formal but tedious; it can be made easier by tools like the one described in [23].The optimal solution of the deterministic equivalent problem provides a prediction of theoptimal value of the original problem. It also outputs a solution, consisting of values6

for the controls at each node of the tree. The solution is thus a stochastic process, withwell-defined values on the tree nodes.Phase 3: ValidationThere exist approximation theorems, e.g., [19], that stipulate that under some regularityconditions the optimal expected value of the control problem on the approximation treetends to the optimal value of the original stochastic control problem. Such results donot say much on how the optimal controls in the deterministic equivalent can be usedto determine controls for the original problem and, if this extension can be performed,whether it achieves an objective function value close to the optimum. Those questionsare seldom addressed in the literature.For our study, it is important to implement and test the computed solutions. Weproceed as follows. Suppose a scenario is drawn at random according to the probabilitydistribution of the original stochastic process. This scenario is almost surely different fromall scenarios of the event tree underlying the deterministic equivalent problem. To findwhich control which control to apply at stage t, we consider the sub-scenario up to t andlook for the closest sub-scenario up to t of the event tree of the deterministic equivalent.The latter determines the control to be applied at t.It is easy to see that the above operation induces a partition on the set of scenariosat each stage t. This partition can be performed on the full set of scenarios of theoriginal process or on any random sample of such scenarios. An element of the partitionis associated with a sub-scenario up to t of the deterministic equivalent tree. We name thesub-scenario on the tree, the reference sub-scenario. The element of the partition includesall scenarios whose sub-scenarios up to t are closer to the reference sub-scenario than toany other sub-scenario on the tree. The extension scheme is pictured on Figure 2.j pp pp pp pp pp pp pu pppp pppp pppppppj pp pp pp pp pp pjp p p p p p p p p p puppp p p p p j p p p p p p p p p p p p p p p jpp pp pp pp pp pp pp pp ppppppu pp pp pppppppppj pp pp pp pp pp pjpppppppjppppppppppjj pp pp pp pp pp pp ppppppu pppp pppp pp pp pppppppppppppp pp pp pp p p p p jp p p p p p p p p p pjujp p p p p p p p p p p pjpp p p p u pppp pp pp pp pp pp pp pppp pp pp pp pp pp pp pjjjt 1t 2t 3ujujujujujujujujt 4Figure 2: Decision sets to implement the stochastic programming solutionThe decision rule consists in applying at any given element of the partition the samecontrol as the one that is prescribed at the reference scenario. Quite naturally

Step decision rules for multistage stochastic programming: a heuristic approach J. Th eni e J.-Ph.Vial September 27, 2006 Abstract Stochastic programming with step decision rules, SPSDR, is an attempt to over-come the curse of computational complexity of multistage stochastic programming problems. SPSDR combines several techniques.

Related Documents:

Bruksanvisning för bilstereo . Bruksanvisning for bilstereo . Instrukcja obsługi samochodowego odtwarzacza stereo . Operating Instructions for Car Stereo . 610-104 . SV . Bruksanvisning i original

grade step 1 step 11 step 2 step 12 step 3 step 13 step 4 step 14 step 5 step 15 step 6 step 16 step 7 step 17 step 8 step 18 step 9 step 19 step 10 step 20 /muimn 17,635 18,737 19,840 20,942 22,014 22,926 23,808 24,689 325,57! 26,453 /2qsohrs steps 11-20 8.48 9.0! 9.54 10.07 10.60 11.02 11.45 11.87 12.29 12.72-

Special Rates 562-600 Station Number 564 Duty Sta Occupation 0083-00 City: FAYETTEVILL State: AR Grade Suppl Rate Step 1 Step 2 Step 3 Step 4 Step 5 Step 6 Step 7 Step 8 Step 9 Step 10 Min OPM Tab Eff Date Duty Sta Occupation 0601-13 City: FAYETTEVILL State: AR Grade Suppl Rate Step 1 Step 2 Step 3 Step 4 Step 5 Step 6 Step 7 Step 8 Step 9 Step 10 Min OPM Tab Eff Date

Grade Minimum Step 1 Step 2 Step 3 Step 4 Step 5 Step 6 Step 7 Mid-Point Step 8 Step 9 Step 10 Step 11 Step 12 Step 13 Step 14 Maximum Step 15 12/31/2022 Accounting Services Coordinator O-19 45.20 55.15 65.10 Hourly 94,016 114,712 135,408 Appx Annual 12/31/2022 Accounting Services Manager O-20 47.45 57.90 68.34 Hourly

10 tips och tricks för att lyckas med ert sap-projekt 20 SAPSANYTT 2/2015 De flesta projektledare känner säkert till Cobb’s paradox. Martin Cobb verkade som CIO för sekretariatet för Treasury Board of Canada 1995 då han ställde frågan

service i Norge och Finland drivs inom ramen för ett enskilt företag (NRK. 1 och Yleisradio), fin ns det i Sverige tre: Ett för tv (Sveriges Television , SVT ), ett för radio (Sveriges Radio , SR ) och ett för utbildnings program (Sveriges Utbildningsradio, UR, vilket till följd av sin begränsade storlek inte återfinns bland de 25 största

Hotell För hotell anges de tre klasserna A/B, C och D. Det betyder att den "normala" standarden C är acceptabel men att motiven för en högre standard är starka. Ljudklass C motsvarar de tidigare normkraven för hotell, ljudklass A/B motsvarar kraven för moderna hotell med hög standard och ljudklass D kan användas vid

Master’s Thesis in Automotive Engineering JILING LI ZHEN ZHU Department of Applied Mechanics . The battery thermal management system (BTMS) plays a vital role in the control of the battery thermal behaviour. The BTMS technologies are: air cooling system, liquid cooling system, direct refrigerant cooling system, phase change material (PCM) cooling system, and thermo-electric cooling system .