Cutting planes for semidefinite relaxations based on triangle-free subgraphs

DOI10.1007/s11590-015-0922-3zbMath1356.90116OpenAlexW2167764737MaRDI QIDQ279802

Mirjam Dür, Naomi Shaked-Monderer, Abraham Berman, Julia Sponsel

Publication date: 29 April 2016

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-015-0922-3

zbMATH Keywords

completely positive matricescopositive cutssemidefinite relaxation

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items

Triangle-free graphs and completely positive matrices

Cites Work

• Unnamed Item
• The extreme rays of the \(5 \times 5\) copositive cone
• On the computational complexity of membership problems for the completely positive cone and its dual
• Geometry of the copositive and completely positive cones
• The difference between \(5\times 5\) doubly nonnegative and completely positive matrices
• New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability
• Criteria for copositive matrices
• A test for copositive matrices
• On copositive matrices
• Separating doubly nonnegative and completely positive matrices
• Separation and relaxation for cones of quadratic forms
• On copositive matrices with -1, 9, 1 entries
• On the copositive representation of binary and continuous nonconvex quadratic programs
• Factorization and cutting planes for completely positive matrices by copositive projection
• Two remarks on copositive matrices
• On classes of copositive matrices
• Copositivity cuts for improving SDP bounds on the clique number
• Approximation of the Stability Number of a Graph via Copositive Programming
• Completely positive matrices associated withM-matrices
• Computing the Stability Number of a Graph Via Linear and Semidefinite Programming