(253a) Enhancing Relaxations for Nonconvex Mixed-Integer Quadratically-Constrained Quadratic Programs

Enhancing Relaxations for Nonconvex Mixed-Integer Quadratically Constrained Quadratic Programs

Mixed-integer quadratically-constrained quadratic programs (MIQCQPs), and related classes of problems such as quadratically-constrained quadratic programs (QCQPs) and quadratic programs (QPs) arise in a wide variety of engineering and scientific applications including pooling and blending in process networks [12], facility location [23], production planning [8], quadratic assignment [9] and portfolio optimization [15]. Due to their practical importance, these classes of problems have been extensively studied in the mathematical programming literature. They are typically solved using spatial branch-and-bound algorithms, whose efficiency primarily depends on the quality of the relaxations constructed to bound the problem.

Commonly used relaxations for these type of problems can be classified into four groups. The first group involves relaxations obtained via standard factorable programming techniques whereby each quadratic function is decomposed iteratively by introducing intermediate variables and constraints for each nonconvex term, until each intermediate expression can be outer-approximated by its convex and/or concave envelopes [10, 20, 22]. While these techniques are relatively simple to implement, they typically result in large relaxation gaps. The second group is given by semi-definite programming (SDP) relaxations. This approach has received significant attention in recent years [1, 5, 6, 21]. While SDP relaxations often provide strong bounds, they are computationally expensive to solve, which limits their use within general purpose branch-and-bound global solvers. The third group relies on the reformulation-linearization techniques (RLT) [17–19]. Though these techniques typically yield tight bounds, the resulting relaxations grow quickly in size, and thus can become expensive to solve. The fourth group consists of factorable relaxations augmented by adding various classes of valid inequalities such as SDP-based cuts [7, 16], RTL-based cuts [24, 25], facets of the envelopes of edge-concave and multilinear subexpressions [2, 3, 11, 13], and mixed-integer cuts [4]. These augmented relaxations provide stronger bounds than standard factorable relaxations while remaining computationally inexpensive to solve. Due to its practicality, this class of relaxations is employed in most general-purpose global optimization packages.

In this work, we show how certain facets of the Boolean Quadric Polytope [14] can be utilized in order to enhance factorable relaxations of MIQCQPs constructed by global optimization solvers. To illustrate the benefits of this approach, we propose a computational implementation which integrates these facets as cutting planes into the branch-and-reduce global solver BARON. Our implementation consists of several algorithmic developments including tools for the identification of substructures in a graph representation of the problem, as well as efficient cut generation and separation algorithms which are embedded at every node of the branch-and-bound tree. We demonstrate the impact of the proposed implementation by conducting an extensive computational study on a large collection of problems selected from publicly available test sets.

References:

[1] Anstreicher, K. M., Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming, Journal of Global Optimization, 43:471–484, 2009.

[2] Bao, X., Khajavirad, A., Sahinidis, N.V., and Tawarmalani, M., Global optimization of nonconvex problems with multilinear intermediates. Mathematical Programming Computation, 7:1–37, 2015.

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

[4] Bonami, P., Günlük, O., and Linderoth, J. Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods, Mathematical Programming Computation, 2018, https://doi.org/10.1007/s12532-018-0133-x

[5] Buchheim, C. and Wiegele, A. Semidefinite relaxations for non-convex quadratic mixed-integer programming, Mathematical Programming, 141:435–452, 2013.

[6] Burer, S., Vandenbussche, D., A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Mathematical Programming, 112:259–282, 2008.

[7] Dong, H., Relaxing nonconvex quadratic functions by multiple adaptive diagonal perturbations. SIAM Journal on Optimization, 26:1962–1985, 2016.

[8] Liu, M.L. and Sahinidis, N.V., Process planning in a fuzzy environment, European Journal of Operational Research, 100:142–169, 1997.

[9] Loiola, E.M., De Abreu, N.M.M., Boaventura-Netto, P.O., Hahn, P., and Querido, T., A survey for the quadratic assignment problem, European Journal of Operational Research, 176:657–690, 2007.

[10] McCormick, G. P., Computability of global solutions to factorable nonconvex programs: Part I—Convex underestimating problems, Mathematical Programming, 10:147–175, 1976.

[11] Misener, R. and Floudas, C.A., Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations, Mathematical Programming, 136:155–182, 2012.

[12] Misener, R., Gounaris, C.E., and Floudas, C.A., Mathematical modeling and global optimization of large-scale extended pooling problems with the (EPA) complex emissions constraints, Computers and Chemical Engineering, 34:1432–1456, 2010.

[13] Misener, R., Smadbeck, J.B, and Floudas, C.A., Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2, Optimization Methods and Software, 30:215–249, 2015.

[14] Padberg, M. The boolean quadric polytope: Some characteristics, facets and relatives. Mathematical Programming, 45:139–172, 1989.

[15] Rios, L. and Sahinidis, N.V., Portfolio optimization for wealth-dependent risk preferences, Annals of Operations Research, 177:63–90, 2010.

[16] Saxena A., Bonami, P., and Lee, J., Convex relaxations of mixed integer quadratically constrained programs: Projected formulations, Mathematical Programming, 130:359–413, 2011.

[17] Sherali, H.D. and Adams, W.P., A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems, SIAM Journal on Discrete Mathematics, 3:411–430, 1990.

[18] Sherali, H.D., and Alameddine, A., A new reformulation-linearization technique for bilinear programming problems, Journal of Global Optimization, 2:379–410, 1992.

[19] Sherali, H.D. and Tuncbilek, C.H., A reformulation–convexification approach for solving nonconvex quadratic programming problems, Journal of Global Optimization, 7:1–31, 1995.

[20] Sherali, H. D. and Wang, H., Global optimization of nonconvex factorable programming problems, Mathematical Programming, 89:459–478, 2001.

[21] Shor, N.Z., Quadratic optimization problems, Soviet Journal of Computer and Systems Sciences, 25:1–11, 1987.

[22] Tawarmalani, M. and Sahinidis, N. V., Global optimization of mixed-integer nonlinear programs: A theoretical and computational study. Mathematical Programming, 99:563–591, 2004.

[23] Xie, W. and Sahinidis, N.V., A branch-and-bound algorithm for the continuous facility layout problem, Computers and Chemical Engineering, 32:1016–1028, 2008.

[24] Zorn, K. and Sahinidis, N.V., Global optimization of general non-convex problems with intermediate bilinear substructures, Optimization Methods and Software, 29:442–462, 2013.

[25] Zorn, K. and Sahinidis, N.V., Global optimization of general nonconvex problems with intermediate polynomial substructures, Journal of Global Optimization, 59:673–693, 2014.