On the copositive representation of binary and continuous nonconvex quadratic programs

By S. Burer. Mathematical programming, 2009

475 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/9fa3c06c3a0ef2d98e8c877a16fad9bd57243b99

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Networks and Communications

In Numerical Analysis

Citations in the corpus

The difference between 5×5 doubly nonnegative and completely positive matrices (2009, background): “Recently, it has attracted interest in optimization where it has been shown that NP-hard nonconvex quadratic programs, possibly also containing binary variables, may be reformulated as linear optimization problems over this cone [5].”
Mixed-integer nonlinear optimization*† (2013, methodology): “We refer the reader to the works of Tawarmalani and Sahinidis (2002) and Burer and Letchford (2012a) for additional surveys focused on nonconvex MINLP.”
Non-convex mixed-integer nonlinear programming: A survey (2012, methodology): “These include, for example, maximum cut (or binary quadratic programming (QP)) and its variants [39–41], clustering [42], non-convex QP with binary variables [43], quadratically constrained QP [44], the quadratic traveling salesman problem (TSP) [45], TSP with neighborhoods [46], and polynomial opti”
Geometry of the copositive and completely positive cones (2011, background): “It has been shown in [4] that if we consider the quadratic binary problem, where the symmetric matrix Q and the vectors c, a1, .”
Interior points of the completely positive cone. (2008, background): “Burer [ 4 ] showed the very general result that every quadratic problem with linear and binary constraints can be rewritten as such a problem.”
AN IMPROVED CHARACTERISATION OF THE INTERIOR OF THE COMPLETELY POSITIVE CONE (2010, background): “For example, it was shown by Bomze et al. [3] that the maximum clique problem can be reformulated as a linear optimisation problem over either the copositive or completely positive cone, and Burer [5] showed that every quadratic problem with linear and binary constraints can be rewritten in such a f”
Challenges and opportunities in quantum optimization (2023, unknown): “Finally, a mathematically elegant reformulation of an MIP problem results in a linear programme over the dual of the cone of copositive matrices 137 .”
An Exact Penalty Method for Binary Optimization Based on MPEC Formulation (2017, background): “completely positive relaxation (Burer, 2009) {0,+1}n ≈ {x |X xxT , diag(X) = x, x ≥ 0, X is CP}”
Copositive Programming – a Survey (2010, methodology): “The algorithm is not adequate for general models derived from Burer’s result [19], and provides only poor results for box-constrained quadratic problems.”