TY - JOUR
T1 - Enhancing the normalized multiparametric disaggregation technique for mixed-integer quadratic programming
AU - Andrade, Tiago
AU - Oliveira, Fabricio
AU - Hamacher, Silvio
AU - Eberhard, Andrew
PY - 2019/4
Y1 - 2019/4
N2 - We propose methods for improving the relaxations obtained by the normalized multiparametric disaggregation technique (NMDT). These relaxations constitute a key component for some methods for solving nonconvex mixed-integer quadratically constrained quadratic programming (MIQCQP) problems. It is shown that these relaxations can be more efficiently formulated by significantly reducing the number of auxiliary variables (in particular, binary variables) and constraints. Moreover, a novel algorithm for solving MIQCQP problems is proposed. It can be applied using either its original NMDT or the proposed reformulation. Computational experiments are performed using both benchmark instances from the literature and randomly generated instances. The numerical results suggest that the proposed techniques can improve the quality of the relaxations.
AB - We propose methods for improving the relaxations obtained by the normalized multiparametric disaggregation technique (NMDT). These relaxations constitute a key component for some methods for solving nonconvex mixed-integer quadratically constrained quadratic programming (MIQCQP) problems. It is shown that these relaxations can be more efficiently formulated by significantly reducing the number of auxiliary variables (in particular, binary variables) and constraints. Moreover, a novel algorithm for solving MIQCQP problems is proposed. It can be applied using either its original NMDT or the proposed reformulation. Computational experiments are performed using both benchmark instances from the literature and randomly generated instances. The numerical results suggest that the proposed techniques can improve the quality of the relaxations.
KW - Convex relaxation
KW - McCormick envelopes
KW - Nonconvex mixed-integer quadratically constrained quadratic programs
KW - Normalized multiparametric disaggregation technique
UR - http://www.scopus.com/inward/record.url?scp=85058715282&partnerID=8YFLogxK
U2 - 10.1007/s10898-018-0728-9
DO - 10.1007/s10898-018-0728-9
M3 - Article
AN - SCOPUS:85058715282
SN - 0925-5001
VL - 73
SP - 701
EP - 722
JO - Journal of Global Optimization
JF - Journal of Global Optimization
IS - 4
ER -