Augmented simulation methods for discrete stochastic optimization with recourse
- PDF / 697,271 Bytes
- 23 Pages / 439.37 x 666.142 pts Page_size
- 97 Downloads / 221 Views
Augmented simulation methods for discrete stochastic optimization with recourse Tahir Ekin1
· Stephen Walker2 · Paul Damien2
Accepted: 15 October 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We develop an augmented simulation approach to solve discrete stochastic optimization problems by converting them into a grand simulation problem in the joint space of random and decision variables. The optimal decision is obtained via the mode of the augmented probability model, using a new multivariate extension of the classic Barker’s algorithm. Illustrations on different versions of univariate and multivariate discrete news-vendor problems with exogenous and endogenous uncertainties are detailed. We contrast our method with the Metropolis–Hastings algorithm, the nested sampling-based augmented simulation method, and traditional Monte Carlo simulation-based optimization schemes. The proposed method is shown to be computationally efficient and could serve as another tool to solve discrete stochastic optimization problems with recourse. Keywords Discrete stochastic optimization · Simulation-based optimization · Augmented probability simulation · Barker algorithm · Stochastic programs with recourse
1 Introduction Decision models under uncertainty are confronted with a variety of challenges; see Birge and Louveaux (2011) and Powell (2016). To tackle some of these challenges, recent computational advances have increased the popularity of simulation–based approaches, especially in cases where the objective function is either analytically unavailable or expensive to compute. Among these advances, traditional Monte Carlo sampling methods are widely utilized; see Homem-de Mello and Bayraksan (2014) for an overview. However, it is well-known that they may not be suitable for problems where functions of the random variable corresponding to the observed data are difficult to estimate; these may be due to the number of decision possibilities, the dimensionality of the random variable, or the shape of the data density. Subsequently, the estimation error due to Monte Carlo simulation could impact the quality
B
Tahir Ekin [email protected]
1
McCoy College of Business, Texas State University, 601 University Drive, San Marcos, TX 78666, USA
2
University of Texas in Austin, Austin, TX, USA
123
Annals of Operations Research
of the optimal decision and can be particularly acute when the random variable’s density is skewed and/or multi-modal. For the purposes of this paper, and discrete stochastic optimization in general, it may be useful to consider two broad types of stochastic uncertainty—exogenous (aka non-decisiondependent) versus endogenous (aka decision-dependent) uncertainty. Sampling-based optimization algorithms for the former are, for example, discussed in Infanger (1993) and Higle and Sen (1996). The latter type of uncertainty is computationally more demanding since any optimization should consider all decision dependent possibilities; see, Goel and Grossmann (2006). Stated diffe
Data Loading...
