On semidefinite programming relaxations for the satisfiability problem

DOI10.1007/s001860400377zbMath1087.90056OpenAlexW2089028944MaRDI QIDQ2386349

Miguel F. Anjos

Publication date: 22 August 2005

Published in: Mathematical Methods of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s001860400377

zbMATH Keywords

Global optimizationCombinatorial optimizationSemidefinite programmingSatisfiability problem

Mathematics Subject Classification ID

Semidefinite programming (90C22) Nonconvex programming, global optimization (90C26) Combinatorial optimization (90C27) Boolean programming (90C09)

Related Items

An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs, Semidefinite resolution and exactness of semidefinite relaxations for satisfiability, Partial Lagrangian relaxation for the unbalanced orthogonal Procrustes problem, Sums of squares based approximation algorithms for MAX-SAT, On semidefinite least squares and minimal unsatisfiability, A combinatorial approach to nonlocality and contextuality

Uses Software

• SDPT3
• PENNON
• COL