×

zbMATH — the first resource for mathematics

Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations. (English) Zbl 1257.90079
Summary: We propose a deterministic global optimization approach, whose novel contributions are rooted in the edge-concave and piecewise-linear underestimators, to address nonconvex mixed-integer quadratically-constrained quadratic programs (MIQCQP) to \({\epsilon}\)-global optimality. The facets of low-dimensional (\(n \leq 3\)) edge-concave aggregations dominating the termwise relaxation of MIQCQP are introduced at every node of a branch-and-bound tree. Concave multivariable terms and sparsely distributed bilinear terms that do not participate in connected edge-concave aggregations are addressed through piecewise-linear relaxations. Extensive computational studies are presented for point packing problems, standard and generalized pooling problems, and examples from GLOBALLib (Meeraus, Globallib. http://www.gamsworld.org/global/globallib.htm).

MSC:
90C26 Nonconvex programming, global optimization
90C20 Quadratic programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achterberg T., Koch T., Martin A.: Branching rules revisited. Oper. Res. Lett. 33(1), 42–54 (2005) · Zbl 1076.90037 · doi:10.1016/j.orl.2004.04.002
[2] Adhya N., Tawarmalani M., Sahinidis N.V.: A Lagrangian approach to the pooling problem. Ind. Eng. Chem. Res. 38(5), 1965–1972 (1999)
[3] Adjiman C.S., Androulakis I.P., Floudas C.A.: A global optimization method, \(\alpha\)BB, for general twice differentiable NLPs-II. Implementation and computional results. Comput. Chem. Eng. 22, 1159–1179 (1998) · doi:10.1016/S0098-1354(98)00218-X
[4] Adjiman C.S., Dallwig S., Floudas C.A., Neumaier A.: A global optimization method, \(\alpha\)BB, for general twice differentiable NLPs-I. Theoretical advances. Comput. Chem. Eng. 22, 1137–1158 (1998) · doi:10.1016/S0098-1354(98)00027-1
[5] Aggarwal A., Floudas C.A.: Synthesis of general distillation sequences–nonsharp separations. Comput. Chem. Eng. 14(6), 631–653 (1990) · doi:10.1016/0098-1354(90)87033-L
[6] Al-Khayyal F.A., Falk J.E.: Jointly constrained biconvex programming. Math. Oper. Res. 8(2), 273–286 (1983) · Zbl 0521.90087 · doi:10.1287/moor.8.2.273
[7] Anderson E., Bai Z., Bischof C., Blackford S., Demmel J., Dongarra J., Du Croz J., Greenbaum A., Hammarling S., McKenney A., Sorensen D.: LAPACK Users’ Guide. 3rd edn. Society for Industrial and Applied Mathematics, Philadelphia (1999) · Zbl 0934.65030
[8] Androulakis I.P., Maranas C.D., Floudas C.A.: \(\alpha\)BB: a global optimization method for general constrained nonconvex problems. J. Global Optim. 7, 337–363 (1995) · Zbl 0846.90087 · doi:10.1007/BF01099647
[9] Anstreicher K.M.: Semidefinite programming versus the reformulation–linearization technique for nonconvex quadratically constrained quadratic programming. J. Global Optim. 43(2–3), 471–484 (2009) · Zbl 1169.90425 · doi:10.1007/s10898-008-9372-0
[10] Anstreicher K.M., Burer S.: Computable representations for convex hulls of low-dimensional quadratic forms. Math. Program. 124(1–2), 33–43 (2010) · Zbl 1198.90311 · doi:10.1007/s10107-010-0355-9
[11] Audet C., Brimberg J., Hansen P., Le Digabel S., Mladenovic N.: Pooling problem: alternate formulations and solution methods. Manag. Sci. 50(6), 761–776 (2004) · Zbl 1232.90349 · doi:10.1287/mnsc.1030.0207
[12] Audet C., Hansen P., Jaumard B., Savard G.: A branch and cut algorithm for nonconvex quadratically constrained quadratic programming. Math. Program. 87(1), 131–152 (2000) · Zbl 0966.90057
[13] Bagajewicz M.: A review of recent design procedures for water networks in refineries and process plants. Comput. Chem. Eng. 24, 2093–2113 (2000) · doi:10.1016/S0098-1354(00)00579-2
[14] Bao, X., Sahinidis, N.V., Tawarmalani, M.: Semidefinite relaxations for quadratically constrained quadratic programming: a review and comparisons. Math. Program. doi: 10.1007/s10107-011-0462-2 · Zbl 1232.49035
[15] Bao X., Sahinidis N.V., Tawarmalani M.: Multiterm polyhedral relaxations for nonconvex, quadratically-constrained quadratic programs. Optim. Methods Softw. 24(4–5), 485–504 (2009) · Zbl 1179.90252 · doi:10.1080/10556780902883184
[16] Belotti P., Lee J., Liberti L., Margot F., Wächter A.: Branching and bounds tightening techniques for non-convex MINLP. Optim. Methods Softw. 24(4–5), 597–634 (2009) · Zbl 1179.90237 · doi:10.1080/10556780903087124
[17] Ben-Tal A., Eiger G., Gershovitz V.: Global minimization by reducing the duality gap. Math. Program. 63, 193–212 (1994) · Zbl 0807.90101 · doi:10.1007/BF01582066
[18] Bergamini M.L., Grossmann I., Scenna N., Aguirre P.: An improved piecewise outer-approximation algorithm for the global optimization of MINLP models involving concave and bilinear terms. Comput. Chem. Eng. 32(3), 477–493 (2008) · doi:10.1016/j.compchemeng.2007.03.011
[19] Brimberg J., Hansen P., Mladenovic N.: A note on reduction of quadratic and bilinear programs with equality constraints. J. Global Optim. 22(1–4), 39–47 (2002) · Zbl 1045.90043 · doi:10.1023/A:1013838625301
[20] Brooke, A., Kendrick, D., Meeraus, A.: General algebraic modeling language (GAMS) 2011, version 23.6. http://www.gams.com/
[21] Burer S., Letchford A.N.: On nonconvex quadratic programming with box constraints. SIAM J. Optim. 20(2), 1073–1089 (2009) · Zbl 1201.90146 · doi:10.1137/080729529
[22] Burer S., Vandenbussche D.: A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Math. Program. 113(2), 259–282 (2008) · Zbl 1135.90034 · doi:10.1007/s10107-006-0080-6
[23] Cambini S., Sodini C.: Decomposition methods for solving nonconvex quadratic programs via branch and bound. J. Global Optim. 33, 313–336 (2005) · Zbl 1093.90034 · doi:10.1007/s10898-004-6095-8
[24] Ciric A.R., Floudas C.A.: A retrofit approach for heat exchanger networks. Comput. Chem. Eng. 13(6), 703–715 (1989) · doi:10.1016/0098-1354(89)80008-0
[25] Dolan E.D., Moré J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[26] Faria D.C., Bagajewicz M.J.: On the appropriate modeling of process plant water systems. AIChE J. 56(3), 668–689 (2010)
[27] Floudas C.A.: Deterministic Global Optimization: Theory, Methods and Applications. Nonconvex Optimization and Its Applications. Kluwer Academic Publishers, Dordrecht (2000)
[28] Floudas C.A., Aggarwal A.: A decomposition strategy for global optimum search in the pooling problem. ORSA J. Comput. 2, 225–235 (1990) · Zbl 0755.90091 · doi:10.1287/ijoc.2.3.225
[29] Floudas C.A., Aggarwal A., Ciric A.R.: Global optimum search for nonconvex NLP and MINLP problems. Comput. Chem. Eng. 13(10), 1117–1132 (1989) · doi:10.1016/0098-1354(89)87016-4
[30] Floudas C.A., Akrotirianakis I.G., Caratzoulas S., Meyer C.A., Kallrath J.: Global optimization in the 21st century: advances and challenges. Comput. Chem. Eng. 29, 1185–1202 (2005) · doi:10.1016/j.compchemeng.2005.02.006
[31] Floudas C.A., Anastasiadis S.H.: Synthesis of distillation sequences with several multicomponent feed and product streams. Chem. Eng. Sci. 43(9), 2407–2419 (1988) · doi:10.1016/0009-2509(88)85175-3
[32] Floudas C.A., Gounaris C.E.: A review of recent advances in global optimization. J. Global Optim. 45(1), 3–38 (2009) · Zbl 1180.90245 · doi:10.1007/s10898-008-9332-8
[33] Floudas C.A., Grossmann I.E.: Synthesis of flexible heat-exchanger networks with uncertain flowrates and temperatures. Comput. Chem. Eng. 11(4), 319–336 (1987) · doi:10.1016/0098-1354(87)85014-7
[34] Floudas C.A., Pardalos P.M.: State-of-the-art in global optimization–computational methods and applications–preface. J. Global Optim. 7(2), 113 (1995) · Zbl 0843.00057 · doi:10.1007/BF01097056
[35] Floudas C.A., Pardalos P.M., Adjiman C.S., Esposito W.R., Gms Z.H., Harding S.T., Klepeis J.L., Meyer C.A., Schweiger C.A.: Handbook of Test Problems in Local and Global Optimization. Kluwer Academic Publishers, Dordrecht (1999) · Zbl 0943.90001
[36] Floudas C.A., Paules G.E.: A mixed-integer nonlinear programming formulation for the synthesis of heat-integrated distillation sequences. Comput. Chem. Eng. 12(6), 531–546 (1988) · doi:10.1016/0098-1354(88)87003-0
[37] Floudas C.A., Visweswaran V.: A global optimization algorithm (GOP) for certain classes of nonconvex NLPs: I. Theory. Comput. Chem. Eng. 14(12), 1397–1417 (1990) · doi:10.1016/0098-1354(90)80020-C
[38] Floudas C.A., Visweswaran V.: Primal-relaxed dual global optimization approach. J. Optim. Theory Appl. 78(2), 187–225 (1993) · Zbl 0796.90056 · doi:10.1007/BF00939667
[39] Gill, P.E., Murray, W., Saunders, M.A. SNOPT. 1999, version 5.3. http://www.sbsi-sol-optimize.com/asp/sol_product_snopt.htm
[40] 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) · doi:10.1021/ie8016048
[41] Hansen P., Jaumard B.: Reduction of indefinite quadratic programs to bilinear programs. J. Global Optim. 2, 41–60 (1992) · Zbl 0786.90050 · doi:10.1007/BF00121301
[42] Hasan M.M.F., Karimi I.A.: Piecewise linear relaxation of bilinear programs using bivariate partitioning. AIChE J. 56(7), 1880–1893 (2010) · doi:10.1002/aic.12109
[43] ILOG. CPLEX. 2009, version 11.1 http://www-01.ibm.com/software/integration/optimization/cplex-optimizer
[44] zowski J.: Review of water network design methods with literature annotations. Ind. Eng. Chem. Res. 49(10), 4475–4516 (2010) · doi:10.1021/ie901632w
[45] Karuppiah R., Grossmann I.E.: Global optimization for the synthesis of integrated water systems in chemical processes. Comput. Chem. Eng. 30, 650–673 (2006) · doi:10.1016/j.compchemeng.2005.11.005
[46] Keha A.B., de Farias I.R., Nemhauser G.L.: Models for representing piecewise linear cost functions. Oper. Res. Lett. 32(1), 44–48 (2004) · Zbl 1056.90107 · doi:10.1016/S0167-6377(03)00059-2
[47] Kokossis A.C., Floudas C.A.: Synthesis of isothermal reactor–separator–recycle systems. Chem. Eng. Sci. 46(5–6), 1361–1383 (1991) · doi:10.1016/0009-2509(91)85063-4
[48] Kokossis A.C., Floudas C.A.: Optimization of complex reactor networks–II. nonisothermal operation. Chem. Eng. Sci. 49(7), 1037–1051 (1994) · doi:10.1016/0009-2509(94)80010-3
[49] Liberti L., Pantelides C.C.: An exact reformulation algorithm for large nonconvex NLPs involving bilinear terms. J. Global Optim. 36(2), 161–189 (2006) · Zbl 1131.90045 · doi:10.1007/s10898-006-9005-4
[50] Lin X., Floudas C.A.: Design, synthesis and scheduling of multipurpose batch plants via an effective continuous-time formulation. Comput. Chem. Eng. 25(4–6), 665–674 (2001) · doi:10.1016/S0098-1354(01)00663-9
[51] Linderoth J.: A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs. Math. Program. 103(2), 251–282 (2005) · Zbl 1099.90039 · doi:10.1007/s10107-005-0582-7
[52] Lougee-Heimer R.: The common optimization interface for operations research: promoting open-source software in the operations research community. IBM J. Res. Dev. 47(1), 57–66 (2003) · Zbl 05420370 · doi:10.1147/rd.471.0057
[53] Maranas C.D., Floudas C.A.: Finding all solutions of nonlinearly constrained systems of equations. J. Global Optim. 7(2), 143–182 (1995) · Zbl 0841.90115 · doi:10.1007/BF01097059
[54] McCormick G.P.: Computability of global solutions to factorable nonconvex programs: part 1-convex underestimating problems. Math. Program. 10(1), 147–175 (1976) · Zbl 0349.90100 · doi:10.1007/BF01580665
[55] Meeraus, A.: Globallib. http://www.gamsworld.org/global/globallib.htm
[56] Meyer C.A., Floudas C.A.: Trilinear monomials with positive or negative domains: facets of the convex and concave envelopes. In: Floudas, C.A., Pardalos, P.M. (eds) Frontiers in Global Optimization, pp. 327–352. Kluwer Academic Publishers, Dordrecht (2003) · Zbl 1176.90469
[57] Meyer C.A., Floudas C.A.: Trilinear monomials with mixed sign domains: facets of the convex and concave envelopes. J. Global Optim. 29(2), 125–155 (2004) · Zbl 1085.90047 · doi:10.1023/B:JOGO.0000042112.72379.e6
[58] Meyer C.A., Floudas C.A.: Convex envelopes for edge-concave functions. Math. Program. 103(2), 207–224 (2005) · Zbl 1099.90045 · doi:10.1007/s10107-005-0580-9
[59] Meyer C.A., Floudas C.A.: Global optimization of a combinatorially complex generalized pooling problem. AIChE J. 52(3), 1027–1037 (2006) · doi:10.1002/aic.10717
[60] Misener R., Floudas C.A.: Advances for the pooling problem: modeling, global optimization, and computational studies. Appl. Comput. Math. 8(1), 3–22 (2009) · Zbl 1188.90287
[61] Misener R., Floudas C.A.: Global optimization of large-scale pooling problems: quadratically constrained MINLP models. Ind. Eng. Chem. Res. 49(11), 5424–5438 (2010) · doi:10.1021/ie100025e
[62] Misener, R., Floudas, C.A.: Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations, 2011. http://www.optimization-online.org/DB_HTML/2011/11/3240.html · Zbl 1257.90079
[63] Misener R., Gounaris C.E., Floudas C.A.: Global optimization of gas lifting operations: a comparative study of piecewise linear formulations. Ind. Eng. Chem. Res. 48(13), 6098–6104 (2009) · doi:10.1021/ie8012117
[64] Misener R., Gounaris C.E., Floudas C.A.: Mathematical modeling and global optimization of large-scale extended pooling problems with the (EPA) complex emissions constraints. Comput. Chem. Eng. 34(9), 1432–1456 (2010) · doi:10.1016/j.compchemeng.2010.02.014
[65] 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) · doi:10.1016/j.compchemeng.2011.01.026
[66] Pardalos P.M.: Global optimization algorithms for linearly constrained indefinite quadratic problems. Comput. Math. Appl. 21(6–7), 87–97 (1991) · Zbl 0733.90051 · doi:10.1016/0898-1221(91)90163-X
[67] Pham V., Laird C., El-Halwagi M.: Convex hull discretization approach to the global optimization of pooling problems. Ind. Eng. Chem. Res. 48, 1973–1979 (2009) · doi:10.1021/ie8003573
[68] Quesada I., Grossmann I.E.: Global optimization of bilinear process networks with multicomponent flows. Comput. Chem. Eng. 19, 1219–1242 (1995) · doi:10.1016/0098-1354(94)00123-5
[69] Rikun A.D.: A convex envelope formula for multilinear functions. J. Global Optim. 10, 425–437 (1997) · Zbl 0881.90099 · doi:10.1023/A:1008217604285
[70] Rosen J.B., Pardalos P.M.: Global minimization of large-scale constrained concave quadratic problems by separable programming. Math. Program. 34(2), 163–174 (1986) · Zbl 0597.90066 · doi:10.1007/BF01580581
[71] 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 (2011) · Zbl 1211.90186 · doi:10.1007/s11590-010-0228-4
[72] Saif Y., Elkamel A., Pritzker M.: Global optimization of reverse osmosis network for wastewater treatment and minimization. Ind. Eng. Chem. Res. 47(9), 3060–3070 (2008) · doi:10.1021/ie071316j
[73] Saxena, A., Bonami, P., Lee, J.: Convex relaxations of non-convex mixed integer quadratically constrained programs: projected formulations. Math. Program. doi: 0.1007/s10107-010-0340-3 · Zbl 1229.90144
[74] Saxena A., Bonami P., Lee J.: Convex relaxations of non-convex mixed integer quadratically constrained programs: extended formulations. Math. Program. 124(1–2), 383–411 (2010) · Zbl 1198.90330 · doi:10.1007/s10107-010-0371-9
[75] Sherali H.D.: On mixed-integer zero-one representations for separable lower-semicontinuous piecewise-linear functions. Oper. Res. Lett. 28(4), 155–160 (2001) · Zbl 0992.90049 · doi:10.1016/S0167-6377(01)00063-3
[76] Sherali H.D., Adams W.P.: A Reformulation–Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Nonconvex Optimization and Its Applications. Kluwer Academic Publishers, Dordrecht (1999) · Zbl 0926.90078
[77] Sherali H.D., Alameddine A.: A new reformulation–linearization technique for bilinear programming problems. J. Global Optim. 2, 379–410 (1992) · Zbl 0791.90056 · doi:10.1007/BF00122429
[78] Sherali H.D., Tuncbilek C.H.: A reformulation–convexification approach for solving nonconvex quadratic-programming problems. J. Global Optim. 7(1), 1–31 (1995) · Zbl 0844.90064 · doi:10.1007/BF01100203
[79] Sherali H.D., Tuncbilek C.H.: New reformulation linearization/convexification relaxations for univariate and multivariate polynomial programming problems. Oper. Res. Lett. 21(1), 1–9 (1997) · Zbl 0885.90105 · doi:10.1016/S0167-6377(97)00013-8
[80] Tardella F.: On a class of functions attaining their maximum at the vertices of a polyhedron. Discret. Appl. Math. 22, 191–195 (1988) · Zbl 0663.90068 · doi:10.1016/0166-218X(88)90093-5
[81] Tardella F.: On the existence of polyhedral convex envelopes. In: Floudas, C.A., Pardalos, P.M. (eds) Frontiers in Global Optimization, pp. 563–573. Kluwer Academic Publishers, Dordrecht (2003) · Zbl 1176.90473
[82] Tardella F.: Existence and sum decomposition of vertex polyhedral convex envelopes. Optim. Lett. 2, 363–375 (2008) · Zbl 1152.90614 · doi:10.1007/s11590-007-0065-2
[83] Tawarmalani M., Sahinidis N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Applications, Software, and Applications. Nonconvex Optimization and Its Applications. Kluwer Academic Publishers, Norwell (2002) · Zbl 1031.90022
[84] Vandenbussche D., Nemhauser G.L.: A branch-and-cut algorithm for nonconvex quadratic programs with box constraints. Math. Program. 102(3), 559–575 (2005a) · Zbl 1137.90010 · doi:10.1007/s10107-004-0550-7
[85] Vandenbussche D., Nemhauser G.L.: A polyhedral study of nonconvex quadratic programs with box constraints. Math. Program. 102(3), 531–557 (2005b) · Zbl 1137.90009 · doi:10.1007/s10107-004-0549-0
[86] Vielma J.P., Ahmed S., Nemhauser G.: Mixed-integer models for nonseparable piecewise-linear optimization: unifying framework and extensions. Oper. Res. 58(2), 303–315 (2010) · Zbl 1226.90046 · doi:10.1287/opre.1090.0721
[87] Vielma, J.P., Nemhauser, G.: Modeling disjunctive constraints with a logarithmic number of binary variables and constraints. Math. Program. 2010. doi: 10.1007/s10107-009-0295-4 · Zbl 1143.90384
[88] Vigerske, S.: COIN-OR/GAMSLinks, 2011. Trunk Revision 1026. https://projects.coin-or.org/GAMSlinks/
[89] Visweswaran V.: MINLP: applications in blending and pooling. In: Floudas, C.A., Pardalos, P.M. (eds.) Encyclopedia of Optimization, pp. 2114–2121. Springer, New York (2009)
[90] Visweswaran V., Floudas C.A.: A global optimization algorithm (GOP) for certain classes of nonconvex NLPs: II. Application of theory and test problems. Comput. Chem. Eng. 14(12), 1419–1434 (1990) · doi:10.1016/0098-1354(90)80021-3
[91] Visweswaran V., Floudas C.A.: New properties and computational improvement of the GOP algorithm for problems with quadratic objective functions and constraints. J. Global Optim. 3, 439–462 (1993) · Zbl 0795.90070 · doi:10.1007/BF01096414
[92] Wicaksono D.S., Karimi I.A.: Piecewise MILP under-and overestimators for global optimization of bilinear programs. AIChE J. 54(4), 991–1008 (2008) · doi:10.1002/aic.11425
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.