Global optimization algorithm for mixed integer quadratically constrained quadratic program

摘要

Mixed integer quadratic programs with quadratic constraints (MIQQP) occur frequently in various areas of engineering practice and management science, but most solution methods for this kind of problems are often designed for its special cases. In this paper, we present a simple global optimization algorithm for solving problem (MIQQP). We first convert problem (MIQQP) into an equivalent generalized bilinear programming problem with integer variables (EIQQP). We next show that replacing the quadratic objective and constraint functions with their convex envelopes is dominated by an alternative methodology based on convexifying the range of the bilinear terms on the feasible region. Finally, by incorporating the reduction-correction techniques and sampling strategies into the branch and bound scheme, the proposed algorithm is developed for solving (MIQQP). Convergence and optimality of the algorithm are presented and numerical examples taken from some recent literature and MINLPLib2 are carried out to validate the performance of the proposed algorithm.