article

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

Authors:

Ignacio E. GrossmannAuthors Info & Claims

Journal of Global Optimization, Volume 67, Issue 1-2

Pages 43 - 58

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

Published: 01 January 2017 Publication History

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.

References

[1]

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

[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)

Digital Library

[3]

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

[4]

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

[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)

[6]

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

[7]

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

Digital Library

[8]

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

Digital Library

[9]

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

[10]

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

[11]

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

Digital Library

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[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)

[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)

Digital Library

[19]

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

Digital Library

[20]

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

Digital Library

[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)

[22]

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

[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)

[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)

[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)

[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)

[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)

[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)

[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)

[32]

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

[33]

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

Digital Library

[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)

Digital Library

[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)

[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)

[38]

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

[39]

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

[40]

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

[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)

Digital Library

Cited By

Bernal Neira DGrossmann I(2024)Convex mixed-integer nonlinear programs derived from generalized disjunctive programming using conesComputational Optimization and Applications10.1007/s10589-024-00557-988:1(251-312)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1007/s10589-024-00557-9
Nagarajan HLu MWang SBent RSundar K(2022)An adaptive, multivariate partitioning algorithm for global optimization of nonconvex programsJournal of Global Optimization10.1007/s10898-018-00734-174:4(639-675)Online publication date: 10-Mar-2022
https://dl.acm.org/doi/10.1007/s10898-018-00734-1
Koehler JBürgler JFontana UFux EHerzog FPouly MSaller SSalyaeva AScheiblechner PWaelti K(2021)Cable tree wiring - benchmarking solvers on a real-world scheduling problem with a variety of precedence constraintsConstraints10.1007/s10601-021-09321-w26:1-4(56-106)Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.1007/s10601-021-09321-w
Show More Cited By

Global optimization of non-convex generalized disjunctive programs: a review on reformulations and relaxation techniques
1. Information systems
  1. Data management systems
    1. Database administration
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Generalized Convex Disjunctive Programming: Nonlinear Convex Hull Relaxation

Generalized Disjunctive Programming (GDP) has been introduced recently as an alternative to mixed-integer programming for representing discrete/continuous optimization problems. The basic idea of GDP consists of representing these problems in terms of ...
Global optimization of bilinear programs with a multiparametric disaggregation technique

In this paper, we present the derivation of the multiparametric disaggregation technique (MDT) by Teles et al. (J. Glob. Optim., 2011 ) for solving nonconvex bilinear programs. Both upper and lower bounding formulations corresponding to mixed-integer ...
Cutting Plane Algorithm for Convex Generalized Disjunctive Programs

In this work, we propose a cutting plane algorithm to improve optimization models that are originally formulated as convex generalized disjunctive programs. Generalized disjunctive programs are traditionally reformulated as mixed-integer nonlinear ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Global Optimization

Journal of Global Optimization Volume 67, Issue 1-2

January 2017

440 pages

ISSN:0925-5001

Issue’s Table of Contents

Copyright © Copyright © 2017 Springer Science+Business Media New York.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 January 2017

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 28 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bernal Neira DGrossmann I(2024)Convex mixed-integer nonlinear programs derived from generalized disjunctive programming using conesComputational Optimization and Applications10.1007/s10589-024-00557-988:1(251-312)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1007/s10589-024-00557-9
Nagarajan HLu MWang SBent RSundar K(2022)An adaptive, multivariate partitioning algorithm for global optimization of nonconvex programsJournal of Global Optimization10.1007/s10898-018-00734-174:4(639-675)Online publication date: 10-Mar-2022
https://dl.acm.org/doi/10.1007/s10898-018-00734-1
Koehler JBürgler JFontana UFux EHerzog FPouly MSaller SSalyaeva AScheiblechner PWaelti K(2021)Cable tree wiring - benchmarking solvers on a real-world scheduling problem with a variety of precedence constraintsConstraints10.1007/s10601-021-09321-w26:1-4(56-106)Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.1007/s10601-021-09321-w
Jornada DLeon V(2020)Filtering Algorithms for Biobjective Mixed Binary Linear Optimization Problems with a Multiple-Choice ConstraintINFORMS Journal on Computing10.1287/ijoc.2019.089132:1(57-73)Online publication date: 1-Jan-2020
https://dl.acm.org/doi/10.1287/ijoc.2019.0891
Lyu YChen LZhang CQu DMin-Allah NWang Y(2018)An interleaved depth-first search method for the linear optimization problem with disjunctive constraintsJournal of Global Optimization10.1007/s10898-017-0602-170:4(737-756)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1007/s10898-017-0602-1

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents