Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

Global optimization of non-convex generalized disjunctive programs: a review on reformulations and relaxation techniques

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

Abstract

In this paper we present a review on the latest advances in logic-based solution methods for the global optimization of non-convex generalized disjunctive programs. Considering that the performance of these methods relies on the quality of the relaxations that can be generated, our focus is on the discussion of a general framework to find strong relaxations. We identify two main sources of non-convexities that any methodology to find relaxations should account for. Namely, the one arising from the non-convex functions and the one arising from the disjunctive set. We review the work that has been done on these two fronts with special emphasis on the latter. We then describe different logic-based optimization techniques that make use of the relaxation framework and its impact through a set of numerical examples typically encountered in Process Systems Engineering. Finally, we outline challenges and future lines of work in this area.

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

Similar content being viewed by others

References

  1. Al-Khayyal, F.A., Falk, J.E.: Jointly constrained biconvex programming. Math. Oper. Res. 8(2), 273–286 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  2. Anstreicher, K.M.: Semidefinite programming versus the reformulation-linearization technique for non-convex quadratically constrained quadratic programming. J. Glob. Optim. 43(2–3), 471–484 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  3. Balas, E.: Disjunctive Programming. Ann. Discret. Math. 5, 3–51 (1979)

    Article  MATH  Google Scholar 

  4. Balas, E.: Disjunctive programming and a hierarchy of relaxations for discrete optimization problems. SIAM J. Algebr. Discrete Methods 6, 466–486 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  5. Bergamini, M.L., Aguirre, P.A., Grossmann, I.E.: Logic-based outer approximation for globally optimal synthesis of process networks. Comput. Chem. Eng. 29(9), 1914–1933 (2005)

    Article  Google Scholar 

  6. Ceria, S., Soares, J.: Convex programming for disjunctive convex optimization. Math. Program. 86, 595–614 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  7. Floudas, C.A.: Deterministic Global Optimization: Theory Methods and Applications. Kluwer, Dordrecht (2000)

    Book  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  9. Galan, B., Grossmann, I.E.: Optimal design of distributed wastewater treatment networks. Ind. Eng. Chem. Res. 37, 4036–4048 (1998)

    Article  Google Scholar 

  10. Grossmann, I.E.: Review of non-linear mixed integer and disjunctive programming techiques for process systems engineering. Optim. Eng. 3, 227–252 (2002)

    Article  MathSciNet  Google Scholar 

  11. Grossmann, I.E., Lee, S.: Generalized convex disjunctive programming: nonlinear convex hull relaxation. Comput. Optim. Appl. 26, 83–100 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  12. Grossmann, I.E., Trespalacios, F.: Systematic modeling of discrete-continuous optimization models through generalized disjunctive programming. AIChE J. 59, 3276–3295 (2013)

    Article  Google Scholar 

  13. Horst, R., Tuy, H.: Global Optimization Deterministic Approaches, 3rd edn. Springer, Berlin (1996)

    Book  MATH  Google Scholar 

  14. Khajavirad, A., Sahinidis, N.V.: Convex envelopes generated from finitely many compact convex sets. Math. Program. 137(1), 371–408 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  15. Kocis, G.R., Grossmann, I.E.: Relaxation strategy for the structural optimization of process flow sheets. Ind. Eng. Chem. Res. 26, 1869 (1987)

    Article  Google Scholar 

  16. Lee, S., Grossmann, I.E.: New algorithms for nonlinear generalized disjunctive programming. Comput. Chem. Eng. 24, 2125–2141 (2000)

    Article  Google Scholar 

  17. Lee, S., Grossmann, I.E.: Global optimization of nonlinear generalized disjunctive programming with bilinear inequality constraints: application to process networks. Comput. Chem. Eng. 27, 1557–1575 (2003)

    Article  Google Scholar 

  18. Liberti, L., Pantelides, C.C.: An exact reformulation algorithm for large non-convex NLPs involving bilinear terms. J. Glob. Optim. 36(2), 161–189 (2006)

    Article  MATH  Google Scholar 

  19. McCormick, G.P.: Computability of global solutions to factorable nonconvex programs. Part I. Convex underestimating problems. Math. Program. 10, 146–175 (1976)

    Article  MATH  Google Scholar 

  20. Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley-Interscience, New York (1988)

    Book  MATH  Google Scholar 

  21. Quesada, I., Grossmann, I.E.: An LP/NLP based branch and bound algorithm for convex MINLP optimization problems. Comput. Chem. Eng. 16, 937–947 (1992)

    Article  Google Scholar 

  22. Raman, R., Grossmann, I.E.: Modelling and computational techniques for logic-based integer programming. Comput. Chem. Eng. 18, 563 (1994)

    Article  Google Scholar 

  23. Ruiz, J.P.: Thesis: Global optimization of nonconvex Generalized Disjunctive Programs. Carnegie Mellon University (2011)

  24. Ruiz, J.P., Grossmann, I.E.: Strengthening the lower bounds for bilinear and concave GDP problems. Comput. Chem. Eng. 34(3), 914–930 (2010)

    Article  Google Scholar 

  25. Ruiz, J.P., Grossmann, I.E.: Generalized disjunctive programming: a framework for formulation and alternative algorithms for MINLP optimization. IMA Vol. Math. Its Appl. 218, 93–115 (2012)

    MATH  Google Scholar 

  26. Ruiz, J.P., Grossmann, I.E.: A hierarchy of relaxations for nonlinear convex generalized disjunctive programming. Eur. J. Oper. Res. 218(1), 38–47 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  27. Ruiz, J.P., Grossmann, I.E.: Using redundancy to strengthen the relaxation for the global optimization of MINLP. Comput. Chem. Eng. 35(12), 2729–2740 (2011)

    Article  Google Scholar 

  28. Ruiz, J.P., Grossmann, I.E.: Exploiting vector space properties to strengthen the relaxation of bilinear programs arising in the global optimization of process networks. Optim. Lett. 5, 1–11 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  29. Ruiz, J.P., Grossmann, I.E.: Using convex nonlinear relaxations in the global optimization of nonconvex generalized disjunctive programs. Comput. Chem. Eng. 49, 70–84 (2013)

    Article  Google Scholar 

  30. Sawaya, N.: Thesis: Reformulations, relaxations and cutting planes for generalized disjunctive programming. Carnegie Mellon University (2006)

  31. Sherali, H.D., Alameddine, A.: A new reformulation linearization technique for bilinear programming problems. J. Glob. Optim. 2, 379–410 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  32. Stubbs, R., Mehrotra, S.: A branch-and-cut method for 0–1 mixed convex programming. Math. Program. 86(3), 515–532 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  33. Tawarmalani, M., Sahinidis, N.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming. Kluwer, Dordrecht (2002)

    Book  MATH  Google Scholar 

  34. Trespalacios, F., Grossmann, I.E.: Algorithmic approach for improved mixed-integer reformulations of convex generalized disjunctive programs. INFORMS J. Comput. 27(1), 59–74 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  35. Trespalacios, F., Grossmann, I.E.: Cutting planes for improved global logic-based outer approximation for the synthesis of process networks. Comput. Chem. Eng., Submitted for publication (2015)

  36. Turkay, M., Grossmann, I.E.: A logic-based outer-approximation algorithm for MINLP optimization of process flowsheets. Comput. Chem. Eng. 20, 959–978 (1996)

    Article  Google Scholar 

  37. Vecchietti, A., Lee, S., Grossmann, I.E.: Modeling of discrete/continuous optimization problems: characterization and formulation of disjunctions and their relaxations. Comput. Chem. Eng. 27, 433–448 (2003)

    Article  Google Scholar 

  38. Viswanathan, J., Grossmann, I.E.: A combined penalty function and outer-approximation method for MINLP optimization. Comput. Chem. Eng. 14, 769–782 (1990)

    Article  Google Scholar 

  39. Wicaksono, D.S., Karimi, I.A.: Piecewise MILP under- and overestimators for global optimization of bilinear programs. AICHE J. 54, 991–1008 (2008)

    Article  Google Scholar 

  40. Williams, H.P.: Mathematical Building in Mathematical Programming. Wiley, New York (1985)

    MATH  Google Scholar 

  41. Zamora, J.M., Grossmann, I.E.: A branch and bound algorithm for problems with concave univariate, bilinear and linear fractional terms. J. Glob. Optim. 14(3), 217–249 (1999)

    Article  MATH  Google Scholar 

Download references

Acknowledgments

The authors would like to acknowledge financial support from the National Science Foundation under Grant 601 OCI-0750826.

Author information

Authors and Affiliations

  1. Carnegie Mellon University, Pittsburgh, PA, USA

    Ignacio E. Grossmann

  2. Soteica Visual Mesa LLC, Austin, TX, USA

    Juan P. Ruiz

Authors
  1. Juan P. Ruiz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ignacio E. Grossmann
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ignacio E. Grossmann.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Ruiz, J.P., Grossmann, I.E. Global optimization of non-convex generalized disjunctive programs: a review on reformulations and relaxation techniques. J Glob Optim 67, 43–58 (2017). https://doi.org/10.1007/s10898-016-0401-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-016-0401-0

Keywords

Search

Navigation