×

Computational strategies for non-convex multistage MINLP models with decision-dependent uncertainty and gradual uncertainty resolution. (English) Zbl 1269.90073

Summary: In many planning problems under uncertainty the uncertainties are decision-dependent and resolve gradually depending on the decisions made. In this paper, we address a generic non-convex MINLP model for such planning problems where the uncertain parameters are assumed to follow discrete distributions and the decisions are made on a discrete time horizon. In order to account for the decision-dependent uncertainties and gradual uncertainty resolution, we propose a multistage stochastic programming model in which the non-anticipativity constraints in the model are not prespecified but change as a function of the decisions made. Furthermore, planning problems consist of several scenario subproblems where each subproblem is modeled as a nonconvex mixed-integer nonlinear program. We propose a solution strategy that combines global optimization and outer-approximation in order to optimize the planning decisions. We apply this generic problem structure and the proposed solution algorithm to several planning problems to illustrate the efficiency of the proposed method with respect to the method that uses only global optimization.

MSC:

90C15 Stochastic programming
91B06 Decision theory
90C26 Nonconvex programming, global optimization

Software:

BARON
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ahmed, S. (2000). Strategic planning under uncertainty: Stochastic integer programming approaches. Ph.d. thesis, University of Illinois at Urbana-Champaign.
[2] Beale, E. M. L. (1955). On minimizing a convex function subject to linear inequalities. Journal of Royal Statistical Society, Series B, 17, 173–184. · Zbl 0068.13701
[3] Boland, N., Dumitrescu, I., & Froyland, G. (2008). A multistage stochastic programming approach to open pit mine production scheduling with uncertain geology. Optimization Online, http://www.optimization-online.org/DB_HTML/2008/10/2123.html .
[4] Charnes, A., & Cooper, W. W. (1963). Deterministic equivalents for optimizing and satisficing under chance constraints. Operations Research, 11(1), 18–39. · Zbl 0117.15403 · doi:10.1287/opre.11.1.18
[5] Dantzig, G. B. (1955). Linear programming under uncertainty. Management Science, 1(3–4), 197–206. · Zbl 0995.90589 · doi:10.1287/mnsc.1.3-4.197
[6] Dias, M. (2002). Investment in information in petroleum, real options and revelation. In Proceedings of the 6th annual international conference on real options Cyprus: Real Options Group at Cyprus
[7] Dimitriadis, A. D., Shah, N., & Pantelides, C. C. (1997). RTN-based rolling horizon algorithms for medium term scheduling of multipurpose plants. Computers and Chemical Engineering, 21, 1061–1066.
[8] Duran, M. A., & Grossmann, I. E. (1986). An outer-approximation algorithm for a class of mixed-integer nonlinear programs. Mathematical Programming, 36(3), 307–339. · Zbl 0619.90052 · doi:10.1007/BF02592064
[9] Fisher, M. L. (1985). An applications oriented guide to Lagrangian relaxation. Interfaces, 15(2), 10–21. · doi:10.1287/inte.15.2.10
[10] Goel, V. (2005). Stochastic programming approaches for the optimal development of gas fields under uncertainty. Ph.d. thesis, Carnegie Mellon University.
[11] Goel, V., & Grossmann, I. E. (2004). A stochastic programming approach to planning of offshore gas field developments under uncertainty in reserves. Computers and Chemical Engineering, 28(8), 1409–1429. · doi:10.1016/j.compchemeng.2003.10.005
[12] Goel, V., & Grossmann, I. E. (2006). A class of stochastic programs with decision dependent uncertainty. Mathematical Programming, Ser. B, 108(2–3), 355–394. · Zbl 1130.90375 · doi:10.1007/s10107-006-0715-7
[13] Goel, V., Grossmann, I. E., El-Bakry, A. S., & Mulkay, E. L. (2006). A novel branch and bound algorithm for optimal development of gas fields under uncertainty in reserves. Computers and Chemical Engineering, 30, 1076–1092. · doi:10.1016/j.compchemeng.2006.02.006
[14] Harrison, K. W. (2007). Two-stage decision-making under uncertainty and stochasticity: Bayesian programming. Advances in Water Resources, 30(3), 641–664. · doi:10.1016/j.advwatres.2006.03.006
[15] Held, H., & Woodruff, D. L. (2005). Heuristics for multi-stage interdiction of stochastic networks. Journal of Heuristics, 11(5–6), 483–500. · Zbl 1122.90318 · doi:10.1007/s10732-005-3122-y
[16] Jonsbraten, T. W. (1998). Optimization models for petroleum field exploitation. Ph.d. thesis, Norwegian School of Economics and Business Administration.
[17] Jonsbraten, T. W., Wets, R. J., & Woodruff, D. L. (1998). A class of stochastic programs with decision dependent random elements. Annals of Operations Research, 82, 83–106. · Zbl 0911.90268 · doi:10.1023/A:1018943626786
[18] Kleywegt, A. J., Shapiro, A., & Homem-de Mello, T. (2002). The sample average approximation method for stochastic discrete optimization. SIAM Journal on Optimization, 12(2), 479–502. · Zbl 0991.90090 · doi:10.1137/S1052623499363220
[19] Pflug, G. C. (1990). Online optimization of simulated Markovian processes. Mathematics of Operations, 15(3), 381–395. · Zbl 0726.90088 · doi:10.1287/moor.15.3.381
[20] Ruszczyński, A. (1997). Decomposition methods in stochastic programming. Mathematical Programming, 79(1-3), 333–353. · Zbl 0887.90129
[21] Sahinidis, N. V. (2000). Baron: Branch-and-reduce optimization navigator. User’s manual. Version 4.0. http://archimedes.cheme.cmu.edu/baron/manuse.pdf .
[22] Sahinidis, N. V. (2004). Optimization under uncertainty: state-of-the-art and opportunities. Computers and Chemical Engineering, 28(6-7), 971–983. · doi:10.1016/j.compchemeng.2003.09.017
[23] Schultz, R. (2003). Stochastic programming with integer variables. Mathematical Programming, Ser. B, 97(1–2), 285–309. · Zbl 1035.90053
[24] Solak, S. (2007). Efficient solution procedures for multistage stochastic formulations of two problem classes. Ph.d. thesis, Georgia Institute of Technology.
[25] Stensland, G., & Tjøstheim, D. (1991). Optimal decisions with reduction of uncertainty over time–an application to oil production. In D. Lund & B. Øksendal (Eds.), Stochastic Models and Option Values (pp. 267–291). · Zbl 0825.90566
[26] Tarhan, B., & Grossmann, I. E. (2008). A multistage stochastic programming approach with strategies for uncertainty reduction in the synthesis of process networks with uncertain yields. Computers and Chemical Engineering, 32, 766–788. · doi:10.1016/j.compchemeng.2007.03.003
[27] Tarhan, B., Grossmann, I. E., & Goel, V. (2009). Stochastic programming approach for the planning of offshore oil or gas field infrastructure under decision-dependent uncertainty. Industrial and Engineering Chemistry Research, 48(6), 3078–3097. · doi:10.1021/ie8013549
[28] Viswanath, K., Peeta, S., & Salman, S. F. (2004). Investing in the links of a stochastic network to minimize expected shortest path. length. Purdue University economics working papers 1167, Purdue University, Department of Economics, West Lafayette, IN.
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.