Copositivity cuts for improving SDP bounds on the clique number

DOI10.1007/s10107-010-0363-9zbMath1198.90312OpenAlexW2029500689MaRDI QIDQ2638373

Florian Frommlet, Immanuel M. Bomze, Marco Locatelli

Publication date: 16 September 2010

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-010-0363-9

zbMATH Keywords

semidefinite programmingmaximum clique problemLovász' bound

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Quadratic programming (90C20) Combinatorial optimization (90C27)

Related Items

Cutting planes for semidefinite relaxations based on triangle-free subgraphs, Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem, (Global) optimization: historical notes and recent developments, Approximation of the Shannon capacity via matrix cone programming, Separating doubly nonnegative and completely positive matrices, Copositive optimization -- recent developments and applications, Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization, Factorization and cutting planes for completely positive matrices by copositive projection, Globally Solving Nonconvex Quadratic Programs via Linear Integer Programming Techniques, Strengthening Chvátal-Gomory Cuts for the Stable Set Problem, Exploiting symmetry in copositive programs via semidefinite hierarchies

Uses Software

• CSDP
• YALMIP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Semidefinite programming relaxations for graph coloring and maximal clique problems
• New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability
• The sandwich theorem
• On the copositive representation of binary and continuous nonconvex quadratic programs
• Global Optimization with Polynomials and the Problem of Moments
• Approximation of the Stability Number of a Graph via Copositive Programming
• Gap, cosum and product properties of the θ′ bound on the clique number
• Semidefinite Bounds for the Stability Number of a Graph via Sums of Squares of Polynomials
• A comparison of the Delsarte and Lovász bounds
• On the Shannon capacity of a graph
• CSDP, A C library for semidefinite programming
• Computing the Stability Number of a Graph Via Linear and Semidefinite Programming