Enhancements of discretization approaches for non-convex mixed-integer quadratically constrained quadratic programming: part II
本研究提出双重离散化归一化多参数分解技术（D-NMDT），用于求解非凸混合整数二次约束二次规划问题，理论分析和计算实验表明该方法能产生更紧的对偶界。
Abstract This is Part II of a study on mixed-integer programming (MIP) relaxation techniques for the solution of non-convex mixed-integer quadratically constrained quadratic programs (MIQCQPs). We set the focus on MIP relaxation methods for non-convex continuous variable products where both variables are bounded and extend the well-known MIP relaxation normalized multiparametric disaggregation technique (NMDT), applying a sophisticated discretization to both variables. We refer to this approach as doubly discretized normalized multiparametric disaggregation technique (D-NMDT). In a comprehensive theoretical analysis, we underline the theoretical advantages of the enhanced method D-NMDT compared to NMDT. Furthermore, we perform a broad computational study to demonstrate its effectiveness in terms of producing tight dual bounds for MIQCQPs. Finally, we compare D-NMDT to the separable MIP relaxations from Part I and a state-of-the-art MIQCQP solver.