×

Review and comparison of algorithms and software for mixed-integer derivative-free optimization. (English) Zbl 1486.90130

Summary: This paper reviews the literature on algorithms for solving bound-constrained mixed-integer derivative-free optimization problems and presents a systematic comparison of available implementations of these algorithms on a large collection of test problems. Thirteen derivative-free optimization solvers are compared using a test set of 267 problems. The testbed includes: (i) pure-integer and mixed-integer problems, and (ii) small, medium, and large problems covering a wide range of characteristics found in applications. We evaluate the solvers according to their ability to find a near-optimal solution, find the best solution among currently available solvers, and improve a given starting point. Computational results show that the ability of all these solvers to obtain good solutions diminishes with increasing problem size, but the solvers evaluated collectively found optimal solutions for 93% of the problems in our test set. The open-source solvers MISO and NOMAD were the best performers among all solvers tested. MISO outperformed all other solvers on large and binary problems, while NOMAD was the best performer on mixed-integer, non-binary discrete, small, and medium-sized problems.

MSC:

90C11 Mixed integer programming
90C56 Derivative-free methods and methods using generalized derivatives
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abramson, MA; Audet, C.; Chrissis, JW; Walston, JG, Mesh adaptive direct search algorithms for mixed variable optimization, Optim. Lett., 3, 35-37 (2009) · Zbl 1154.90551
[2] Abramson, M.A., Audet, C., Couture, G., Dennis, Jr., J.E., Le Digabel, S.: The Nomad project (Current as of 15 March, 2021). http://www.gerad.ca/nomad/
[3] Abramson, M.A., Audet, C., Dennis, J.E., Jr.: Filter pattern search algorithms for mixed variable constrained optimization problems. Department of Computational and Applied Mathematics, Rice University, Tech. rep. (2004) · Zbl 1138.65043
[4] Abramson, MA; Audet, C.; Dennis, JE Jr; Le Digabel, S., OrthoMADS: a deterministic MADS instance with orthogonal directions, SIAM J. Optim., 20, 948-966 (2009) · Zbl 1189.90202
[5] Adams, B.M., Ebeida, M.S., Eldred, M.S., Geraci, G., Jakeman, J.D., Maupin, K.A., Monschke, J.A., Swiler, L.P., Stephens, J.A., Vigil, D.M., Wildey, T.M., Bohnhoff, W.J., Dalbey, K.R., Eddy, J.P., Hooper, R.W., Hu, K.T., Hough, P.D., Ridgway, E.M., Rushdi, A.: DAKOTA, a multilevel parallel object-oriented framework for design optimization, parameter estimation, uncertainty quantification, and sensitivity analysis: version 6.5 user’s manual. Sandia National Laboratories, Albuquerque, NM and Livermore, CA (2016). https://dakota.sandia.gov/
[6] Audet, C.; Béchard, V.; Le Digabel, S., Nonsmooth optimization through mesh adaptive direct search and variable neighborhood search, J. Glob. Optim., 41, 299-318 (2008) · Zbl 1157.90535
[7] Audet, C.; Dennis, JE Jr, Pattern search algorithms for mixed variable programming, SIAM J. Optim., 11, 573-594 (2000) · Zbl 1035.90048
[8] Audet, C.; Dennis, JE Jr, Analysis of generalized pattern searches, SIAM J. Optim., 13, 889-903 (2003) · Zbl 1053.90118
[9] Audet, C.; Dennis, JE Jr, Mesh adaptive direct search algorithms for constrained optimization, SIAM J. Optim., 17, 188-217 (2006) · Zbl 1112.90078
[10] Audet, C.; Hare, W., Derivative-free and Blackbox Optimization (2017), Cham: Springer, Cham · Zbl 1391.90001
[11] Audet, C.; Le Digabel, S.; Tribes, C., The mesh adaptive direct search algorithm for granular and discrete variables, SIAM J. Optim., 29, 1164-1189 (2019) · Zbl 1411.90229
[12] Boneh, A., Golan, A.: Constraints’ redundancy and feasible region boundedness by random feasible point generator (RFPG). In: Third European Congress on Operations Research (EURO III). Amsterdam (1979)
[13] Cao, Y.; Jiang, L.; Wu, Q., An evolutionary programming approach to mixed-variable optimization problems, Appl. Math. Model., 24, 931-942 (2000) · Zbl 1168.90636
[14] Chipperfield, A.J., Fleming, P.J., Fonseca, C.M.: Genetic algorithm tools for control systems engineering. In: Proceedings of Adaptive Computing in Engineering Design and Control, vol. 128, p. 133 (1994)
[15] Ciccazzo, A.; Latorre, V.; Liuzzi, G.; Lucidi, S.; Rinaldi, F., Derivative-free robust optimization for circuit design, J. Optim. Theory Appl., 164, 842-861 (2015) · Zbl 1320.90100
[16] Conn, AR; Scheinberg, K.; Vicente, LN, Introduction to Derivative-free Optimization (2009), Philadelphia: SIAM, Philadelphia · Zbl 1163.49001
[17] Costa, A.; Nannicini, G., RBFOpt: an open-source library for black-box optimization with costly function evaluations, Math. Program. Comput., 10, 597-629 (2018) · Zbl 1411.90005
[18] Custódio, AL; Vicente, LN, Using sampling and simplex derivatives in pattern search methods, SIAM J. Optim., 18, 537-555 (2007) · Zbl 1144.65039
[19] Davis, E.; Ierapetritou, M., A kriging based method for the solution of mixed-integer nonlinear programs containing black-box functions, J. Glob. Optim., 43, 191-205 (2009) · Zbl 1179.90238
[20] Eberhart, R., Kennedy, J.: A new optimizer using particle swarm theory. In: Proceedings of the Sixth International Symposium on Micro Machine and Human Science, pp. 39-43. Nagoya, Japan (1995)
[21] Fermi, E., Metropolis, N.: Numerical solution of minimum problem. Los Alamos Unclassified Report LA-1492, Los Alamos National Laboratory, Los Alamos (1952)
[22] Fowler, K.; Reese, J.; Kees, C.; Dennis, J. Jr; Kelley, C.; Miller, C.; Audet, C.; Booker, A.; Couture, G.; Darwin, R.; Farthing, M.; Finkel, D.; Gablonsky, J.; Gray, G.; Kolda, T., Comparison of derivative-free optimization methods for groundwater supply and hydraulic capture community problems, Adv. Water Resour., 31, 743-757 (2008)
[23] García-Palomares, U.; Costa-Montenegro, E.; Asorey-Cacheda, R.; González-Castaño, F., Adapting derivative free optimization methods to engineering models with discrete variables, Optim. Eng., 13, 579-594 (2012) · Zbl 1293.65092
[24] Gross, B.; Roosen, P., Total process optimization in chemical engineering with evolutionary algorithms, Comput. Chem. Eng., 22, S229-S236 (1998)
[25] Hemker, T.; Fowler, KR; Farthing, MW; von Stryk, O., A mixed-integer simulation-based optimization approach with surrogate functions in water resources management, Optim. Eng., 9, 341-360 (2008) · Zbl 1419.90007
[26] Holland, J.H.: Adaptation in Natural and Artificial Systems. The University of Michigan Press (1975) · Zbl 0317.68006
[27] Holmström, K., Göran, A.O., Edvall, M.M.: User’s guide for TOMLAB/OQNLP. Tomlab Optimization (2007). http://tomopt.com
[28] Holmström, K., Göran, A.O., Edvall, M.M.: User’s guide for TOMLAB 7. Tomlab Optimization (Current as of 15 March, 2021). http://tomopt.com
[29] Holmström, K.; Quttineh, NH; Edvall, MM, An adaptive radial basis algorithm (ARBF) for expensive black-box mixed-integer constrained global optimization, Optim. Eng., 9, 311-339 (2008) · Zbl 1400.90226
[30] Hooke, R.; Jeeves, TA, Direct search solution of numerical and statistical problems, J. Assoc. Comput. Mach., 8, 212-219 (1961) · Zbl 0111.12501
[31] Huyer, W.; Neumaier, A., Global optimization by multilevel coordinate search, J. Glob. Optim., 14, 331-355 (1999) · Zbl 0956.90045
[32] Huyer, W.; Neumaier, A., SNOBFIT—stable noisy optimization by branch and fit, ACM Trans. Math. Softw., 35, 1-25 (2008)
[33] Jones, DR; Floudas, CA; Pardalos, PM, The DIRECT global optimization algorithm, Encyclopedia of Optimization, 431-440 (2001), Boston: Kluwer Academic Publishers, Boston · Zbl 1027.90001
[34] Kennedy, J., Eberhart, R.: Particle swarm optimization. In: Proceedings of the IEEE International Conference on Neural Networks, pp. 1942-1948. Piscataway, NJ, USA (1995)
[35] Kirkpatrick, S.; Gelatt, CD; Vecchi, MP, Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162
[36] Kleijnen, JPC; Van Beers, W.; Van Nieuwenhuyse, I., Constrained optimization in expensive simulation: novel approach, Eur. J. Oper. Res., 202, 164-174 (2010) · Zbl 1189.90156
[37] Laguna, M.; Gortázar, F.; Gallego, M.; Duarte, A.; Martí, R., A black-box scatter search for optimization problems with integer variables, J. Glob. Optim., 58, 497-516 (2014) · Zbl 1305.90304
[38] Larson, J., Leyffer, S., Palkar, P., Wild, S.: A method for convex black-box integer global optimization (2019). arXiv:1903.11366 · Zbl 1473.90181
[39] Lewis, RM; Torczon, VJ, Pattern search algorithms for bound constrained minimization, SIAM J. Optim., 9, 1082-1099 (1999) · Zbl 1031.90047
[40] Liao, T.; Socha, K.; de Oca, M.; Stützle, T.; Dorigo, M., Ant colony optimization for mixed-variable optimization problems, IEEE Trans. Evol. Comput., 18, 503-518 (2013)
[41] Liu, J.; Ploskas, N.; Sahinidis, N., Tuning baron using derivative-free optimization algorithms, J. Glob. Optim., 74, 4, 611-637 (2019) · Zbl 1428.90135
[42] Liuzzi, G.; Lucidi, S.; Rinaldi, F., Derivative-free methods for bound constrained mixed-integer optimization, Comput. Optim. Appl., 53, 505-526 (2012) · Zbl 1257.90058
[43] Liuzzi, G.; Lucidi, S.; Rinaldi, F., Derivative-free methods for mixed-integer constrained optimization problems, J. Optim. Theory Appl., 164, 933-965 (2015) · Zbl 1321.90087
[44] Liuzzi, G.; Lucidi, S.; Rinaldi, F., An algorithmic framework based on primitive directions and nonmonotone line searches for black-box optimization problems with integer variables, Math. Program. Comput., 12, 673-702 (2020) · Zbl 1452.90322
[45] Liuzzi, G.; Lucidi, S.; Sciandrone, M., Sequential penalty derivative-free methods for nonlinear constrained optimization, SIAM J. Optim., 20, 2614-2635 (2010) · Zbl 1223.65045
[46] Lucidi, S.: DFL—derivative-free library (current as of 15 March, 2021). http://www.dis.uniroma1.it/ lucidi/DFL/
[47] Lucidi, S.; Piccialli, V.; Sciandrone, M., An algorithm model for mixed variable programming, SIAM J. Optim., 15, 1057-1084 (2005) · Zbl 1077.65064
[48] Lucidi, S.; Sciandrone, M., A derivative-free algorithm for bound constrained optimization, Comput. Optim. Appl., 21, 119-142 (2002) · Zbl 0988.90033
[49] Matheron, G., Principles of geostatistics, Econ. Geol., 58, 1246-1266 (1967)
[50] Moré, J.; Wild, S., Benchmarking derivative-free optimization algorithms, SIAM J. Optim., 20, 172-191 (2009) · Zbl 1187.90319
[51] Müller, J., Miso: mixed-integer surrogate optimization framework, Optim. Eng., 17, 177-203 (2016) · Zbl 1364.90230
[52] Müller, J.: Miso: mixed-integer surrogate optimization framework (current as of 15 March, 2021). https://optimization.lbl.gov/downloads#h.p_BjSaeAORU9gm
[53] Müller, J.; Shoemaker, CA; Piché, R., SO-MI: a surrogate model algorithm for computationally expensive nonlinear mixed-integer black-box global optimization problems, Comput. Oper. Res., 40, 1383-1400 (2013) · Zbl 1352.90067
[54] Müller, J.; Shoemaker, CA; Piché, R., SO-I: a surrogate model algorithm for expensive nonlinear integer programming problems including global optimization applications, J. Glob. Optim., 59, 865-889 (2014) · Zbl 1305.90305
[55] Nelder, JA; Mead, R., A simplex method for function minimization, Comput. J., 7, 308-313 (1965) · Zbl 0229.65053
[56] Neumaier, A.: SNOBFIT—stable noisy optimization by branch and FIT (current as of 15 March, 2021). http://www.mat.univie.ac.at/ neum/software/snobfit/
[57] Newby, E.; Ali, MM, A trust-region-based derivative free algorithm for mixed integer programming, Comput. Optim. Appl., 60, 199-229 (2015) · Zbl 1308.90112
[58] Ploskas, N.; Laughman, C.; Raghunathan, A.; Sahinidis, N., Optimization of circuitry arrangements for heat exchangers using derivative-free optimization, Chem. Eng. Res. Des., 131, 16-28 (2018)
[59] Porcelli, M.; Toint, PL, BFO, a trainable derivative-free brute force optimizer for nonlinear bound-constrained optimization and equilibrium computations with continuous and discrete variables, ACM Trans. Math. Softw., 44, 1-25 (2017) · Zbl 1484.65136
[60] Powell, M.J.D.: The BOBYQA algorithm for bound constrained optimization without derivatives. Tech. rep., Department of Applied Mathematics and Theoretical Physics, University of Cambridge (2009)
[61] Rashid, K.; Ambani, S.; Cetinkaya, E., An adaptive multiquadric radial basis function method for expensive black-box mixed-integer nonlinear constrained optimization, Eng. Optim., 45, 185-206 (2013)
[62] Rios, LM; Sahinidis, NV, Derivative-free optimization: a review of algorithms and comparison of software implementations, J. Glob. Optim., 56, 1247-1293 (2013) · Zbl 1272.90116
[63] Sauk, B.; Ploskas, N.; Sahinidis, N., GPU parameter tuning for tall and skinny dense linear least squares problems, Optim. Methods Softw., 35, 638-660 (2018) · Zbl 1445.90107
[64] Schlüter, M.; Egea, JA; Banga, JR, Extended ant colony optimization for non-convex mixed integer nonlinear programming, Comput. Oper. Res., 36, 2217-2229 (2009) · Zbl 1158.90391
[65] Schlüter, M.; Gerdts, M., The oracle penalty method, J. Glob. Optim., 47, 293-325 (2010) · Zbl 1190.90219
[66] Schlüter, M., Munetomo, M.: MIDACO user guide. MIDACO-SOLVER (2016). http://www.midaco-solver.com/
[67] Socha, K.; Dorigo, M., Ant colony optimization for continuous domains, Eur. J. Oper. Res., 185, 1155-1173 (2008) · Zbl 1146.90537
[68] Spendley, W.; Hext, GR; Himsworth, FR, Sequential application for simplex designs in optimisation and evolutionary operation, Technometrics, 4, 441-461 (1962) · Zbl 0121.35603
[69] Sriver, TA; Chrissis, JW; Abramson, MA, Pattern search ranking and selection algorithms for mixed variable simulation-based optimization, Eur. J. Oper. Res., 198, 878-890 (2009) · Zbl 1176.90269
[70] Tawarmalani, M.; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249 (2005) · Zbl 1099.90047
[71] Toint, P.L., Porcelli, M.: BFO—brute-force optimizer (current as of 15 March, 2021). https://sites.google.com/site/bfocode/home
[72] Torczon, VJ, On the convergence of pattern search algorithms, SIAM J. Optim., 7, 1-25 (1997) · Zbl 0884.65053
[73] Vicente, LN, Implicitly and densely discrete black-box optimization problems, Optim. Lett., 3, 475-482 (2009) · Zbl 1170.90441
[74] Vigerske, S.: Minlplib 2. In: Proceedings of the XII Global Optimization Workshop MAGO, pp. 137-140 (2014)
[75] Winfield, D.: Function and functional optimization by interpolation in data tables. Ph.D. thesis, Harvard University, Cambridge, MA (1969)
[76] Winslow, T.A., Trew, R.J., Gilmore, P., Kelley, C.T.: Simulated performance optimization of GaAs MESFET amplifiers. In: IEEE/Cornell Conference on Advanced Concepts in High Speed Semiconductor Devices and Circuits, pp. 393-402. Piscataway, NJ (1991)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.