(135a) Global Optimization of Mixed-Integer Quadratically-Constrained Quadratic Programs (QCQP) Through Piecewise-Linear and Edge-Concave Relaxations

Nonconvex quadratically-constrained quadratic programs (nonconvex QCQP) and those admitting integer variables (MIQCQP), are ubiquitous in process systems applications including heat integration networks, separation systems, reactor networks, reactor-separator-recycle systems, and batch processes. Among these applications are the pooling problems, which represent the optimization challenge of maximizing profit subject to feedstock availability, intermediate storage capacity, demand, and product specification constraints [9, 17, 18, 19]. The pooling problem, which is a MIQCQP, has important practical applications to many process systems engineering domains, including petroleum refining, water systems, supply-chain operations, and communications [4, 11, 16, 26].

We previously addressed large-scale pooling problems to ε-global optimality using a disjunctive relaxation formulation that activates appropriate under- and overestimators in specific domain segments and integrated this relaxation scheme into a branch-and-bound global optimization algorithm. Similar underestimators have been exploited in an array of process network applications [7, 10, 12, 13, 15, 20, 21, 27]. Here we address generic MIQCQP by extending these results beyond the special structure of MIQCQP representing process network problems. Because there is an inherent trade-off between relaxation tightness and solving time, we seek to elucidate the conditions under which these relaxations offer an advantage over the commonly-used termwise hull relaxation.

Complementing the piecewise-linear relaxations, we investigate polyhedral facets generated through edge-concave aggregations [2, 5, 8, 14, 23, 24, 25]. Edge-concave functions admit a vertex polyhedral envelope and therefore have a convex hull consisting entirely of linear facets [14, 23, 24, 25]. We detect possible low-dimensional (n ≤ 3) edge-concave aggregations of two or three variables in MIQCQP, determine the convex hull of the aggregated terms, and integrate facets that strictly dominate the termwise relaxation into our underestimation scheme at every node of a branch-and-bound tree. The facets that do not strictly dominate the termwise relaxation are still useful for bounds reduction within the context of branch-and-bound global optimization.

The proposed global optimization approach, whose novel contributions are rooted in the underestimators, determines an appropriate relaxation scheme employing piecewise linear underestimators and edge-concave relaxations and integrates the resulting mixed-integer linear program (MILP) into a branch-and-bound global optimization algorithm. We also incorporate standard techniques such as Reformulation-Linearization Technique feasibility-based range reduction [3, 22], limited optimality-based bounds tightening, and reliability branching [1, 6]. Extensive computational studies are presented for point packing problems, quadratic programming problems, and standard and generalized pooling problems.

[1] T. Achterberg, T. Koch, and A. Martin. Branching rules revisited. Oper. Res. Lett., 33(1):42–54, 2005. 

[2] K. M. Anstreicher and S. Burer. Computable representations for convex hulls of low-dimensional quadratic forms. Math. Program., 124 (12):33–43, 2010. 

[3] C. Audet, P. Hansen, B. Jaumard, and G. Savard. A branch and cut algorithm for nonconvex quadratically constrained quadratic programming. Math. Program., 87(1):131 – 152, 2000. 

[4] M. Bagajewicz. A review of recent design procedures for water networks in refineries and process plants. Comput. Chem. Eng., 24:2093-2113, 2000.

[5] X. Bao, N. V. Sahinidis, and M. Tawarmalani. Multiterm polyhedral relaxations for nonconvex, quadratically-constrained quadratic programs. Optimization Methods and Software, 24(4-5):485 – 504, 2009.

[6] P. Belotti, J. Lee, L. Liberti, F. Margot, and A. Wachter. Branching and bounds tightening techniques for non-convex MINLP. Optimization Methods and Software, 24(4-5):597–634, 2009.

[7] M. L. Bergamini, I. Grossmann, N. Scenna, and P. Aguirre. 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.

[8] S. Burer and A. N. Letchford. On nonconvex quadratic programming with box constraints. SIAM J. Optim., 20(2):1073–1089, 2009.

[9] C. E. Gounaris, R. Misener, and C. A. Floudas. Computational comparison of piecewise-linear relax- ations for pooling problems. Ind. Eng. Chem. Res., 48(12):5742 – 5766, 2009.

[10] M. M. F. Hasan and I. A. Karimi. Piecewise linear relaxation of bilinear programs using bivariate partitioning. AIChE J., 56(7):1880 – 1893, 2010.

[11] J. Jezowski. Review of water network design methods with literature annotations. Ind. Eng. Chem. Res., 49(10):4475 – 4516, 2010.

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

[13] J. Li, R. Misener, and C. A. Floudas. Continuous-time modeling and global optimization approach for scheduling of crude oil operations. AIChE Journal, 2011. In Press.

[14] C. A. Meyer and C. A. Floudas. Convex envelopes for edge-concave functions. Math. Program., 103(2):207–224, 2005.

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

[16] R. Misener and C. A. Floudas. Advances for the pooling problem: Modeling, global optimization, and computational studies. Applied and Computational Mathematics, 8(1):3 – 22, 2009.

[17] R. Misener and C. A. Floudas. Global optimization of large-scale pooling problems: Quadratically constrained MINLP models. Ind. Eng. Chem. Res., 49(11):5424 – 5438, 2010.

[18] R. Misener, C. E. Gounaris, and C. A. Floudas. 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.

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

[20] V. Pham, C. Laird, and M. El-Halwagi. Convex hull discretization approach to the global optimization of pooling problems. Ind. Eng. Chem. Res., 48:1973 – 1979, 2009.

[21] Y. Saif, A. Elkamel, and M. Pritzker. Global optimization of reverse osmosis network for wastewater treatment and minimization. Ind. Eng. Chem. Res., 47(9):3060 – 3070, 2008.

[22] H. D. Sherali and C. H. Tuncbilek. New reformulation linearization/convexification relaxations for univariate and multivariate polynomial programming problems. Oper. Res. Letters, 21(1):1 – 9, 1997.

[23] F. Tardella. On a class of functions attaining their maximum at the vertices of a polyhedron. Discret. Appl. Math., 22:191–195, 1988/89.

[24] F. Tardella. On the existence of polyhedral convex envelopes. In C. A. Floudas and P. M. Pardalos, editors, Frontiers in Global Optimization, pages 563–573. Kluwer Academic Publishers, 2003.

[25] F. Tardella. Existence and sum decomposition of vertex polyhedral convex envelopes. Optim. Lett., 2:363–375, 2008.

[26] V. Visweswaran. MINLP: Applications in blending and pooling. In C. A. Floudas and P. M. Pardalos, editors, Encyclopedia of Optimization, pages 2114 – 2121. Springer Science, 2 edition, 2009.

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