×

On stochastic dynamic programming for solving large-scale planning problems under uncertainty. (English) Zbl 1179.90243

Summary: The stochastic dynamic programming approach outlined here, makes use of the scenario tree in a back-to-front scheme. The multi-period stochastic problems, related to the subtrees whose root nodes are the starting nodes (i.e., scenario groups), are solved at each given stage along the time horizon. Each subproblem considers the effect of the stochasticity of the uncertain parameters from the periods of the given stage, by using curves that estimate the expected future value (EFV) of the objective function. Each subproblem is solved for a set of reference levels of the variables that also have nonzero elements in any of the previous stages besides the given stage. An appropriate sensitivity analysis of the objective function for each reference level of the linking variables allows us to estimate the EFV curves applicable to the scenario groups from the previous stages, until the curves for the first stage have been computed. An application of the scheme to the problem of production planning with logical constraints is presented. The aim of the problem consists of obtaining the planning of tactical production over the scenarios along the time horizon. The expected total cost is minimized to satisfy the product demand. Some computational experience is reported. The proposed approach compares favorably with a state-of-the-art optimization engine in instances on a very large scale.
Scope and purpose
For quite some time, we have known that traditional methods of deterministic optimization are not suitable to capture the truly dynamic nature of most real-life problems, in view of the fact that the parameters which represent information concerning the future are uncertain. Many of the problems in planning under uncertainty, have logical constraints that require \(0-1\) variables in their formulation and can be solved via stochastic integer programming using scenario tree analysis. Given the dimensions of the deterministic equivalent model (DEM) of the stochastic problem, certain decomposition approaches can be considered by exploiting the structure of the models. Traditional decomposition schemes, such as the Benders and Lagrangean approaches, do not appear to provide the solution for large-scale problems (mainly in the cardinality of the scenario tree) in affordable computing effort. In this work, a stochastic dynamic programming approach is suggested, which we feel is particularly suited to exploit the scenario tree structure and, therefore, very amenable to finding solutions to very large-scale DEMs. The pilot case used involves a classical tactical production planning problem, where the structure is not exploited by the proposed approach so that it is generally applicable.

MSC:

90C15 Stochastic programming
90C39 Dynamic programming
90B35 Deterministic scheduling theory in operations research
90B30 Production models
90C09 Boolean programming

Software:

CORO
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Escudero, L. F.; Galindo, E.; Gómez, E.; García, G.; Sabau, V., Schumann, a modelling framework for supply chain management under uncertainty, European Journal of Operational Research, 119, 13-34 (1999) · Zbl 0933.90021
[2] Alonso-Ayuso, A.; Escudero, L. F.; Ortuño, M. T., Modeling production planning and scheduling under uncertainty, (Wallace, S. W.; Ziemba, W. T., Applications of stochastic programming. MPS-SIAM-series in optimization (2005), SIAM: SIAM Philadelphia, PA), 217-252 · Zbl 1105.90315
[3] Escudero, L. F.; Quintana, F. J.; Salmerón, J., Coro, a modelling and an algorithmic framework for oil supply, transformation and distribution optimization under uncertainty, European Journal of Operational Research, 114, 638-656 (1999) · Zbl 0938.90019
[4] Jarrow RA, Maksimovic V, Ziemba WT, editors. Finance, Amsterdam: North-Holland; 1995.; Jarrow RA, Maksimovic V, Ziemba WT, editors. Finance, Amsterdam: North-Holland; 1995. · Zbl 0884.90033
[5] Uryasev S, Pardalos PM, editors. Stochastic optimization: algorithms and applications. Dordrecht: Kluwer Academic Publishers; 2001.; Uryasev S, Pardalos PM, editors. Stochastic optimization: algorithms and applications. Dordrecht: Kluwer Academic Publishers; 2001.
[6] Wallace SW, Ziemba WT, editors. Applications of stochastic programming. MPS-SIAM-series in optimization. Philadelphia, PA: SIAM; 2005.; Wallace SW, Ziemba WT, editors. Applications of stochastic programming. MPS-SIAM-series in optimization. Philadelphia, PA: SIAM; 2005.
[7] Ziemba WT. Mulvey JM, editors. Worldwide asset and liability modeling. Cambridge: Cambridge University Press; 1998.; Ziemba WT. Mulvey JM, editors. Worldwide asset and liability modeling. Cambridge: Cambridge University Press; 1998.
[8] Birge J, Louveaux FV. Introduction to stochastic programming. Berlin: Springer; 1997.; Birge J, Louveaux FV. Introduction to stochastic programming. Berlin: Springer; 1997. · Zbl 0892.90142
[9] Higle, J. L.; Sen, S., Stochastic decomposition (1996), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht
[10] Kall, P.; Wallace, S. W., Stochastic programming (1994), Wiley: Wiley New York · Zbl 0812.90122
[11] Butcher, W. S., Stochastic dynamic programming for optimum reservoir operation, Water Resources Bulletin, 7, 115-123 (1971)
[12] Cervera, C.; Wen, A.; Chen, W. C.P., Optimization of a large scale water reservoir network by stochastic dynamic programming with efficient state space discretization, European Journal of Operational Research, 171, 1139-1151 (2006) · Zbl 1116.90123
[13] Cervera, C.; Wen, A.; Chen, W. C.P., Neural network and regression spline value function approximations for stochastic dynamic programming, Computers & Operations Research, 34, 70-90 (2007) · Zbl 1102.90040
[14] Escudero LF, Martinez J. Stochastic programming for estimating the water future expected value in hydrothermal electric systems. In: International symposium on mathematical programming, Atlanta, GA, USA, 2000.; Escudero LF, Martinez J. Stochastic programming for estimating the water future expected value in hydrothermal electric systems. In: International symposium on mathematical programming, Atlanta, GA, USA, 2000.
[15] Labadie, J. W., Optimal operation of multireservoir systems: state-of-the art review, Journal of Water Resources Planning and Management, 130, 93-111 (2004)
[16] Pereira, M. V.F.; Pinto, L. M.V. G., Stochastic optimization of a multireservoir hydroelectric system, a decomposition approach, Water Resources Research, 21, 779-792 (1985)
[17] Pereira, M. V.F.; Pinto, L. M.V. G., Multistage stochastic optimization applied to energy planning, Mathematical Programming, 52, 359-375 (1991) · Zbl 0749.90057
[18] Rockafellar, R. T.; Wets, R. J.-B., Scenario and policy aggregation in optimization under uncertainty, Mathematics of Operations Research, 16, 119-147 (1991) · Zbl 0729.90067
[19] Wagner, H. M.; Within, T. M., A dynamic version of the economic lot size model, Management Science, 5, 89-96 (1958) · Zbl 0977.90500
[20] Belvaux, G.; Wolsey, L. A., Modelling practical lot sizing problems as mixed-integer programs, Management Science, 47, 993-1007 (2001) · Zbl 1232.90169
[21] Dillenberger, Ch.; Escudero, L. F.; Wollensak, A.; Zhang, W., On practical resource allocation for production planning and scheduling with period overlapping setups, European Journal of Operational Research, 75, 275-286 (2004) · Zbl 0806.90055
[22] Krarup J, Bilde O. Plant location, set covering and economic lot size: an \(O(\mathit{mn})\); Krarup J, Bilde O. Plant location, set covering and economic lot size: an \(O(\mathit{mn})\) · Zbl 0364.90067
[23] Miller, A. J.; Nemhauser, G. L.; Savelsbergh, M. W.P., On capacitated lot-sizing and continuous 0-1 knapsack polyhedra, European Journal of Operational Research, 125, 298-315 (2000) · Zbl 0952.90028
[24] Pocket, Y.; Wolsey, L. A., Solving multi-item lot sizing problems using strong cutting planes, Management Science, 37, 53-67 (1991) · Zbl 0727.90034
[25] Shapiro JF. Mathematical programming models and methods for production planning and scheduling. In: Graves SC, Rinnooy Kan AHG, Zipkin PH, editors. Logistics of production and inventory. Amsterdam: North-Holland; 1993.; Shapiro JF. Mathematical programming models and methods for production planning and scheduling. In: Graves SC, Rinnooy Kan AHG, Zipkin PH, editors. Logistics of production and inventory. Amsterdam: North-Holland; 1993.
[26] Sousa, J.; Wolsey, L. A., A time indexed formulation of non-preemptive single machine scheduling problems, Mathematical Programming, 54, 353-357 (1992) · Zbl 0768.90041
[27] Wolsey, L. A., MIP modeling of changeovers in production planning and scheduling problems, European Journal of Operational Research, 99, 154-165 (1997) · Zbl 0923.90088
[28] Zipkin, P. H., Models for design and control of stochastic multi-item batch production systems, Operations Research, 34, 91-104 (1986) · Zbl 0594.90041
[29] Ahmed, S.; King, K. J.; Parija, G., A multi-stage stochastic integer programming approach for capacity expansion under uncertainty, Journal of Global Optimization, 26, 3-24 (2003) · Zbl 1116.90382
[30] Alonso-Ayuso, A.; Escudero, L. F.; Ortuño, M. T., On planning under uncertainty in manufacturing, Statistics and Operations Research Transactions, 31, 109-150 (2007) · Zbl 1175.90131
[31] Nemhauser, G.; Wolsey, L. A., Integer and combinatorial optimization (1988), Wiley: Wiley New York · Zbl 0652.90067
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.