TY - JOUR
T1 - Notoriously hard (mixed-)binary QPs
T2 - empirical evidence on new completely positive approaches
AU - Bomze, Immanuel M.
AU - Cheng, Jianqiang
AU - Dickinson, Peter J.C.
AU - Lisser, Abdel
AU - Liu, Jia
N1 - Funding Information:
The authors would like to thank the handling Associate Editors and two anonymous referees for their very useful comments and suggestions which helped to improve our paper significantly. This research benefited from the support of the “FMJH Program Gaspard Monge in Optimization and Operations Research”, and from the support to this program by EDF. Peter J. C. Dickinson would like to gratefully acknowledge support from the Netherlands Organisation for Scientific Research (NWO) through Grant No. 613.009.021.
Publisher Copyright:
© 2018, Springer-Verlag GmbH Germany, part of Springer Nature.
PY - 2019/10/1
Y1 - 2019/10/1
N2 - By now, many copositive reformulations of mixed-binary QPs have been discussed, triggered by Burer’s seminal characterization from 2009. In conic optimization, it is very common to use approximation hierarchies based on positive-semidefinite (psd) matrices where the order increases with the level of the approximation. Our purpose is to keep the psd matrix orders relatively small to avoid memory size problems in interior point solvers. Based upon on a recent discussion on various variants of completely positive reformulations and their relaxations (Bomze et al. in Math Program 166(1–2):159–184, 2017), we here present a small study of the notoriously hard multidimensional quadratic knapsack problem and quadratic assignment problem. Our observations add some empirical evidence on performance differences among the above mentioned variants. We also propose an alternative approach using penalization of various classes of (aggregated) constraints, along with some theoretical convergence analysis. This approach is in some sense similar in spirit to the alternating projection method proposed in Burer (Math Program Comput 2:1–19, 2010) which completely avoids SDPs, but for which no convergence proof is available yet.
AB - By now, many copositive reformulations of mixed-binary QPs have been discussed, triggered by Burer’s seminal characterization from 2009. In conic optimization, it is very common to use approximation hierarchies based on positive-semidefinite (psd) matrices where the order increases with the level of the approximation. Our purpose is to keep the psd matrix orders relatively small to avoid memory size problems in interior point solvers. Based upon on a recent discussion on various variants of completely positive reformulations and their relaxations (Bomze et al. in Math Program 166(1–2):159–184, 2017), we here present a small study of the notoriously hard multidimensional quadratic knapsack problem and quadratic assignment problem. Our observations add some empirical evidence on performance differences among the above mentioned variants. We also propose an alternative approach using penalization of various classes of (aggregated) constraints, along with some theoretical convergence analysis. This approach is in some sense similar in spirit to the alternating projection method proposed in Burer (Math Program Comput 2:1–19, 2010) which completely avoids SDPs, but for which no convergence proof is available yet.
KW - Completely positive
KW - Copositivity
KW - Mul tidimensional knapsack problem
KW - Nonconvex optimization
KW - Nonlinear optimization
KW - Penalization method
KW - Quadratic assignment problem
KW - Quadratic optimization
KW - Reformulations
UR - http://www.scopus.com/inward/record.url?scp=85057297990&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85057297990&partnerID=8YFLogxK
U2 - 10.1007/s10287-018-0337-6
DO - 10.1007/s10287-018-0337-6
M3 - Article
AN - SCOPUS:85057297990
SN - 1619-697X
VL - 16
SP - 593
EP - 619
JO - Computational Management Science
JF - Computational Management Science
IS - 4
ER -