Abstract
Metaheuristics are known to be effective in finding good solutions in combinatorial optimization, but solving stochastic problems is costly due to the need for evaluation of multiple scenarios. We propose a general method to reduce the number of scenario evaluations per solution and thus improve metaheuristic efficiency. We use a sequential sampling procedure exploiting estimates of the solutions’ expected objective values. These values are obtained with a predictive model, which is founded on an estimated discrete probability distribution linearly related to all solutions’ objective distributions; the probability distribution is continuously refined based on incoming solution evaluation. The proposed method is tested using simulated annealing, but in general applicable to single solution metaheuristics. The method’s performance is compared to descriptive sampling and an adaptation of a sequential sampling method assuming noisy evaluations. Experimental results on three problems indicate the proposed method is robust overall, and performs better on average than the baselines on two of the problems.
K. Postek—Independent Researcher.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Amaran, S., Sahinidis, N.V., Sharda, B., Bury, S.J.: Simulation optimization: a review of algorithms and applications. Ann. Oper. Res. 240, 351–380 (2016). https://doi.org/10.1007/s10479-015-2019-x
Ball, R.C., Branke, J., Meisel, S.: Optimal sampling for simulated annealing under noise. INFORMS J. Comput. 30, 200–215 (2018). https://doi.org/10.1287/ijoc.2017.0774
Ballestín, F.: When it is worthwhile to work with the stochastic RCPSP? J. Sched. 10, 153–166 (2007). https://doi.org/10.1007/s10951-007-0012-1
Ballestín, F., Leus, R.: Resource-constrained project scheduling for timely project completion with stochastic activity durations. Prod. Oper. Manag. 18, 459–474 (2009). https://doi.org/10.1111/j.1937-5956.2009.01023.x
Bartz-Beielstein, T., Blum, D., Branke, J.: Particle swarm optimization and sequential sampling in noisy environments. In: Doerner, K.F., Gendreau, M., Greistorfer, P., Gutjahr, W., Hartl, R.F., Reimann, M. (eds.) Metaheuristics. ORSIS, vol. 39, pp. 261–273. Springer, Boston, MA (2007). https://doi.org/10.1007/978-0-387-71921-4_14
Bellman, R.: Dynamic programming. Science 153(3731), 34–37 (1966). https://doi.org/10.1126/science.153.3731.34
Bianchi, L., Dorigo, M., Gambardella, L.M., Gutjahr, W.J.: A survey on metaheuristics for stochastic combinatorial optimization. Nat. Comput. 8, 239–287 (2009). https://doi.org/10.1007/s11047-008-9098-4
Birge, J.R., Louveaux, F.: Introduction to Stochastic Programming. Springer, New York (2011). https://doi.org/10.1007/978-1-4614-0237-4
Bouneffouf, D., Rish, I., Aggarwal, C.: Survey on applications of multi-armed and contextual bandits. In: 2020 IEEE Congress on Evolutionary Computation (CEC), pp. 1–8. (2020). https://doi.org/10.1109/CEC48606.2020.9185782
Bulgak, A.A., Sanders, J.L.: Integrating a modified simulated annealing algorithm with the simulation of a manufacturing system to optimize buffer sizes in automatic assembly systems. In: 1988 Winter Simulation Conference Proceedings, pp. 684–690. (1988). https://doi.org/10.1109/WSC.1988.716241
Chen, Z., Demeulemeester, E., Bai, S., Guo, Y.: Efficient priority rules for the stochastic resource-constrained project scheduling problem. Eur. J. Oper. Res. 270, 957–967 (2018). https://doi.org/10.1016/j.ejor.2018.04.025
Dumouchelle, J., Julien, E., Kurtz, J., Khalil, E.B.: Neur2ro: neural two-stage robust optimization. arXiv preprint (2023). https://doi.org/10.48550/ARXIV.2310.04345
Gelman, A., Carlin, J.B., Stern, H.S., Rubin, D.B.: Bayesian Data Analysis. Chapman and Hall/CRC, Boca Raton (1995). https://doi.org/10.1201/9780429258411
Groves, M., Branke, J.: Sequential sampling for noisy optimisation with CMA-ES. In: Proceedings of the 2018 Genetic and Evolutionary Computation Conference, pp. 1023–1030. Association for Computing Machinery, Inc., (2018). https://doi.org/10.1145/3205455.3205559
Juan, A.A., Faulin, J., Grasman, S.E., Rabe, M., Figueira, G.: A review of simheuristics: extending metaheuristics to deal with stochastic combinatorial optimization problems. Oper. Res. Perspect. 2, 62–72 (2015). https://doi.org/10.1016/j.orp.2015.03.001
Juan, A.A., et al.: A review of the role of heuristics in stochastic optimisation: from metaheuristics to learnheuristics. Ann. Oper. Res. (2021). https://doi.org/10.1007/s10479-021-04142-9
Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220, 671–680 (1983). https://doi.org/10.1126/science.220.4598.671
Kleywegt, A.J., Shapiro, A., Homem-de-mello, T.: The sample average approximation method for stochastic discrete optimization. Soc. Ind. Appl. Math. 12, 479–502 (2001). https://doi.org/10.1137/S1052623499363220
Kolisch, S.: Psplib a project scheduling problem library. Eur. J. Oper. Res. 96, 205–216 (1996). https://doi.org/10.1016/S0377-2217(96)00170-1
Kolisch, R., Hartmann, S.: Heuristic algorithms for the resource-constrained project scheduling problem: classification and computational analysis. In: Weglarz, J. (eds.) Project Scheduling. International Series in Operations Research & Management Science, LNCS, vol. 14, pp. 147–178. Springer, Boston, MA (1999). https://doi.org/10.1007/978-1-4615-5533-9_7
Lattimore, T., Szepesvári, C.: Bandit Algorithms. Cambridge University Press, Cambridge (2020). https://doi.org/10.1017/9781108571401
Lei, H., Laporte, G., Guo, B.: The capacitated vehicle routing problem with stochastic demands and time windows. Comput. Oper. Res. 38, 1775–1783 (2011). https://doi.org/10.1016/j.cor.2011.02.007
Liu, N., Truong, V.A., Wang, X., Anderson, B.R.: Integrated scheduling and capacity planning with considerations for patients’ length-of-stays. Prod. Oper. Manag. 28, 1735–1756 (2019). https://doi.org/10.1111/poms.13012
Min, D., Yih, Y.: Scheduling elective surgery under uncertainty and downstream capacity constraints. Eur. J. Oper. Res. 206, 642–652 (2010). https://doi.org/10.1016/j.ejor.2010.03.014
Prudius, A.A., Andradóttir, S.: Averaging frameworks for simulation optimization with applications to simulated annealing. Nav. Res. Logist. 59, 411–429 (2012). https://doi.org/10.1002/nav.21496
Rahimi, I., Gandomi, A.H.: A comprehensive review and analysis of operating room and surgery scheduling. Arch. Comput. Methods Eng. 28, 1667–1688 (2021). https://doi.org/10.1007/s11831-020-09432-2
Ritzinger, U., Puchinger, J., Hartl, R.F.: A survey on dynamic and stochastic vehicle routing problems. Int. J. Prod. Res. 54, 215–231 (2016). https://doi.org/10.1080/00207543.2015.1043403
Rostami, S., Creemers, S., Leus, R.: New strategies for stochastic resource-constrained project scheduling. J. Sched. 21, 349–365 (2018). https://doi.org/10.1007/s10951-016-0505-x
Saliby, E.: Descriptive sampling: a better approach to Monte Carlo simulation. Source J. Oper. Res. Soc. 41, 1133–1142 (1990). https://doi.org/10.2307/2583110
Schutte, N.: Codebase experiments sequential predictive sampling. https://github.com/NoahJSchutte/sequential-predictive-sampling. Accessed 21 Mar 2024
Schutte, N., van den Houten, K., Eigbe, E.: Dynamic scenario reduction for simulation based optimization under uncertainty, working notes of the data science meets optimisation workshop at IJCAI 2022. https://drive.google.com/file/d/1kxzgO8ZhW2bjXo1vwVskK4_5LNRbp5vj/view?usp=sharing. Accessed 21 Mar 2024
Seyyedabbasi, A.: A reinforcement learning-based metaheuristic algorithm for solving global optimization problems. Adv. Eng. Softw. 178, 103411 (2023). https://doi.org/10.1016/j.advengsoft.2023.103411
Shehadeh, K.S.: Data-driven distributionally robust surgery planning in flexible operating rooms over a wasserstein ambiguity. Comput. Oper. Res. 146 (2022). https://doi.org/10.1016/j.cor.2022.105927
Shehadeh, K.S., Zuluaga, L.F.: 14th AIMMS-MOPTA optimization modeling competition 2022: surgery scheduling in flexible operating rooms under uncertainty. https://iccopt2022.lehigh.edu/ competition-and-prizes/aimms-mopta-competition/. Accessed 21 Mar 2024
Solomon, M.M.: Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35, 254–265 (1987). https://doi.org/10.1287/opre.35.2.254
Vajda, S.: Mathematical Programming. Courier Corporation, Chelmsford (2009)
Zakaria, A., Ismail, F.B., Lipu, M.S., Hannan, M.A.: Uncertainty models for stochastic optimization in renewable energy applications. Renew. Energy 145, 1543–1571 (2020). https://doi.org/10.1016/j.renene.2019.07.081
Zhu, S., Fan, W., Yang, S., Pei, J., Pardalos, P.M.: Operating room planning and surgical case scheduling: a review of literature. J. Comb. Optim. 37, 757–805 (2019). https://doi.org/10.1007/s10878-018-0322-6
Acknowledgements
We thank the reviewers for their suggestions. This work was partially supported by Epistemic AI and by TAILOR, both funded by EU Horizon 2020 under grants 964505 and 952215 respectively.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Schutte, N., Postek, K., Yorke-Smith, N. (2024). Improving Metaheuristic Efficiency for Stochastic Optimization by Sequential Predictive Sampling. In: Dilkina, B. (eds) Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2024. Lecture Notes in Computer Science, vol 14743. Springer, Cham. https://doi.org/10.1007/978-3-031-60599-4_10
Download citation
DOI: https://doi.org/10.1007/978-3-031-60599-4_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-60601-4
Online ISBN: 978-3-031-60599-4
eBook Packages: Computer ScienceComputer Science (R0)