Notoriously hard (mixed-)binary QPs: empirical evidence on new completely positive approaches

Immanuel M. Bomze (), Jianqiang Cheng (), Peter J. C. Dickinson (), Abdel Lisser () and Jia Liu ()
Additional contact information
Immanuel M. Bomze: Universität Wien
Jianqiang Cheng: University of Arizona
Peter J. C. Dickinson: University of Twente
Abdel Lisser: Université Paris Sud - XI
Jia Liu: Xi’an Jiaotong University

Computational Management Science, 2019, vol. 16, issue 4, No 4, 593-619

Abstract: 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.

Keywords: Copositivity; Completely positive; Quadratic optimization; Reformulations; Nonlinear optimization; Nonconvex optimization; Penalization method; Quadratic assignment problem; Mul tidimensional knapsack problem; 90C20; 90C26; 90C30 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10287-018-0337-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:comgts:v:16:y:2019:i:4:d:10.1007_s10287-018-0337-6

Ordering information: This journal article can be ordered from
http://www.springer. ... ch/journal/10287/PS2

DOI: 10.1007/s10287-018-0337-6

Access Statistics for this article

Computational Management Science is currently edited by Ruediger Schultz

More articles in Computational Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().