Decision-dependent probabilities in stochastic programs with recourse

Computational Management Science - Tập 15 - Trang 369-395 - 2018
Lars Hellemo1, Paul I. Barton2, Asgeir Tomasgard3
1Department of Economics and Technology Management, SINTEF Technology and Society, Trondheim, Norway
2Process Systems Engineering Laboratory, Department of Chemical Engineering, Massachusetts Institute of Technology, Cambridge, USA
3Department of Industrial Economics and Technology Management, NTNU, Trondheim, Norway

Tóm tắt

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.

Tài liệu tham khảo

Abramowitz M, Stegun I (1964) Handbook of mathematical functions with formulas, graphs, and mathematical tables, vol 55. Dover Publications, New York

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

Apap RM, Grossmann IE (2017) Models and computational strategies for multistage stochastic programming under endogenous and exogenous uncertainties. Comput Chem Eng 103:233–274

Artstein Z, Wets R (1994) Stability results for stochastic programs and sensors, allowing for discontinuous objective functions. SIAM J Optim 4:537–550

Beale EML (1955) On minimizing a convex function subject to linear inequalities. J R Stat Soc B 17(2):173–184

Behboodian J (1970) On the modes of a mixture of two normal distributions. Technometrics 12(1):131–139

Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numer Math 4(1):238–252

Ben-Tal A, Nemirovski A (1998) Robust convex optimization. Math Oper Res 23(4):769–805

Ben-Tal A, Eiger G, Gershovitz V (1994) Global minimization by reducing the duality gap. Math Program 63(1):193–212

Bertsimas D, Sim M (2003) Robust discrete optimization and network flows. Math Program 98(1):49–71

Bertsimas D, Sim M (2004) The price of robustness. Oper Res 52(1):35–53

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

Colvin M, Maravelias CT (2008) A stochastic programming approach for clinical trial planning in new drug development. Comput Chem Eng 32(11):2626–42

Colvin M, Maravelias CT (2009a) Scheduling of testing tasks and resource planning in new product development using stochastic programming. Comput Chem Eng 33(5):964–976

Colvin M, Maravelias C (2009b) A branch and cut framework for multi-stage stochastic programming problems under endogenous uncertainty. Comput Aided Chem Eng 27:255–260

Colvin M, Maravelias CT (2010) 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(1):205–15

Dantzig GB (1955) Linear programming under uncertainty. Manag Sci 1:197–206

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

Epperly TG, Pistikopoulos EN (1997) A reduced space branch and bound algorithm for global optimization. J Global Optim 11(3):287–311

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

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

Feller W (1943) On a general class of “contagious” distributions. Ann Math Stat 14(4):389–400

Frühwirth-Schnatter S (2006) Finite mixture and Markov switching models. Springer, New York

Geoffrion A (1972) Generalized benders decomposition. J Optim Theory Appl 10(4):237–260

Goel V, Grossmann I (2004) A stochastic programming approach to planning of offshore gas field developments under uncertainty in reserves. Comput Chem Eng 28(8):1409–1429

Goel V, Grossmann I (2006) A class of stochastic programs with decision dependent uncertainty. Math Program 108(2):355–394

Gupta V, Grossmann IE (2011) Solution strategies for multistage stochastic programming with endogenous uncertainties. Comput Chem Eng 35(11):2235–2247

Held H, Woodruff D (2005) Heuristics for multi-stage interdiction of stochastic networks. J Heuristics 11(5):483–500

Jonsbråten T (1998) Oil field optimization under price uncertainty. J Oper Res Soc 49(8):811–818

Jonsbråten T, Wets R, Woodruff D (1998) A class of stochastic programs with decision dependent random elements. Ann Oper Res 82:83–106

Kuhn D (2009) An information-based approximation scheme for stochastic optimization problems in continuous time. Math Oper Res 34(2):428–444

Kuhn D, Wiesemann W, Georghiou A (2011) Primal and dual linear decision rules in stochastic and robust optimization. Math Program 130(1):177–209

Kumaraswamy P (1980) A generalized probability density function for double-bounded random processes. J Hydrol 46(1):79–88

Lappas N, Gounaris C (2016) Multi-stage adjustable robust optimization for process scheduling under uncertainty. AIChE Journal 62:1646–1667. https://doi.org/10.1002/aic.15183

Lappas N, Gounaris CE (2018) Robust optimization for decision-making under endogenous uncertainty. Comput Chem Eng. https://doi.org/10.1016/j.compchemeng.2018.01.006

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

Louveaux FV, Smeers Y (1988) Optimal investments for electricity generation: a stochastic model and a test problem. In: Ermoliev Y, Wets RJB (eds) Numerical techniques for stochastic optimization. Springer, Berlin, pp 445–454

Mitsos A, Chachuat B, Barton P (2009) McCormick-based relaxations of algorithms. SIAM J Optim 20(2009):573–601

Nohadani O, Sharma K (2016) Optimization under decision-dependent uncertainty. arXiv:1611.07992

Ntaimo L, Arrubla JAG, Stripling C, Young J, Spencer T (2012) A stochastic programming standard response model for wildfire initial attack planning. Can J For Res 42(6):987–1001

Peeta S, Salman FS, Gunnec D, Viswanath K (2010) Pre-disaster investment decisions for strengthening a highway network. Comput Oper Res 37(10):1708–1719

Pflug G (1996) Optimization of stochastic models: the interface between simulation and optimization. Kluwer Academic, Boston

Pflug GC, Pichler A (2011) Approximations for probability distributions and stochastic optimization problems. Stochastic optimization methods in finance and energy. Springer, New York, pp 343–387

Pflug G, Wozabal D (2007) Ambiguity in portfolio selection. Quant Finance 7(4):435–442

Rubinstein RY, Shapiro A (1993) Discrete event systems: sensitivity analysis and stochastic optimization by the score function method, vol 346. Wiley, New York

Solak S (2007) Efficient solution procedures for multistage stochastic formulations of two problem classes. Ph.D. thesis, Georgia Institute of Technology, Atlanta

Solak S, Clarke JP, Johnson E, Barnes E (2010) Modeling methods and a branch and cut algorithm for pharmaceutical clinical trial planning using stochastic programming. Eur J Oper Res 207(1):420–433

Tarhan B, Grossmann I, Goel V (2009) Stochastic programming approach for the planning of offshore oil or gas field infrastructure under decision-dependent uncertainty. Ind Eng Chem Res 48(6):3078–3097

Tawarmalani M, Sahinidis NV (2002) Convexification and global optimization in continuous and mixed-integer nonlinear programming. Kluwer Academic Publishers, Norwell

Varaiya P, Wets RJB (1989) Stochastic dynamic optimization, approaches and computation. In: Iri M, Tanabe K (eds) Mathematical programming, recent developments and applications. Kluwer Academic Publisher, Boston, pp 309–332

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

Thông tin
Thông tin xuất bản

Computational Management Science

Tập 15

369-395

Thông tin tác giả