[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Global optimization of bilinear programs with a multiparametric disaggregation technique

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

Abstract

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 linear programs are derived using disjunctive programming and exact linearizations, and incorporated into two global optimization algorithms that are used to solve bilinear programming problems. The relaxation derived using the MDT is shown to scale much more favorably than the relaxation that relies on piecewise McCormick envelopes, yielding smaller mixed-integer problems and faster solution times for similar optimality gaps. The proposed relaxation also compares well with general global optimization solvers on large problems.

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
£29.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 includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

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

Similar content being viewed by others

References

  1. Misener, R., Thompson, J.P., Floudas, C.A.: APOGEE: global optimization of standard, generalized, and extended pooling problems via linear and logarithmic partitioning schemes. Comput. Chem. Eng. 35(5), 876–892 (2011)

    Article  Google Scholar 

  2. Misener, R., Floudas, C.A.: Advances for the pooling problem: modeling, global optimization, and computational studies. Appl. Comput. Math. 8(1), 3–22 (2009)

    Google Scholar 

  3. Bagajewicz, M.: A review of recent design procedures for water networks in refineries and process plants. Comput. Chem. Eng. 24(9–10), 2093–2113 (2000)

    Article  Google Scholar 

  4. Jeżowski, J.: Review of water network design methods with literature annotations. Ind. Eng. Chem. Res. 49(10), 4475–4516 (2010)

    Article  Google Scholar 

  5. Haverly, C.A.: Studies of the behavior of recursion for the pooling problem. SIGMAP Bull. 25, 19–28 (1978)

    Article  Google Scholar 

  6. Quesada, I., Grossmann, I.E.: Global optimization of bilinear process networks with multicomponent flows. Comput. Chem. Eng. 19(12), 1219–1242 (1995)

    Article  Google Scholar 

  7. Tawarmalani, M., Sahinidis, N. V.: Convexification and global optimization in continuous and mixed-integer nonlinear programming. Kluwer, Dordrecht, pp. 254–284 (2002)

  8. Meyer, C.A., Floudas, C.A.: Global optimization of a combinatorially complex generalized pooling problem. AIChE J. 52(3), 1027–1037 (2006)

    Article  Google Scholar 

  9. Misener, R., Floudas, C.A.: Global optimization of large-scale generalized pooling problems: quadratically constrained MINLP models. Ind. Eng. Chem. Res. 49(11), 5424–5438 (2010)

    Article  Google Scholar 

  10. Karuppiah, R., Grossmann, I.E.: Global optimization for the synthesis of integrated water systems in chemical processes. Comput. Chem. Eng. 30, 650–673 (2006)

    Article  Google Scholar 

  11. Teles, J.P., Castro, P.M., Matos, H.A.: Global optimization of water networks design using multiparametric disaggregation. Comput. Chem. Eng. 40, 132–147 (2012)

    Article  Google Scholar 

  12. Ahmetović, E., Grossmann, I.E.: Global superstructure optimization for the design of integrated process water networks. AIChE J. 57(2), 434–457 (2010)

    Article  Google Scholar 

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

    Article  Google Scholar 

  14. Liberti, L., Cafieri, S., Tarissan, F.: Reformulations in mathematical programming: a computational approach. In: Abraham, A., Hassanien, A., Siarry, P., Engelbrecht, A. (eds.) Foundations of Computational Intelligence, vol. 3, pp. 153–234. Springer, Heidelberg (2009)

    Google Scholar 

  15. Liberti, L., Pantelides, C.C.: An exact reformulation algorithm for large nonconvex NLPs involving bilinear terms. J. Glob. Optim. 36, 161 (2006)

    Article  Google Scholar 

  16. 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 (2011)

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Google Scholar 

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

    Book  Google Scholar 

  21. Floudas, C.A., Visweswaran, V.: Quadratic optimization. In: Horst, R., Pardalos, P.M. (eds.) Handbook of Global Optimization. Kluwer, Dordrecht (1995)

    Google Scholar 

  22. Shor, N.: Dual quadratic estimates in polynomial and Boolean programming. Ann. Oper. Res. 25(1), 163–168 (1990)

    Article  Google Scholar 

  23. Xu, H.K.: An iterative approach to quadratic optimization. J. Optim. Theory Appl. 116(3), 659–678 (2003)

    Article  Google Scholar 

  24. Yu, N.: Semidefinite relaxation and nonconvex quadratic optimization. Optim. Methods Softw. 9(1–3), 141–160 (1998)

    Google Scholar 

  25. Ye, Y.: Approximating quadratic programming with bound and quadratic constraints. Math. Program. 84(2), 219–226 (1999)

    Google Scholar 

  26. Adhya, N., Tawarmalani, M., Sahinidis, N.V.: A Lagrangian approach to the pooling problem. Ind. Eng. Chem. Res. 38(5), 1956–1972 (1999)

    Article  Google Scholar 

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

    Article  Google Scholar 

  28. Vielma, J.P., Ahmed, S., Nemhauser, G.: Mixed-integer models for nonseparable piecewise-linear optimization: unifying framework and extensions. Oper. Res. 58, 303–315 (2010)

    Article  Google Scholar 

  29. Vielma, J.P., Nemhauser, G.: Modeling disjunctive constraints with a logarithmic number of binary variables and constraints. Math. Program. (in press 2010). doi:10.1007/s10107-009-0295-4

  30. Teles, J.P., Castro, P.M., Matos, H.A.: Multiparametric disaggregation technique for global optimization of polynomial programming problems. J. Glob. Optim (2011). doi:10.1007/s10898-011-9809-8

  31. Grossmann, I.E., Ruiz, J.P.: Generalized disjunctive programming: a framework for formulation and alternative algorithms for MINLP optimization. In: Lee, J., Leyffer, S. (eds.) IMA Volume 154, Mixed Integer Nonlinear Programming (2011)

  32. Oral, M., Kettani, O.: A linearization procedure for quadratic and cubic mixed-integer problems. Oper. Res. 40(Suppl 1): S109–S116 (1992) (Optimization)

    Google Scholar 

  33. Balas, E.: Disjunctive programming and a hierarchy of relaxations for discrete optimization problems. SIAM J. Algebraic Discret. Math. 6, 466–486 (1985)

    Article  Google Scholar 

  34. Grossmann, I.E.: Review of nonlinear mixed-integer and disjunctive programming techniques. Optim. Eng. 3(3), 227–252 (2002)

    Article  Google Scholar 

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

    Article  Google Scholar 

  36. Gounaris, C.E., Misener, R., Floudas, C.A.: Computational comparison of piecewise-linear relaxations for pooling problems. Ind. Eng. Chem. Res. 48(12), 5742–5766 (2009)

    Article  Google Scholar 

  37. Quesada, I., Grossmann, I.E.: A global optimization algorithm for linear fractional and bilinear programs. J. Glob. Optim. 6(1), 39–76 (1995)

    Article  Google Scholar 

  38. Brook, A., Kendrick, D., Meeraus, A.: GAMS, a user’s guide. ACM SIGNUM Newslett. 23(3–4) (1988)

  39. IBM. IBM ILOG CPLEX V12.1—User’s Manual for CPLEX, IBM (2009)

  40. Drud, A.S.: CONOPT–A Large-Scale GRG Code. INFORMS J. Comput. 6(2), 207–216 (1994)

    Article  Google Scholar 

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

    Article  Google Scholar 

  42. Rijckaert, M., Martens, X.: Comparison of generalized geometric programming algoritms. J. Optim. Theory Appl. 26, 205 (1978)

    Article  Google Scholar 

  43. Hock, W., Schittkowski, K.: Test Examples for Nonlinear Programming Codes. Vol. 187 of Lecture Notes in Economics and Mathematical Systems. Springer, Berlin (1981)

  44. Shen, P., Zhang, K.: Global optimization of signomial geometric programming using linear relaxation. Appl. Math. Comput. 150(1), 99–114 (2004)

    Article  Google Scholar 

  45. Kolodziej, S.P.: Global Optimization of the Multiperiod Blend Problem. Master’s Thesis, Carnegie Mellon University, Pittsburgh (2012)

  46. Kolodziej, S.P., Grossmann, I.E., Furman, K.C., Sawaya, N.W.: A novel global optimization approach to the multiperiod blending problem (Submitted, 2012)

  47. Gurobi Optimizer Reference Manual Version 4.5. Gurobi Optimization. http://www.gurobi.com/doc/45/refman/ (2011)

  48. Sherali, H.D., Adams, W.P., Driscoll, P.J.: Exploiting special structures in constructing a hierarchy of relaxations for 0–1 mixed integer problems. Oper. Res. 46(3), 396–405 (1998)

    Article  Google Scholar 

  49. Misener R., Floudas, C.A.: Global mixed-integer quadratic optimizer. J. Glob. Optim (in press, 2012). DOI:10.1007/s10898-012-9874-7

Download references

Acknowledgments

Ignacio Grossmann and Scott Kolodziej acknowledge financial support from the National Science Foundation under Grant OCI-0750826. Pedro Castro gratefully acknowledges financial support from the Luso-American Foundation, under the 2011 Portugal-U.S. Research Networks Program.

Author information

Authors and Affiliations

  1. Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, PA, 15213-3890, USA

    Scott Kolodziej & Ignacio E. Grossmann

  2. Laboratório Nacional de Energia e Geologia, Unidade de Modelaçãoe Otimização de Sistemas Energéticos, 1649-038,  Lisbon, Portugal

    Pedro M. Castro

Authors
  1. Scott Kolodziej
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Pedro M. Castro
    View author publications

    You can also search for this author in PubMed Google Scholar

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

Cite this article

Kolodziej, S., Castro, P.M. & Grossmann, I.E. Global optimization of bilinear programs with a multiparametric disaggregation technique. J Glob Optim 57, 1039–1063 (2013). https://doi.org/10.1007/s10898-012-0022-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-012-0022-1

Keywords

Search

Navigation