×

zbMATH — the first resource for mathematics

Constrained optimization in expensive simulation: novel approach. (English) Zbl 1189.90156
Summary: This article presents a novel heuristic for constrained optimization of computationally expensive random simulation models. One output is selected as objective to be minimized, while other outputs must satisfy given threshold values. Moreover, the simulation inputs must be integer and satisfy linear or nonlinear constraints. The heuristic combines (i) sequentialized experimental designs to specify the simulation input combinations; (ii) Kriging (or Gaussian process or spatial correlation modeling) to analyze the global simulation input/output data resulting from these designs; and (iii) integer nonlinear programming to estimate the optimal solution from the Kriging metamodels. The heuristic is applied to an \((s,S)\) inventory system and a call-center simulation, and compared with the popular commercial heuristic OptQuest embedded in the Arena versions 11 and 12. In these two applications the novel heuristic outperforms OptQuest in terms of number of simulated input combinations and quality of the estimated optimum.

MSC:
90C30 Nonlinear programming
90C59 Approximation methods and heuristics in mathematical programming
Software:
bootstrap; DACE; EGO; OptQuest
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abspoel, S.J.; Etman, L.F.P.; Vervoort, J.; van Rooij, R.A.; Schoofs, A.J.G.; Rooda, J.E., Simulation based optimization of stochastic systems with integer design variables by sequential multipoint linear approximation, Struct. multidiscip. optim., 22, 125-138, (2001)
[2] Angün, E., den Hertog, D., Gürkan, G., Kleijnen, J.P.C., 2002. Response surface methodology revisited. In: Yucesan, E., Chen, C.H., Snowdon, J.L., Charnes, J.M. (Eds.), Proceedings of the 2002 Winter Simulation Conference, pp. 377-383.
[3] Ankenman, B., Nelson, B., Staum, J., 2008. Stochastic Kriging for simulation metamodeling. In: Mason, S.J., Hill, R.R., Moench, L., Rose, O. (Eds.), Proceedings of the 2008 Winter Simulation Conference, pp. 362-370. · Zbl 1342.62134
[4] Atlason, J.; Epelman, M.A.; Henderson, S.G., Optimizing call center staffing using simulation and analytic center cutting-plane methods, Management science, 54, 295-309, (2008) · Zbl 1232.90266
[5] Avramidis, A.N., Pisacane, O., Gendreau, M., L’ Ecuyer, P., 2007. Simulation-based optimization of agent scheduling in a multiskill call center. In: Ottjes, J., Veeke, H., (Eds.), Fifth International Industrial Simulation Conference, ISC’2007, Delft, Netherlands, pp. 255-263.
[6] Barton, R.R.; Meckesheimer, M., Metamodel-based simulation optimization, (), 535-574
[7] Bashyam, S.; Fu, M.C., Optimization of (s,S) inventory systems with random lead times and a service level constraint, Management science, 44, 243-256, (1998) · Zbl 0989.90004
[8] Bates, R.A.; Kenett, R.S.; Steinberg, D.M.; Wynn, H.P., Achieving robust design from computer simulations, Quality technology and quantitative management, 3, 161-177, (2006) · Zbl 1309.93063
[9] Beyer, H.; Sendhoff, B., Robust optimization – a comprehensive survey, Computer methods in applied mechanics and engineering, 196, 3190-3218, (2007) · Zbl 1173.74376
[10] Biles, W.E., Kleijnen, J.P.C., van Beers, W.C.M., van Nieuwenhuyse, I., 2007. Kriging metamodels in constrained simulation optimization: An explorative study. In: Henderson, S.G., Biller, B., Hsieh, M.-H., Shortle, J., Tew, J.D., Barton, R.R., (Eds.), Proceedings of 2007 Winter Simulation Conference, pp. 355-362.
[11] Branke, J.; Chick, S.E.; Schmidt, C., Selecting a selection procedure, Management science, 53, 1916-1932, (2007) · Zbl 1232.62042
[12] Cezik, M.T.; L’Ecuyer, P., Staffing multiskill call centers via linear programming and simulation, Management science, 54, 310-323, (2008) · Zbl 1232.90301
[13] Chilès, J.-P.; Delfiner, P., Geostatistics: modeling spatial uncertainty, (1999), Wiley New York · Zbl 0922.62098
[14] Cioppa, T.M.; Lucas, T.W., Efficient nearly orthogonal and space-filling Latin hypercubes, Technometrics, 49, 45-55, (2007)
[15] Cressie, N.A.C., Statistics for spatial data: revised edition, (1993), Wiley New York
[16] Davis, E.; Ierapetritou, M., A Kriging based method for the solution of mixed-integer nonlinear programs containing black-box functions, Journal of global optimization, 43, 191-205, (2009) · Zbl 1179.90238
[17] Den Hertog, D.; Kleijnen, J.P.C.; Siem, A.Y.D., The correct Kriging variance estimated by bootstrapping, Journal of the operational research society, 57, 400-409, (2006) · Zbl 1086.62042
[18] Driessen, L., Brekelmans, R.C.M., Gerichhausen, M., Hamers, H., den Hertog, D., 2006a. Why methods for optimization problems with time consuming function evaluations and integer variables should use global approximation models. CentER Discussion Paper 2006-04, CentER, Tilburg University, Tilburg, The Netherlands.
[19] Driessen, L.; Brekelmans, R.; Hamers, H.; den Hertog, D., On D-optimality based trust regions for black-box optimization problems, Structural and multidisciplinary optimization, 31, 40-48, (2006) · Zbl 1245.90147
[20] Efron, B.; Tibshirani, R.J., An introduction to the bootstrap, (1993), Chapman & Hall New York · Zbl 0835.62038
[21] Fu, M.C., Optimization for simulation: theory vs. practice, Informs journal on computing, 14, 192-215, (2002) · Zbl 1238.90001
[22] Fu, M.C., Are we there yet? the marriage between simulation and optimization, OR/MS today, 34, 16-17, (2007)
[23] Greenberg, H.J.; Morisson, T., Robust optimization, ()
[24] Grossmann, I.E., Review of nonlinear mixed-integer and disjunctive programming techniques, Optimization and engineering, 3, 227-252, (2002) · Zbl 1035.90050
[25] Huang, D.; Allen, T.T.; Notz, W.; Zheng, N., Global optimization of stochastic black-box systems via sequential Kriging meta-models, Journal of global optimization, 34, 441-466, (2006) · Zbl 1098.90097
[26] Jones, D.R.; Schonlau, M.; Welch, W.J., Efficient global optimization of expensive black-box functions, Journal of global optimization, 13, 455-492, (1998) · Zbl 0917.90270
[27] Joseph, V.R.; Hung, Y.; Sudjianto, A., Blind Kriging: A new method for developing metamodels, Journal of mechanical design, 130, 3, 031102, (2008)
[28] Kelly, J.P., Simulation optimization is evolving, Informs journal on computing, 14, 223-225, (2002)
[29] Kelton, W.D.; Sadowski, R.P.; Sturrock, D.T., Simulation with arena, (2007), McGraw-Hill Boston
[30] Kenett, R.; Steinberg, D., New frontiers in design of experiments, Quality progress, 61-65, (2006)
[31] Kleijnen, J.P.C., Design and analysis of simulation experiments, (2008), Springer Science+Business Media
[32] Kleijnen, J.P.C., Kriging metamodeling in simulation: A review, European journal of operation research, 192, 707-716, (2009) · Zbl 1157.90544
[33] Kleijnen, J.P.C.; Deflandre, D., Validation of regression metamodels in simulation: bootstrap approach, European journal of operation research, 170, 120-131, (2006) · Zbl 1330.62201
[34] Kleijnen, J.P.C.; van Beers, W.C.M., Application-driven sequential designs for simulation experiments: Kriging metamodeling, Journal of operation research society, 55, 876-883, (2004) · Zbl 1060.62090
[35] Kleijnen, J.P.C.; Wan, J., Optimization of simulated systems: optquest and alternatives, Simulation modelling practice and theory, 15, 354-362, (2007)
[36] Law, A.M., Simulation modeling and analysis, (2007), McGraw-Hill Boston
[37] Lophaven, S.N., Nielsen, H.B., Sondergaard, J., 2002. DACE: A Matlab Kriging toolbox, version 2.0. IMM Technical University of Denmark, Lyngby.
[38] Martin, J.D., Simpson, T.W., 2004. A Monte Carlo simulation of the Kriging model. In: Tenth AIAA/ISSMO Symposium on Multidisciplinary Analysis and Optimization, AIAA-2004-4483.
[39] Martin, J.D.; Simpson, T.W., Use of Kriging models to approximate deterministic computer models, AIAA journal, 43, 4, 853-863, (2005)
[40] Miller, R.G., Simultaneous statistical inference, (1981), Springer New York · Zbl 0463.62002
[41] Oden, J.T., 2006. Revolutionizing engineering science through simulation. National Science Foundation (NSF), Blue Ribbon Panel on Simulation-Based Engineering Science.
[42] Pasupathy, R., Henderson, S.G., 2006. A testbed of simulation-optimization problems. In: Perrone, L.F., Wieland, F.P., Liu, J., Lawson, B.G., Nicol, D.M., Fujimoto, R.M., (Eds.), Proceedings of 2006 Winter Simulation Conference, pp. 255-263.
[43] Pintér, J.D., Computational global optimization: state-of-the-art and perspectives, OR/MS today, 34, 5, 18-19, (2007)
[44] Rosen, S.C.; Harmonosky, C.M.; Traband, M.T., Optimization of systems with multiple performance measures via simulation: survey and recommendations, Computers and industrial engineering, 54, 2, 327-339, (2007)
[45] Sacks, J.; Welch, W.J.; Mitchell, T.J.; Wynn, H.P., Design and analysis of computer experiments (includes comments and rejoinder), Statistical science, 4, 4, 409-435, (1989) · Zbl 0955.62619
[46] Santner, T.J.; Williams, B.J.; Notz, W.I., The design and analysis of computer experiments, (2003), Springer-Verlag New York · Zbl 1041.62068
[47] Van Beers, W.C.M.; Kleijnen, J.P.C., Customized sequential designs for random simulation experiments: Kriging metamodeling and bootstrapping, European journal of operation research, 186, 3, 1099-1113, (2008) · Zbl 1133.62060
[48] Wackernagel, H., Multivariate geostatistics: an introduction with applications, (2003), Springer-Verlag Berlin · Zbl 1015.62128
[49] Yin, J., Ng, S.H., Ng, K.M., in press. Kriging model with modified nugget effect. In: Proceedings of the 2008 IEEE International Conference on Industrial Engineering and Engineering Management.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.