[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Tuning BARON using derivative-free optimization algorithms

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

Optimization solvers include many options that allow users to control algorithmic aspects that may have a considerable impact on solver performance. Tuning solver options is often necessary to reduce execution time and improve solution quality. Previous studies of solver tuning techniques have focused on mixed-integer linear programming and local nonlinear programming solvers. In this paper, we investigate the potential of tuning a global optimization solver for nonlinear and mixed-integer nonlinear programming problems. In particular, derivative-free optimization (DFO) algorithms are used to find optimal values for options of the global optimization solver BARON. A set of 126 problems from the GLOBALLib and MINLPLib collections are utilized in a computational study from which we conclude that tuning options can improve the default performance of BARON for individual problems and an entire library. Additionally, we present a systematic comparison of 27 DFO solvers in terms of their ability to improve the performance of the global solver. We find that several DFO implementations are much better than others in terms of finding optimal tuning parameters.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

References

  1. Audet, C., Dennis Jr., J.E.: Mesh adaptive direct search algorithms for constrained optimization. SIAM J. Optim. 17, 188–217 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  2. Audet, C., Orban, D.: Finding optimal algorithmic parameters using derivative-free optimization. Soc. Ind. Appl. Math. 17, 642–664 (2001)

    MathSciNet  MATH  Google Scholar 

  3. Bao, X., Sahinidis, N.V., Tawarmalani, M.: Multiterm polyhedral relaxations for nonconvex, quadratically-constrained quadratic programs. Optim. Methods Softw. 24, 485–504 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bartholomew-Biggs, M.C., Parkhurst, S.C., Wilson, S.P.: Using DIRECT to solve an aircraft routing problem. Comput. Optim. Appl. 21, 311–323 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  5. Baz, M., Hunsaker, B.: Automated Tuning of Optimization Software Parameters. Technical report. Department of Industrial Engineering, University of Pittsburgh, Pittsburgh, PA (2007)

  6. Baz, M., Hunsaker, B., Prokopyev, O.: How much do we “pay” for using default parameters? Comput. Optim. Appl. 48, 91–108 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  7. Bussieck, M.R., Drud, A.S., Meeraus, A.: MINLPLib-A collection of test models for mixed-integer nonlinear programming. INFORMS J. Comput. 15, 114–119 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  8. Chen, W., Shao, Z., Wang, K., Chen, X., Biegler, L.T.: Random sampling-based automatic parameter tuning for nonlinear programming solvers. Ind. Eng. Chem. Res. 50, 3907–3918 (2011)

    Article  Google Scholar 

  9. Conn, A.R., Scheinberg, K., Toint, P.L.: On the convergence of derivative-free methods for unconstrained optimization. In: Buhmann, M.D., Iserles, A. (eds.) Approximation Theory and Optimization, Tribute to M. J. D. Powell, pp. 83–108. Cambridge University Press, Cambridge (1996)

    Google Scholar 

  10. Custódio, A.L., Dennis Jr., J.E., Vicente, L.N.: Using simplex gradients of nonsmooth functions in direct search methods. IMA J. Numer. Anal. 28, 770–784 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  11. Fan, S.S., Zahara, E.: A hybrid simplex search and particle swarm optimization for unconstrained optimization. Eur. J. Oper. Res. 181, 527–548 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  12. Fowler, K.R., Reese, J.P., Kees, C.E., Dennis Jr., J.E., Kelley, C.T., Miller, C.T., Audet, C., Booker, A.J., Couture, G., Darwin, R.W., Farthing, M.W., Finkel, D.E., Gablonsky, J.M., Gray, G., Kolda, T.G.: A comparison of derivative-free optimization methods for groundwater supply and hydraulic capture community problems. Adv. Water Resour. 31, 743–757 (2008)

    Article  Google Scholar 

  13. GLOBAL Library. http://www.gamsworld.org/global/globallib.htm. Accessed 25 Feb 2018

  14. Gutmann, H.M.: A radial basis function method for global optimization. J. Glob. Optim. 19, 201–227 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  15. Han, J., Kokkolaras, M., Papalambros, P.Y.: Optimal design of hybrid fuel cell vehicles. J. Fuel Cell Sci. Technol. 5, 041014 (2008)

    Article  Google Scholar 

  16. Hutter, F., Hoos, H.H., Stützle, T.: Automatic algorithm configuration based on local search. In: Howe, A., Holte, R.C. (eds.) Proceedings of the 22nd National Conference on Artificial Intelligence, pp. 1152–1157. AAAI Press, Menlo Park, CA (2007)

    Google Scholar 

  17. Hutter, F., Hoos, H.H., Leyton-Brown, K.: Automated configuration of mixed integer programming solvers. LNCS 6140, 186–202 (2010)

    Google Scholar 

  18. Hutter, F., Hoos, H.H., Leyton-Brown, K.: Sequential model-based optimization for general algorithm configurations. In: Coello, C.A.C. (ed.) Learning and Intelligent Optimization, pp. 507–523. Springer, Berlin (2011)

  19. Hutter, F., Hoos, H.H., Leyton-Brown, K., Stützle, T.: ParamILS: an antomatic algorithm configuration framework. J. Artif. Intell. Res. 36, 267–306 (2009)

    Article  MATH  Google Scholar 

  20. Huyer, W., Neumaier, A.: Global optimization by multilevel coordinate search. J. Glob. Optim. 14, 331–355 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  21. Hvattum, L.M., Glover, F.: Finding local optima of high-dimensional functions using direct search methods. Eur. J. Oper. Res. 195, 31–45 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  22. Ingber, L.: Adaptive Simulated Annealing (ASA). http://www.ingber.com/#ASA. Accessed 25 Feb 2018

  23. Jones, D.R., Perttunen, C.D., Stuckman, B.E.: Lipschitzian optimization without the Lipschitz constant. J. Optim. Theory Appl. 79, 157–181 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  24. Liu, M.L., Sahinidis, N.V., Shectman, J.P.: Planning of chemical process networks via global concave minimization. In: Grossmann, I.E. (ed.) Global Optimization in Engineering Design, pp. 195–230. Kluwer Academic Publishers, Boston (1996)

    Chapter  Google Scholar 

  25. Mongeau, M., Karsenty, H., Rouzé, V., Hiriart-Urruty, J.B.: Comparison of public-domain software for black box global optimization. Optim. Methods Softw. 13, 203–226 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  26. Moré, J.M., Wild, S.M.: Benchmarking derivative-free optimization algorithms. SIAM. J. Optim. 20(1), 172–191 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  27. Nelder, J.A., Mead, R.: A simplex method for function minimization. Comput. J. 7, 308–313 (1965)

    Article  MathSciNet  MATH  Google Scholar 

  28. Powell, M.J.D.: A direct search optimization method that models the objective and constraint functions by linear interpolation. In: Gomez, S., Hennart, J.P. (eds.) Advances in Optimization and Numerical Analysis, pp. 51–67. Kluwer Academic, Dordrecht (1994)

    Chapter  Google Scholar 

  29. Powell, M.J.D.: Recent research at Cambridge on radial basis functions. Technical report. Department of Applied Mathematics and Theoretical Physics, University of Cambridge (1998)

  30. Puranik, Y., Sahinidis, N.V.: Bounds tightening based on optimality conditions for nonconvex box-constrained optimization. J. Glob. Optim. 67, 59–77 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  31. Puranik, Y., Sahinidis, N.V.: Domain reduction techniques for global NLP and MINLP optimization. Constraints 22, 338–376 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  32. Rios, L.M., Sahinidis, N.V.: Derivative-free optimization: a review of algorithms and comparison of software implementations. J. Glob. Optim. 56, 1247–1293 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  33. Ryoo, H.S., Sahinidis, N.V.: Global optimization of nonconvex NLPs and MINLPs with applications in process design. Comput. Chem. Eng. 19, 551–566 (1995)

    Article  Google Scholar 

  34. Ryoo, H.S., Sahinidis, N.V.: A branch-and-reduce approach to global optimization. J. Glob. Optim. 8, 107–139 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  35. Sahinidis, N.V.: BARON: a general purpose global optimization software package. J. Glob. Optim. 8, 201–205 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  36. Sahinidis, N.V.: Global optimization and constraint satisfaction: the branch-and-reduce approach. In: Bliek, C., Jermann, C., Neumaier, A. (eds.) Global Optimization and Constraint Satisfaction. Lecture Notes in Computer Science, vol. 2861, pp. 1–16. Springer, Berlin (2003)

    Chapter  Google Scholar 

  37. Sahinidis, N.V.: BARON 15.5.0: Global Optimization of Mixed-Integer Nonlinear Programs, User’s Manual (2015)

  38. Shectman, J.P., Sahinidis, N.V.: A finite algorithm for global minimization of separable concave programs. J. Glob. Optim. 12, 1–36 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  39. Spendley, W., Hext, G.R., Himsworth, F.R.: Sequential application for simplex designs in optimisation and evolutionary operation. Technometrics 4, 441–461 (1962)

    Article  MathSciNet  MATH  Google Scholar 

  40. Stewart, C.R.: Master’s thesis. Vriginia Commonwealth University, Richmond, VA (2010)

  41. Tawarmalani, M., Ahmed, S., Sahinidis, N.V.: Product disaggregation and relaxations of mixed-integer rational programs. Optim. Eng. 3, 281–303 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  42. Tawarmalani, M., Sahinidis, N.V.: Convex extensions and convex envelopes of l.s.c. functions. Math. Program. 93, 247–263 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  43. Tawarmalani, M., Sahinidis, N.V.: Global optimization of mixed-integer nonlinear programs: a theoretical and computational study. Math. Program. 99, 563–591 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  44. Tawarmalani, M., Sahinidis, N.V.: A polyhedral branch-and-cut approach to global optimization. Math. Program. 103, 225–249 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  45. Torczon, V.J.: On the convergence of pattern search algorithms. SIAM J. Optim. 7, 1–25 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  46. Vaz, A.I.F.: PSwarm Home Page. http://www.norg.uminho.pt/aivaz/pswarm/. Accessed 25 Feb 2018

  47. Vaz, A.I.F., Vicente, L.N.: A particle swarm pattern search method for bound constrained global optimization. J. Glob. Optim. 39, 197–219 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  48. Zorn, K., Sahinidis, N.V.: Global optimization of general nonconvex problems with intermediate bilinear substructures. Optim. Methods Softw. 29, 442–462 (2013)

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, USA

    Jianfeng Liu, Nikolaos Ploskas & Nikolaos V. Sahinidis

Authors
  1. Jianfeng Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nikolaos Ploskas
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Nikolaos V. Sahinidis
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Nikolaos V. Sahinidis.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Liu, J., Ploskas, N. & Sahinidis, N.V. Tuning BARON using derivative-free optimization algorithms. J Glob Optim 74, 611–637 (2019). https://doi.org/10.1007/s10898-018-0640-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-018-0640-3

Keywords