Decision-dependent probabilities in stochastic programs with recourse. (English) Zbl 1483.90095
Summary: Stochastic programming with recourse usually assumes uncertainty to be exogenous. Our work presents modelling and application of decision-dependent uncertainty in mathematical programming including a taxonomy of stochastic programming recourse models with decision-dependent uncertainty. The work includes several ways of incorporating direct or indirect manipulation of underlying probability distributions through decision variables in two-stage stochastic programming problems. Two-stage models are formulated where prior probabilities are distorted through an affine transformation or combined using a convex combination of several probability distributions. Additionally, we present models where the parameters of the probability distribution are first-stage decision variables. The probability distributions are either incorporated in the model using the exact expression or by using a rational approximation. Test instances for each formulation are solved with a commercial solver, BARON, using selective branching.
MSC:
| 90C15 | Stochastic programming |
Software:
libMCReferences:
| [1] | Abramowitz M, Stegun I (1964) Handbook of mathematical functions with formulas, graphs, and mathematical tables, vol 55. Dover Publications, New York · Zbl 0171.38503 |
| [2] | Ahmed S (2000) Strategic planning under uncertainty—stochastic integer programming approaches. Ph.D. thesis, Graduate College, University of Illinois at Urbana-Champaign, Urbana, IL, USA |
| [3] | Apap, RM; Grossmann, IE, Models and computational strategies for multistage stochastic programming under endogenous and exogenous uncertainties, Comput Chem Eng, 103, 233-274, (2017) · doi:10.1016/j.compchemeng.2016.11.011 |
| [4] | Artstein, Z.; Wets, R., Stability results for stochastic programs and sensors, allowing for discontinuous objective functions, SIAM J Optim, 4, 537-550, (1994) · Zbl 0830.90111 · doi:10.1137/0804030 |
| [5] | Beale, EML, On minimizing a convex function subject to linear inequalities, J R Stat Soc B, 17, 173-184, (1955) · Zbl 0068.13701 |
| [6] | Behboodian, J., On the modes of a mixture of two normal distributions, Technometrics, 12, 131-139, (1970) · Zbl 0195.20304 · doi:10.1080/00401706.1970.10488640 |
| [7] | Benders, JF, Partitioning procedures for solving mixed-variables programming problems, Numer Math, 4, 238-252, (1962) · Zbl 0109.38302 · doi:10.1007/BF01386316 |
| [8] | Ben-Tal, A.; Nemirovski, A., Robust convex optimization, Math Oper Res, 23, 769-805, (1998) · Zbl 0977.90052 · doi:10.1287/moor.23.4.769 |
| [9] | Ben-Tal, A.; Eiger, G.; Gershovitz, V., Global minimization by reducing the duality gap, Math Program, 63, 193-212, (1994) · Zbl 0807.90101 · doi:10.1007/BF01582066 |
| [10] | Bertsimas, D.; Sim, M., Robust discrete optimization and network flows, Math Program, 98, 49-71, (2003) · Zbl 1082.90067 · doi:10.1007/s10107-003-0396-4 |
| [11] | Bertsimas, D.; Sim, M., The price of robustness, Oper Res, 52, 35-53, (2004) · Zbl 1165.90565 · doi:10.1287/opre.1030.0065 |
| [12] | Boland N, Dumitrescu I, Froyland G (2008) A multistage stochastic programming approach to open pit mine production scheduling with uncertain geology. In: 7th joint Australia-New Zealand Mathematics Convention (ANZMC2008), Christchurch, New Zealand |
| [13] | Colvin, M.; Maravelias, CT, A stochastic programming approach for clinical trial planning in new drug development, Comput Chem Eng, 32, 2626-42, (2008) · doi:10.1016/j.compchemeng.2007.11.010 |
| [14] | Colvin, M.; Maravelias, CT, Scheduling of testing tasks and resource planning in new product development using stochastic programming, Comput Chem Eng, 33, 964-976, (2009) · doi:10.1016/j.compchemeng.2008.09.010 |
| [15] | Colvin, M.; Maravelias, C., A branch and cut framework for multi-stage stochastic programming problems under endogenous uncertainty, Comput Aided Chem Eng, 27, 255-260, (2009) · doi:10.1016/S1570-7946(09)70263-9 |
| [16] | Colvin, M.; Maravelias, CT, Modeling methods and a branch and cut algorithm for pharmaceutical clinical trial planning using stochastic programming modeling methods and a branch and cut algorithm for pharmaceutical clinical trial planning using stochastic programming, Eur J Oper Res, 203, 205-15, (2010) · Zbl 1176.90204 · doi:10.1016/j.ejor.2009.07.022 |
| [17] | Dantzig, GB, Linear programming under uncertainty, Manag Sci, 1, 197-206, (1955) · Zbl 0995.90589 · doi:10.1287/mnsc.1.3-4.197 |
| [18] | Dupačová J (2006) Optimization under exogenous and endogenous uncertainty. In: Lukáš L (ed) Proceedings of MME06, University of West Bohemia in Pilsen, pp 131-136 |
| [19] | Epperly, TG; Pistikopoulos, EN, A reduced space branch and bound algorithm for global optimization, J Global Optim, 11, 287-311, (1997) · Zbl 1040.90567 · doi:10.1023/A:1008212418949 |
| [20] | Escudero LF, Garín MA, Merino M, Pérez G (2014) On multistage mixed 0-1 optimization under a mixture of Exogenous and Endogenous Uncertainty in a risk averse environment. Working paper |
| [21] | Escudero L, Garin A, Monge J, Unzueta A (2016) On preparedness resource allocation planning for natural disaster relief by multistage stochastic mixed 0-1 bilinear optimization based on endogenous uncertainty and time consistent risk averse management. Working paper · Zbl 1391.90371 |
| [22] | Feller, W., On a general class of “contagious” distributions, Ann Math Stat, 14, 389-400, (1943) · Zbl 0063.01341 · doi:10.1214/aoms/1177731359 |
| [23] | Frühwirth-Schnatter S (2006) Finite mixture and Markov switching models. Springer, New York · Zbl 1108.62002 |
| [24] | Geoffrion, A., Generalized benders decomposition, J Optim Theory Appl, 10, 237-260, (1972) · Zbl 0229.90024 · doi:10.1007/BF00934810 |
| [25] | Goel, V.; Grossmann, I., A stochastic programming approach to planning of offshore gas field developments under uncertainty in reserves, Comput Chem Eng, 28, 1409-1429, (2004) · doi:10.1016/j.compchemeng.2003.10.005 |
| [26] | Goel, V.; Grossmann, I., A class of stochastic programs with decision dependent uncertainty, Math Program, 108, 355-394, (2006) · Zbl 1130.90375 · doi:10.1007/s10107-006-0715-7 |
| [27] | Gupta, V.; Grossmann, IE, Solution strategies for multistage stochastic programming with endogenous uncertainties, Comput Chem Eng, 35, 2235-2247, (2011) · doi:10.1016/j.compchemeng.2010.11.013 |
| [28] | Held, H.; Woodruff, D., Heuristics for multi-stage interdiction of stochastic networks, J Heuristics, 11, 483-500, (2005) · Zbl 1122.90318 · doi:10.1007/s10732-005-3122-y |
| [29] | Jonsbråten, T., Oil field optimization under price uncertainty, J Oper Res Soc, 49, 811-818, (1998) · Zbl 1140.90429 · doi:10.1057/palgrave.jors.2600562 |
| [30] | Jonsbråten, T.; Wets, R.; Woodruff, D., A class of stochastic programs with decision dependent random elements, Ann Oper Res, 82, 83-106, (1998) · Zbl 0911.90268 · doi:10.1023/A:1018943626786 |
| [31] | Kuhn, D., An information-based approximation scheme for stochastic optimization problems in continuous time, Math Oper Res, 34, 428-444, (2009) · Zbl 1218.90144 · doi:10.1287/moor.1080.0369 |
| [32] | Kuhn, D.; Wiesemann, W.; Georghiou, A., Primal and dual linear decision rules in stochastic and robust optimization, Math Program, 130, 177-209, (2011) · Zbl 1236.90087 · doi:10.1007/s10107-009-0331-4 |
| [33] | Kumaraswamy, P., A generalized probability density function for double-bounded random processes, J Hydrol, 46, 79-88, (1980) · doi:10.1016/0022-1694(80)90036-0 |
| [34] | Lappas, N.; Gounaris, C., Multi-stage adjustable robust optimization for process scheduling under uncertainty, AIChE Journal, 62, 1646-1667, (2016) · doi:10.1002/aic.15183 |
| [35] | Lappas, N.; Gounaris, CE, Robust optimization for decision-making under endogenous uncertainty, Comput Chem Eng, (2018) · doi:10.1016/j.compchemeng.2018.01.006 |
| [36] | Lejeune M, Margot F (2017) Aeromedical battle field evacuation under endogenous uncertainty in casualty delivery times. Manag Sci. https://doi.org/10.1287/mnsc.2017.2894 |
| [37] | Louveaux, FV; Smeers, Y.; Ermoliev, Y. (ed.); Wets, RJB (ed.), Optimal investments for electricity generation: a stochastic model and a test problem, 445-454, (1988), Berlin · Zbl 0659.90061 · doi:10.1007/978-3-642-61370-8_24 |
| [38] | Mitsos, A.; Chachuat, B.; Barton, P., McCormick-based relaxations of algorithms, SIAM J Optim, 20, 573-601, (2009) · Zbl 1192.65083 · doi:10.1137/080717341 |
| [39] | Nohadani O, Sharma K (2016) Optimization under decision-dependent uncertainty. arXiv:1611.07992 · Zbl 1401.90117 |
| [40] | Ntaimo, L.; Arrubla, JAG; Stripling, C.; Young, J.; Spencer, T., A stochastic programming standard response model for wildfire initial attack planning, Can J For Res, 42, 987-1001, (2012) · doi:10.1139/x2012-032 |
| [41] | Peeta, S.; Salman, FS; Gunnec, D.; Viswanath, K., Pre-disaster investment decisions for strengthening a highway network, Comput Oper Res, 37, 1708-1719, (2010) · Zbl 1188.90052 · doi:10.1016/j.cor.2009.12.006 |
| [42] | Pflug G (1996) Optimization of stochastic models: the interface between simulation and optimization. Kluwer Academic, Boston · Zbl 0909.90220 · doi:10.1007/978-1-4613-1449-3 |
| [43] | Pflug, GC; Pichler, A., Approximations for probability distributions and stochastic optimization problems, 343-387, (2011), New York · Zbl 1405.90093 · doi:10.1007/978-1-4419-9586-5_15 |
| [44] | Pflug, G.; Wozabal, D., Ambiguity in portfolio selection, Quant Finance, 7, 435-442, (2007) · Zbl 1190.91138 · doi:10.1080/14697680701455410 |
| [45] | Rubinstein RY, Shapiro A (1993) Discrete event systems: sensitivity analysis and stochastic optimization by the score function method, vol 346. Wiley, New York · Zbl 0805.93002 |
| [46] | Solak S (2007) Efficient solution procedures for multistage stochastic formulations of two problem classes. Ph.D. thesis, Georgia Institute of Technology, Atlanta |
| [47] | Solak, S.; Clarke, JP; Johnson, E.; Barnes, E., Modeling methods and a branch and cut algorithm for pharmaceutical clinical trial planning using stochastic programming, Eur J Oper Res, 207, 420-433, (2010) · Zbl 1205.91099 · doi:10.1016/j.ejor.2010.04.032 |
| [48] | Tarhan, B.; Grossmann, I.; Goel, V., Stochastic programming approach for the planning of offshore oil or gas field infrastructure under decision-dependent uncertainty, Ind Eng Chem Res, 48, 3078-3097, (2009) · doi:10.1021/ie8013549 |
| [49] | Tawarmalani M, Sahinidis NV (2002) Convexification and global optimization in continuous and mixed-integer nonlinear programming. Kluwer Academic Publishers, Norwell · Zbl 1031.90022 · doi:10.1007/978-1-4757-3532-1 |
| [50] | Varaiya, P.; Wets, RJB; Iri, M. (ed.); Tanabe, K. (ed.), Stochastic dynamic optimization, approaches and computation, 309-332, (1989), Boston · Zbl 0813.90086 |
| [51] | Viswanath K, Peeta S, Salman SF (2004) Investing in the links of a stochastic network to minimize expected shortest path length. Tech. rep., Purdue University, Department of Economics, West Lafayette |
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.
