Enhancements of Discretization Approaches for Non-Convex Mixed-Integer Quadratically Constraint Quadratic Programming

We study mixed-integer programming (MIP) relaxation techniques for the solution of non-convex mixed-integer quadratically constrained quadratic programs (MIQCQPs). We present two MIP relaxation methods for non-convex continuous variable products that enhance existing approaches. One is based on a separable reformulation, while the other extends the well-known MIP relaxation normalized multiparametric disaggregation technique (NMDT). In addition, we introduce a logarithmic MIP relaxation for univariate quadratic terms, called saw-tooth relaxation, based on [4]. We combine the latter with the separable reformulation to derive MIP relaxations of MIQCQPs.We provide a comprehensive theoretical analysis of these techniques and perform a broad computational study to demonstrate the effectiveness of the enhanced MIP relaxations in terms of producing tight dual bounds for MIQCQPs.

Citation

@article{barmann2022, title={Enhancements of Discretization Approaches for Non-Convex Mixed-Integer Quadratically Constraint Quadratic Programming}, author={B{\"a}rmann, Andreas and Beach, Benjamin and Burlacu, Robert and Hager, Lukas and Hildebrand, Robert}, year={2022} }

Article

Download

View Enhancements of Discretization Approaches for Non-Convex Mixed-Integer Quadratically Constraint Quadratic Programming