Relaxations of the satisfiability problem using semidefinite programming

DOI10.1023/A:1006362203438MaRDI QIDQ1977751zbMATH OpenOpenAlexFDO

Authors Hans van Maaren, Joost P. Warners, E. de Klerk

Publication date 26 July 2001

Published in Journal of Automated Reasoning (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/a:1006362203438

zbMATH Keywords

semidefinite programmingrelaxationsatisfiability problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Mechanization of proofs and logical operations (03B35)

Recommendations

• Relaxations of the satisfiability problem using semidefinite programming
• On semidefinite programming relaxations for the satisfiability problem
• An improved semidefinite programming relaxation for the satisfiability problem
• An extended semidefinite relaxation for satisfiability
• Semidefinite resolution and exactness of semidefinite relaxations for satisfiability
• Exploiting semidefinite relaxations in constraint programming
• On semidefinite programming relaxations of \((2+p)\)-SAT
• Semidefinite programming relaxations for semialgebraic problems
• Semidefinite relaxations for integer programming
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems

Cited in

(15)

• An extended semidefinite relaxation for satisfiability
• An improved semidefinite programming relaxation for the satisfiability problem
• On semidefinite programming relaxations of \((2+p)\)-SAT
• On semidefinite programming relaxations for the satisfiability problem
• Semidefinite resolution and exactness of semidefinite relaxations for satisfiability
• Semidefinite relaxations of dynamical programs under discrete constraints
• An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs
• Generalising unit-refutation completeness and SLUR via nested input resolution
• scientific article; zbMATH DE number 2159161 (Why is no real title available?)
• Semidefinite programming and constraint programming
• Relaxations of the satisfiability problem using semidefinite programming
• Semidefinite programming and its applications to NP problems
• Exploiting semidefinite relaxations in constraint programming
• scientific article; zbMATH DE number 6000615 (Why is no real title available?)
• On semidefinite least squares and minimal unsatisfiability

Describes a project that uses

Uses Software

• SeDuMi

This page was built for publication: Relaxations of the satisfiability problem using semidefinite programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1977751)