Skip to main content
SpringerLink
Log in

An efficient strategy for the activation of MIP relaxations in a multicore global MINLP solver

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

Abstract

Solving mixed-integer nonlinear programming (MINLP) problems to optimality is a NP-hard problem, for which many deterministic global optimization algorithms and solvers have been recently developed. MINLPs can be relaxed in various ways, including via mixed-integer linear programming (MIP), nonlinear programming, and linear programming. There is a tradeoff between the quality of the bounds and CPU time requirements of these relaxations. Unfortunately, these tradeoffs are problem-dependent and cannot be predicted beforehand. This paper proposes a new dynamic strategy for activating and deactivating MIP relaxations in various stages of a branch-and-bound algorithm. The primary contribution of the proposed strategy is that it does not use meta-parameters, thus avoiding parameter tuning. Additionally, this paper proposes a strategy that capitalizes on the availability of parallel MIP solver technology to exploit multicore computing hardware while solving MINLPs. Computational tests for various benchmark libraries reveal that our MIP activation strategy works efficiently in single-core and multicore environments.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

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

Similar content being viewed by others

References

  1. Belotti, P., Lee, J., Liberti, L., Margot, F., Waechter, A.: Branching and bounds tightening techniques for non-convex MINLP. Optim. Methods Softw. 24, 597–634 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  2. 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 

  3. CMU-IBM cyber-infrastructure for MINLP collaborative site. www.minlp.org (2016). Accessed 27 Sept 2016

  4. Dolan, E., More, J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  5. FICO Xpress-optimizer reference manual, 20.0 edition. http://www.fico.com/xpress (2009). Accessed 27 Sept 2016

  6. Floudas, C.A., Gounaris, C.E.: A review of recent advances in global optimization. J. Glob. Optim. 45, 3–38 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  7. Goux, J.-P., Leyffer, S.: Solving large MINLPs on computational grids. Optim. Eng. 3, 327–346 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  8. Horst, R., Pardalos, P.M., Thoai, N.V.: Introduction to Global Optimization. Kluwer Academic Publishers, Dordrecht (1995)

    MATH  Google Scholar 

  9. Horst, R., Tuy, H.: Global Optimization: Deterministic Approaches, 2nd edn. Springer, Berlin (1993)

    Book  MATH  Google Scholar 

  10. International Business Machines Corporation. CPLEX User’s Manual V12.6. http://www.ibm.com/support/knowledgecenter/SSSA5P (2015). Accessed 27 Sept 2016

  11. Khajavirad, A., Sahinidis, N.V.: A hybrid LP/NLP paradigm for global optimization relaxations. Math. Program. Comput. (under review) (2017)

  12. Kılınç, M.R., Sahinidis, N.V.: Solving MINLPs with BARON, Mixed-Integer Nonlinear Programming Workshop Website. http://minlp.cheme.cmu.edu/2014/papers/kilinc.pdf (2014). Accessed 27 Sept 2016

  13. Koch, T., Achterberg, T., Andersen, E., Bastert, O., Berthold, T., Bixby, R.E., Danna, E., Gamrath, G., Gleixner, A.M., Heinz, S., Lodi, A., Mittelmann, H., Ralphs, T., Salvagnin, D., Steffy, D.E., Wolter, K.: MIPLIB 2010. Math. Program. Comput. 3, 103–163 (2011)

    Article  MathSciNet  Google Scholar 

  14. Lin, Y., Schrage, L.: The global solver in the LINDO API. Optim. Methods Softw. 24, 657–668 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  15. Misener, R., Floudas, C.A.: ANTIGONE: algorithms for continuous/integer global optimization of nonlinear equations. J. Glob. Optim. 59, 503–526 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  16. Pintér, J.D. (ed.): Global Optimization: Scientific and Engineering Case Studies, vol. 85. Springer, New York (2006)

    MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  18. 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 

  19. Sahinidis, N.V.: BARON Manual. BARON official website. http://www.minlp.com/downloads/docs/baron%20manual.pdf (2016). Accessed 26 Sept 2016

  20. 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 

  21. Shinano, Y., Achterberg, T., Berthold, T., Heinz, S., Koch, T.: ParaSCIP: A Parallel Extension of SCIP. Competence in High Performance Computing 2010, pp. 135–148. Springer, Berlin (2011)

    Book  Google Scholar 

  22. Smith, E.M., Pantelides, C.C.: Global optimisation of nonconvex MINLPs. Comput. Chem. Eng. 21, S791–S796 (1997)

    Article  Google Scholar 

  23. 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 

  24. Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications, Nonconvex Optimization and Its Applications, vol. 65. Kluwer Academic Publishers, Dordrecht (2002)

    MATH  Google Scholar 

  25. 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 

  26. 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 

  27. 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 

  28. Vigerske, S., Gleixner, A.: SCIP: global optimization of mixed-integer nonlinear programs in a branch-and-cut framework. Optim. Methods Softw. 1–31 (2017). doi:10.1080/10556788.2017.1335312

  29. Zhou, K., Chen, X., Shao, Z., Wan, W., Biegler, L.T.: Heterogeneous parallel method for mixed integer nonlinear programming. Comput. Chem. Eng. 66, 290–300 (2014)

    Article  Google Scholar 

Download references

Acknowledgements

We gratefully acknowledge the financial support of National Natural Science Foundation of China–Zhejiang Joint Fund for the Integration of Industrialization and Informatization (No. U1509209) and China Scholarship Council for the joint Ph.D. program.

Author information

Authors and Affiliations

  1. State Key Laboratory of Industrial Control Technology, College of Control Science and Engineering, Zhejiang University, Hangzhou, 310027, China

    Kai Zhou & Xi Chen

  2. Department of Chemical Engineering, Carnegie Mellon University, 5000 Forbes Ave., Pittsburgh, PA, 15213, USA

    Mustafa R. Kılınç & Nikolaos V. Sahinidis

Authors
  1. Kai Zhou
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mustafa R. Kılınç
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xi Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Nikolaos V. Sahinidis
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Xi Chen or Nikolaos V. Sahinidis.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zhou, K., Kılınç, M.R., Chen, X. et al. An efficient strategy for the activation of MIP relaxations in a multicore global MINLP solver. J Glob Optim 70, 497–516 (2018). https://doi.org/10.1007/s10898-017-0559-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-017-0559-0

Keywords

Search

Navigation