Notoriously hard (mixed-)binary QPs
- Author(s)
- Immanuel M. Bomze, Jianqiang Cheng, Peter J.C. Dickinson, Abdel Lisser, Jia Liu
- Abstract
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.
- Organisation(s)
- Department of Statistics and Operations Research, Research Network Data Science
- External organisation(s)
- University of Arizona, University of Twente, Université Paris XI - Paris-Sud, Xi'an Jiaotong University (XJTU)
- Journal
- Computational Management Science
- Volume
- 16
- Pages
- 593-619
- No. of pages
- 27
- ISSN
- 1619-697X
- DOI
- https://doi.org/10.1007/s10287-018-0337-6
- Publication date
- 01-2018
- Peer reviewed
- Yes
- Austrian Fields of Science 2012
- 101015 Operations research
- Keywords
- ASJC Scopus subject areas
- Management Information Systems, Information Systems
- Portal url
- https://ucris.univie.ac.at/portal/en/publications/notoriously-hard-mixedbinary-qps(c1a8deb2-acdc-4f87-a9b8-8636a3c3acc4).html