Global optimization of MIQCPs with dynamic piecewise relaxations

We propose a new deterministic global optimization algorithm for solving mixed-integer bilinear programs. It relies on a two-stage decomposition strategy featuring mixed-integer linear programming relaxations to compute estimates of the global optimum, and constrained non-linear versions of the original non-convex mixed-integer nonlinear program to find feasible solutions. As an alternative to spatial branch-and-bound with bilinear envelopes, we use extensively piecewise relaxations for computing estimates and reducing variable domain through optimality-based bound tightening. The novelty is that the number of partitions, a critical tuning parameter affecting the quality of the relaxation and computational time, increases and decreases dynamically based on the computational requirements of the previous iteration. Specifically, the algorithm alternates between piecewise McCormick and normalized multiparametric disaggregation. When solving ten benchmark problems from the literature, we obtain the same or better optimality gaps than two commercial global optimization solvers.