lynx   »   [go: up one dir, main page]
IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v321y2025i1p147-159.html
   My bibliography  Save this article

Probabilistic branch and bound considering stochastic constraints

Author

Listed:
  • Huang, Hao
  • Tsai, Shing Chih
  • Park, Chuljin
Abstract
In this paper, we investigate a simulation optimization problem that poses challenges due to (i) the inability to evaluate the objective and multiple constraint functions analytically; instead, we rely on stochastic simulation to estimate them, and (ii) a discrete and potentially vast solution space. Rather than providing a single optimal solution, our aim is to identify a set of near-optimal solutions within a specific quantile, such as the top 10%. Our investigation covers two different problem settings or frameworks. The first framework is focused solely on a stochastic objective function, disregarding any stochastic constraints. In this context, we propose employing a probabilistic branch-and-bound algorithm to discover a level set of solutions. Alternatively, the second framework involves stochastic constraints. To address such stochastically constrained problems, we utilize a penalty function methodology in conjunction with a probabilistic branch-and-bound algorithm. Furthermore, we establish a convergence analysis of both algorithms to demonstrate their asymptotic validity and highlight their theoretical properties and behavior. Our experimental results provide evidence of the efficiency of our proposed algorithms, showing that they outperform existing approaches in the field of simulation optimization.

Suggested Citation

  • Huang, Hao & Tsai, Shing Chih & Park, Chuljin, 2025. "Probabilistic branch and bound considering stochastic constraints," European Journal of Operational Research, Elsevier, vol. 321(1), pages 147-159.
    • Handle: RePEc:eee:ejores:v:321:y:2025:i:1:p:147-159
    DOI: 10.1016/j.ejor.2024.09.016
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221724007197
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2024.09.016?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. Lee, Mi Lim & Park, Chuljin & Park, Dong Uk, 2018. "Self-adjusting the tolerance level in a fully sequential feasibility check procedure," European Journal of Operational Research, Elsevier, vol. 271(2), pages 733-745.
    2. Fleszar, Krzysztof, 2022. "A branch-and-bound algorithm for the quadratic multiple knapsack problem," European Journal of Operational Research, Elsevier, vol. 298(1), pages 89-98.
    3. Tsai, Shing Chih & Fu, Sheng Yang, 2014. "Genetic-algorithm-based simulation optimization considering a single stochastic constraint," European Journal of Operational Research, Elsevier, vol. 236(1), pages 113-125.
    4. Wendy Xu & Barry Nelson, 2013. "Empirical stochastic branch-and-bound for optimization via simulation," IISE Transactions, Taylor & Francis Journals, vol. 45(7), pages 685-698.
    5. Saif, Ahmed & Elhedhli, Samir, 2016. "Cold supply chain design with environmental considerations: A simulation-optimization approach," European Journal of Operational Research, Elsevier, vol. 251(1), pages 274-287.
    6. Leyuan Shi & Sigurdur Ólafsson, 2000. "Nested Partitions Method for Global Optimization," Operations Research, INFORMS, vol. 48(3), pages 390-407, June.
    7. Naoum-Sawaya, Joe & Ghaddar, Bissan & Arandia, Ernesto & Eck, Bradley, 2015. "Simulation-optimization approaches for water pump scheduling and pipe replacement problems," European Journal of Operational Research, Elsevier, vol. 246(1), pages 293-306.
    8. Tsai, Shing Chih & Yeh, Yingchieh & Kuo, Chen Yun, 2021. "Efficient optimization algorithms for surgical scheduling under uncertainty," European Journal of Operational Research, Elsevier, vol. 293(2), pages 579-593.
    9. Shing Chih Tsai & Jun Luo & Guangxin Jiang & Wei Cheng Yeh, 2023. "Adaptive fully sequential selection procedures with linear and nonlinear control variates," IISE Transactions, Taylor & Francis Journals, vol. 55(6), pages 561-573, June.
    10. Cheng, Zhenxia & Luo, Jun & Wu, Ruijing, 2023. "On the finite-sample statistical validity of adaptive fully sequential procedures," European Journal of Operational Research, Elsevier, vol. 307(1), pages 266-278.
    11. Yuwei Zhou & Sigrún Andradóttir & Seong-Hee Kim & Chuljin Park, 2022. "Finding Feasible Systems for Subjective Constraints Using Recycled Observations," INFORMS Journal on Computing, INFORMS, vol. 34(6), pages 3080-3095, November.
    12. Jack Chen, E., 2011. "A revisit of two-stage selection procedures," European Journal of Operational Research, Elsevier, vol. 210(2), pages 281-286, April.
    13. Zelda B. Zabinsky, 2015. "Stochastic Adaptive Search Methods: Theory and Implementation," International Series in Operations Research & Management Science, in: Michael C Fu (ed.), Handbook of Simulation Optimization, edition 127, chapter 0, pages 293-318, Springer.
    14. L. Jeff Hong & Jun Luo & Barry L. Nelson, 2015. "Chance Constrained Selection of the Best," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 317-334, May.
    15. Pedrielli, Giulia & Wang, Songhao & Ng, Szu Hui, 2020. "An extended Two-Stage Sequential Optimization approach: Properties and performance," European Journal of Operational Research, Elsevier, vol. 287(3), pages 929-945.
    16. Wang, Honggang, 2017. "Multi-objective retrospective optimization using stochastic zigzag search," European Journal of Operational Research, Elsevier, vol. 263(3), pages 946-960.
    17. 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.
    18. L. Jeff Hong & Barry L. Nelson & Jie Xu, 2015. "Discrete Optimization via Simulation," International Series in Operations Research & Management Science, in: Michael C Fu (ed.), Handbook of Simulation Optimization, edition 127, chapter 0, pages 9-44, Springer.
    19. Chun-Hung Chen & Enver Yücesan & Liyi Dai & Hsiao-Chang Chen, 2010. "Optimal budget allocation for discrete-event simulation experiments," IISE Transactions, Taylor & Francis Journals, vol. 42(1), pages 60-70.
    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. Jalali, Hamed & Van Nieuwenhuyse, Inneke & Picheny, Victor, 2017. "Comparison of Kriging-based algorithms for simulation optimization with heterogeneous noise," European Journal of Operational Research, Elsevier, vol. 261(1), pages 279-301.
    2. Yuwei Zhou & Sigrún Andradóttir & Seong-Hee Kim & Chuljin Park, 2022. "Finding Feasible Systems for Subjective Constraints Using Recycled Observations," INFORMS Journal on Computing, INFORMS, vol. 34(6), pages 3080-3095, November.
    3. Yifan Zhou & Chao Yuan & Tian Ran Lin & Lin Ma, 2021. "Maintenance policy structure investigation and optimisation of a complex production system with intermediate buffers," Journal of Risk and Reliability, , vol. 235(3), pages 458-473, June.
    4. Zhong, Ying & Du, Jianzhong & Li, Deng-Feng & Hu, Zhaolin, 2025. "Reference alternatives based knockout-tournament procedure for ranking and selection," European Journal of Operational Research, Elsevier, vol. 320(3), pages 628-641.
    5. Tsai, Shing Chih & Yeh, Yingchieh & Kuo, Chen Yun, 2021. "Efficient optimization algorithms for surgical scheduling under uncertainty," European Journal of Operational Research, Elsevier, vol. 293(2), pages 579-593.
    6. Wang, Xiuxian & Matta, Andrea & Geng, Na & Zhou, Liping & Jiang, Zhibin, 2025. "Simulation-based emergency department staffing and scheduling optimization considering part-time work shifts," European Journal of Operational Research, Elsevier, vol. 321(2), pages 631-643.
    7. Preil, Deniz & Krapp, Michael, 2022. "Bandit-based inventory optimisation: Reinforcement learning in multi-echelon supply chains," International Journal of Production Economics, Elsevier, vol. 252(C).
    8. Lee, Loo Hay & Chew, Ek Peng & Manikam, Puvaneswari, 2006. "A general framework on the simulation-based optimization under fixed computing budget," European Journal of Operational Research, Elsevier, vol. 174(3), pages 1828-1841, November.
    9. Flötteröd, Gunnar, 2017. "A search acceleration method for optimization problems with transport simulation constraints," Transportation Research Part B: Methodological, Elsevier, vol. 98(C), pages 239-260.
    10. Qi Fan & Jiaqiao Hu, 2018. "Surrogate-Based Promising Area Search for Lipschitz Continuous Simulation Optimization," INFORMS Journal on Computing, INFORMS, vol. 30(4), pages 677-693, November.
    11. Hamed Nozari & Esmaeil Najafi & Mohammad Fallah & Farhad Hosseinzadeh Lotfi, 2019. "Quantitative Analysis of Key Performance Indicators of Green Supply Chain in FMCG Industries Using Non-Linear Fuzzy Method," Mathematics, MDPI, vol. 7(11), pages 1-19, October.
    12. Zhang, Xiunian & Lam, Jasmine Siu Lee, 2018. "Shipping mode choice in cold chain from a value-based management perspective," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 110(C), pages 147-167.
    13. Eric Larsen & Sébastien Lachapelle & Yoshua Bengio & Emma Frejinger & Simon Lacoste-Julien & Andrea Lodi, 2022. "Predicting Tactical Solutions to Operational Planning Problems Under Imperfect Information," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 227-242, January.
    14. Xiaoli Feng & Baoyun Qiu & Yongxing Wang, 2020. "Optimizing Parallel Pumping Station Operations in an Open-Channel Water Transfer System Using an Efficient Hybrid Algorithm," Energies, MDPI, vol. 13(18), pages 1-19, September.
    15. Lingxuan Liu & Leyuan Shi, 2019. "Simulation Optimization on Complex Job Shop Scheduling with Non-Identical Job Sizes," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 36(05), pages 1-26, October.
    16. Przemysław Średziński & Martyna Świętochowska & Kamil Świętochowski & Joanna Gwoździej-Mazur, 2022. "Analysis of the Use of the PV Installation in the Power Supply of the Water Pumping Station," Energies, MDPI, vol. 15(24), pages 1-13, December.
    17. Abdul Salam Khan & Bashir Salah & Dominik Zimon & Muhammad Ikram & Razaullah Khan & Catalin I. Pruncu, 2020. "A Sustainable Distribution Design for Multi-Quality Multiple-Cold-Chain Products: An Integrated Inspection Strategies Approach," Energies, MDPI, vol. 13(24), pages 1-25, December.
    18. David D. Cho & Kurt M. Bretthauer & Jan Schoenfelder, 2023. "Patient-to-nurse ratios: Balancing quality, nurse turnover, and cost," Health Care Management Science, Springer, vol. 26(4), pages 807-826, December.
    19. Tsai, Shing Chih & Chen, Sin Ting, 2017. "A simulation-based multi-objective optimization framework: A case study on inventory management," Omega, Elsevier, vol. 70(C), pages 148-159.
    20. Zhang, Siying & Chen, Ning & Song, Xiaoming & Yang, Jia, 2019. "Optimizing decision-making of regional cold chain logistics system in view of low-carbon economy," Transportation Research Part A: Policy and Practice, Elsevier, vol. 130(C), pages 844-857.

    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:eee:ejores:v:321:y:2025:i:1:p:147-159. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.
    Лучший частный хостинг