(101b) SDP-Quality Bounds Via Convex Quadratic Relaxations for Global Optimization of Mixed-Integer Quadratic Programs

Nonconvex quadratic programs (QPs) and mixed-integer quadratic programs (MIQPs) arise in a wide variety of scientific and engineering applications including facility location [18], quadratic assignment [7], molecular conformation [10] and max-cut problems [6]. Given their practical importance, these classes of problems have been studied extensively in the literature and are known to be very challenging to solve to global optimality.

State-of-the-art global optimization solvers rely on spatial branch-and-bound methods to solve nonconvex QPs and MIQPs to global optimality. The efficiency of these algorithms depends to a large extent on the tightness and the computational cost of the relaxations solved for lower bounding. Tighter relaxations lead to tighter bounds, and often speed up convergence of the branch-and-bound algorithm. Commonly used relaxations for bounding nonconvex QPs and MIQPs can be broadly classified into three groups. The first group consists of polyhedral relaxations which are typically derived via factorable programming methods [8, 14, 16] and reformulation-linearization techniques (RLT) [11–13]. The second group is given by semidefinite programming (SDP) relaxations [1, 3, 4, 15]. The third group involves convex quadratic relaxations which can be obtained through different approaches including separable programming procedures [9], d.c. programming techniques [17], and quadratic convex reformulation methods [2].

In this talk, we consider a class of relaxations which falls under the third group. In particular, we introduce a new family of quadratically constrained programming (QCP) relaxations which are derived via convex quadratic cuts. In order to construct these quadratic cuts, we solve a separation problem involving a linear matrix inequality with a special structure that allows the use of specialized solution algorithms [5]. We investigate the theoretical properties of the proposed relaxations and show that they are an outer-approximation of a semi-infinite convex program which under certain conditions is equivalent to a particular semidefinite program. In order to assess the computational benefits of our approach, we implement the new quadratic relaxations in the global optimization solver BARON. We test our implementation by conducting an extensive computational study on a large collection of problems. Numerical results show that the new quadratic relaxations lead to a significant improvement in the performance of BARON, resulting in a new version of this solver which outperforms other state-of-the-art solvers such as CPLEX and GUROBI for many of our test problems.

[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] Billionnet, A., Elloumi, S. and Lambert, A. An efficient compact quadratic convex re-formulation for general integer quadratic programs. Computational Optimization and Applications, 54:141–162, 2013.

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

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

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

[6] Goemans, M. X. and Williamson, D. P. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of ACM, 42:1115–1145, 1995.

[7] 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.

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

[9] Pardalos, P.M., Glick, J.H. and Rosen, J.B. Global minimization of indefinite quadratic problems. Computing, 539:281–291, 1987.

[10] Phillips, A.T. and Rosen, J.B. A quadratic assignment formulation of the molecular conformation problem. Journal of Global Optimization, 4:229–241, 1994.

[11] 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.

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

[13] 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.

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

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

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

[17] Tuy, H. DC optimization: Theory, methods and algorithms. In R. Horst and P.M. Pardalos (eds.), Handbook of Global Optimization, Kluwer Academic Publishers, Boston, MA, 149–216, 1995.

[18] 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.