Optimization Online


Semidefinite Optimization Approaches for Satisfiability and Maximum-Satisfiability Problems

Miguel F. Anjos (anjos***at***stanfordalumni.org)

Abstract: Semidefinite optimization, commonly referred to as semidefinite programming, has been a remarkably active area of research in optimization during the last decade. For combinatorial problems in particular, semidefinite programming has had a truly significant impact. This paper surveys some of the results obtained in the application of semidefinite programming to satisfiability and maximum-satisfiability problems. The approaches presented in some detail include the ground-breaking approximation algorithm of Goemans and Williamson for MAX-2-SAT, the Gap relaxation of de Klerk, van Maaren and Warners, and strengthenings of the Gap relaxation based on the Lasserre hierarchy of semidefinite liftings for polynomial optimization problems. We include theoretical and computational comparisons of the aforementioned semidefinite relaxations for the special case of 3-SAT, and conclude with a review of the most recent results in the application of semidefinite programming to SAT and MAX-SAT.

Keywords: satisfiability, maximum-satisfiability, semidefinite programming,semidefinite optimization, approximation algorithms, semidefinite relaxations,lifting procedures.

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Combinatorial Optimization

Citation: Journal on Satisfiability, Boolean Modeling and Computation, Vol. 1, 2005, 1-47. http://www.isa.ewi.tudelft.nl/Jsat/

Download: [PDF]

Entry Submitted: 09/08/2005
Entry Accepted: 09/08/2005
Entry Last Modified: 09/08/2005

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society