IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v320y2023i2d10.1007_s10479-020-03836-w.html
   My bibliography  Save this article

Augmented simulation methods for discrete stochastic optimization with recourse

Author

Listed:
  • Tahir Ekin

    (Texas State University)

  • Stephen Walker

    (University of Texas in Austin)

  • Paul Damien

    (University of Texas in Austin)

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.

Suggested Citation

  • Tahir Ekin & Stephen Walker & Paul Damien, 2023. "Augmented simulation methods for discrete stochastic optimization with recourse," Annals of Operations Research, Springer, vol. 320(2), pages 771-793, January.
    • Handle: RePEc:spr:annopr:v:320:y:2023:i:2:d:10.1007_s10479-020-03836-w
    DOI: 10.1007/s10479-020-03836-w
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-020-03836-w
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10479-020-03836-w?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Mahmoud H. Alrefaei & Sigrún Andradóttir, 1999. "A Simulated Annealing Algorithm with Constant Temperature for Discrete Stochastic Optimization," Management Science, INFORMS, vol. 45(5), pages 748-764, May.
    2. Tahir Ekin & Nicholas G. Polson & Refik Soyer, 2014. "Augmented Markov Chain Monte Carlo Simulation for Two-Stage Stochastic Programs with Recourse," Decision Analysis, INFORMS, vol. 11(4), pages 250-264, December.
    3. L. Jeff Hong & Barry L. Nelson, 2006. "Discrete Optimization via Simulation Using COMPASS," Operations Research, INFORMS, vol. 54(1), pages 115-129, February.
    4. Karlis, Dimitris & Ntzoufras, Ioannis, 2005. "Bivariate Poisson and Diagonal Inflated Bivariate Poisson Regression Models in R," Journal of Statistical Software, Foundation for Open Access Statistics, vol. 14(i10).
    5. Leyuan Shi & Sigurdur Ólafsson, 2000. "Nested Partitions Method for Global Optimization," Operations Research, INFORMS, vol. 48(3), pages 390-407, June.
    6. Ernst, Ricardo & Powell, Stephen G., 1995. "Optimal inventory policies under service-sensitive demand," European Journal of Operational Research, Elsevier, vol. 87(2), pages 316-327, December.
    7. Tahir Ekin & Nicholas G. Polson & Refik Soyer, 2017. "Augmented nested sampling for stochastic programs with recourse and endogenous uncertainty," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(8), pages 613-627, December.
    8. Urban, Timothy L., 2005. "Inventory models with inventory-level-dependent demand: A comprehensive review and unifying theory," European Journal of Operational Research, Elsevier, vol. 162(3), pages 792-804, May.
    9. Martin Pincus, 1970. "Letter to the Editor—A Monte Carlo Method for the Approximate Solution of Certain Types of Constrained Optimization Problems," Operations Research, INFORMS, vol. 18(6), pages 1225-1228, December.
    10. Jacquier, Eric & Johannes, Michael & Polson, Nicholas, 2007. "MCMC maximum likelihood for latent state models," Journal of Econometrics, Elsevier, vol. 137(2), pages 615-640, April.
    11. Concha Bielza & Peter Müller & David Ríos Insua, 1999. "Decision Analysis by Augmented Probability Simulation," Management Science, INFORMS, vol. 45(7), pages 995-1007, July.
    12. Warren B. Powell, 2016. "Perspectives of approximate dynamic programming," Annals of Operations Research, Springer, vol. 241(1), pages 319-356, June.
    13. Nicholas C. Petruzzi & Maqbool Dada, 1999. "Pricing and the Newsvendor Problem: A Review with Extensions," Operations Research, INFORMS, vol. 47(2), pages 183-194, April.
    14. Satyajith Amaran & Nikolaos V. Sahinidis & Bikram Sharda & Scott J. Bury, 2016. "Simulation optimization: a review of algorithms and applications," Annals of Operations Research, Springer, vol. 240(1), pages 351-380, May.
    15. Panos Parpas & Berk Ustun & Mort Webster & Quang Kha Tran, 2015. "Importance Sampling in Stochastic Programming: A Markov Chain Monte Carlo Approach," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 358-377, May.
    16. Shing Chih Tsai & Tse Yang, 2017. "Rapid screening algorithms for stochastically constrained problems," Annals of Operations Research, Springer, vol. 254(1), pages 425-447, July.
    17. Tevfik Aktekin & Tahir Ekin, 2016. "Stochastic call center staffing with uncertain arrival, service and abandonment rates: A Bayesian perspective," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(6), pages 460-478, September.
    18. Martin Pincus, 1968. "Letter to the Editor—-A Closed Form Solution of Certain Programming Problems," Operations Research, INFORMS, vol. 16(3), pages 690-694, June.
    19. Mahmoud H. Alrefaei & Sigrún Andradóttir, 2005. "Discrete stochastic optimization using variants of the stochastic ruler method," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(4), pages 344-360, June.
    20. Solak, Senay & Clarke, John-Paul B. & Johnson, Ellis L. & Barnes, Earl R., 2010. "Optimization of R&D project portfolios under endogenous uncertainty," European Journal of Operational Research, Elsevier, vol. 207(1), pages 420-433, November.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Tahir Ekin & Nicholas G. Polson & Refik Soyer, 2017. "Augmented nested sampling for stochastic programs with recourse and endogenous uncertainty," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(8), pages 613-627, December.
    2. Ekin, Tahir, 2018. "Integrated maintenance and production planning with endogenous uncertain yield," Reliability Engineering and System Safety, Elsevier, vol. 179(C), pages 52-61.
    3. Ekin, Tahir & Naveiro, Roi & Ríos Insua, David & Torres-Barrán, Alberto, 2023. "Augmented probability simulation methods for sequential games," European Journal of Operational Research, Elsevier, vol. 306(1), pages 418-430.
    4. Tevfik Aktekin & Tahir Ekin, 2016. "Stochastic call center staffing with uncertain arrival, service and abandonment rates: A Bayesian perspective," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(6), pages 460-478, September.
    5. Ekin, Tahir & Aktekin, Tevfik, 2021. "Decision making under uncertain and dependent system rates in service systems," European Journal of Operational Research, Elsevier, vol. 291(1), pages 335-348.
    6. Tahir Ekin & Nicholas G. Polson & Refik Soyer, 2014. "Augmented Markov Chain Monte Carlo Simulation for Two-Stage Stochastic Programs with Recourse," Decision Analysis, INFORMS, vol. 11(4), pages 250-264, December.
    7. Huidong Zhang & Dragan Djurdjanovic, 2022. "Integrated production and maintenance planning under uncertain demand with concurrent learning of yield rate," Flexible Services and Manufacturing Journal, Springer, vol. 34(2), pages 429-450, June.
    8. Andrei A. Prudius & Sigrún Andradóttir, 2012. "Averaging frameworks for simulation optimization with applications to simulated annealing," Naval Research Logistics (NRL), John Wiley & Sons, vol. 59(6), pages 411-429, September.
    9. Alfredo Garcia & Stephen D. Patek & Kaushik Sinha, 2007. "A Decentralized Approach to Discrete Optimization via Simulation: Application to Network Flow," Operations Research, INFORMS, vol. 55(4), pages 717-732, August.
    10. Deniz Preil & Michael Krapp, 2023. "Genetic multi-armed bandits: a reinforcement learning approach for discrete optimization via simulation," Papers 2302.07695, arXiv.org.
    11. Qi Zhang & Jiaqiao Hu, 2019. "Simulation Optimization Using Multi-Time-Scale Adaptive Random Search," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 36(06), pages 1-34, December.
    12. Lihua Sun & L. Jeff Hong & Zhaolin Hu, 2014. "Balancing Exploitation and Exploration in Discrete Optimization via Simulation Through a Gaussian Process-Based Search," Operations Research, INFORMS, vol. 62(6), pages 1416-1438, December.
    13. Salo, Ahti & Andelmin, Juho & Oliveira, Fabricio, 2022. "Decision programming for mixed-integer multi-stage optimization under uncertainty," European Journal of Operational Research, Elsevier, vol. 299(2), pages 550-565.
    14. Vishal Gaur & Young-Hoon Park, 2007. "Asymmetric Consumer Learning and Inventory Competition," Management Science, INFORMS, vol. 53(2), pages 227-240, February.
    15. Shamsuddin Ahmed, 2013. "Performance of derivative free search ANN training algorithm with time series and classification problems," Computational Statistics, Springer, vol. 28(5), pages 1881-1914, October.
    16. Wang, Honggang, 2012. "Retrospective optimization of mixed-integer stochastic systems using dynamic simplex linear interpolation," European Journal of Operational Research, Elsevier, vol. 217(1), pages 141-148.
    17. Sigrún Andradóttir & Andrei A. Prudius, 2009. "Balanced Explorative and Exploitative Search with Estimation for Simulation Optimization," INFORMS Journal on Computing, INFORMS, vol. 21(2), pages 193-208, May.
    18. Xiaoning Luo & Yanmin Jiang & Qiying Hu, 2010. "Supply chain coordination with shelf‐space and retail price dependent demand and heterogeneous retailers," Naval Research Logistics (NRL), John Wiley & Sons, vol. 57(8), pages 673-685, December.
    19. Jia, Shuai & Li, Chung-Lun & Xu, Zhou, 2020. "A simulation optimization method for deep-sea vessel berth planning and feeder arrival scheduling at a container port," Transportation Research Part B: Methodological, Elsevier, vol. 142(C), pages 174-196.
    20. Youhua (Frank) Chen & Ye Lu & Minghui Xu, 2012. "Optimal inventory control policy for periodic‐review inventory systems with inventory‐level‐dependent demand," Naval Research Logistics (NRL), John Wiley & Sons, vol. 59(6), pages 430-440, September.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:annopr:v:320:y:2023:i:2:d:10.1007_s10479-020-03836-w. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.