Step decision rules for multistage stochastic programming: A heuristic approach

✍ Scribed by J. Thénié; J.-Ph. Vial

• Publisher: Elsevier Science
• Year: 2008
• Tongue: English
• Weight: 947 KB
• Volume: 44
• Category: Article
• ISSN: 0005-1098
• DOI: 10.1016/j.automatica.2008.02.001

✦ Synopsis

Stochastic programming with step decision rules (SPSDR) aims to produce efficient solutions to multistage stochastic optimization problems. SPSDR, like plain multistage Stochastic Programming (SP), operates on a Monte Carlo "computing sample" of moderate size that approximates the stochastic process. Unlike SP, SPSDR does not strive to build a balanced event tree out of that sample. Rather, it defines a solution as a special type of decision rule, with the property that the decisions at each stage are piecewise constant functions on the sample of scenarios. Those pieces define a partition of the set of scenarios at each stage t, but the partition at t + 1 need not be refinement of the partition at t. However, the rule is constructed so that the non-anticipativity condition is met, a necessary condition to make the rules operational. To validate the method we show how to extend a non-anticipatory decision rule to arbitrary scenarios within a very large validation sample of scenarios. We apply three methods, SPSDR, SP and Robust Optimization, to the same 12-stage problem in supply chain management, and compare them relatively to different objectives and performance criteria. It appears that SPSDR performs better than SP in that it produces a more accurate estimate (prediction) of the value achieved by its solution on the validation sample, and also that the achieved value is better.