Cutting planes for semidefinite relaxations based on triangle-free subgraphs (Q279802)

It has been shown by \textit{S. Burer} [Math. Program. 120, No. 2 (A), 479--495 (2009; Zbl 1180.90234)] that every optimization problem with quadratic objective function, linear constraints and binary variables can be formulated as a linear problem over the completely positive cone. This problem is NP-hard (covering maximum clique) as is already the problem of checking whether a given matrix is completely positive. Replacing the completely positive cone by the cone of doubly non-negative matrices provides a relaxation of the problem and a bound on its optimal value. For an order of \(n\geq 5\), there are doubly non-negative matrices that are not completely positive, and the idea is to use cuts defined by copositive matrices to get a tighter relaxation. The authors show how to separate triangle-free, non-negative matrices from the completely positive cone. They illustrate their approach on stable set problems and compare their results with those obtained previously.