scientific article; zbMATH DE number 1795723
Semidefinite programming (SDF) relaxations -- in conjunction with randomized rounding schemes -- yield 7/8 and 0.931 approximation algorithms for MAX-3-SAT and MAX-2-SAT respectively. In spite of these powerful theoretical results, it is not clear if SDP can be used as a practical tool for solving MAX-SAT problems to optimality. In this regard, the usefulness of the SDP approach will ultimately depend on the ability to exploit sparsity in the SDP relaxations of large dimension. The authors present an investigation of sparsity issues for the SPD relaxations of Goemans and Williamson, and Feige and Goemans for MAX-2-SAT. Moreover, they test a branch and cut procedure to solve MAX-2-SAT to optimality, where the dual of the SDP relaxation is solved by interior point methods in order to exploit sparsity. Based on this numerical experience, the authors discuss possible extensions to MAX-3-SAT using the 7/8 relaxation of Karlow and Zwick for MAX-3-SAT. For the entire collection see [Zbl 0988.00046].
- Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
- Semidefinite optimization approaches for satisfiability and maximum-satisfiability problems
- On semidefinite programming relaxations for the satisfiability problem
- On semidefinite programming relaxations of \((2+p)\)-SAT
- An improved semidefinite programming relaxation for the satisfiability problem
- On semidefinite programming relaxations of \((2+p)\)-SAT
- Solving the weighted MAX-SAT problem using the dynamic convexized method
- Exact MAX-2SAT solution via lift-and-project closure
- Semidefinite programming and constraint programming
- Semidefinite optimization approaches for satisfiability and maximum-satisfiability problems
- Efficient branch-and-bound algorithms for weighted MAX-2-SAT
- Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
- A new bounding procedure and an improved exact algorithm for the Max-2-SAT problem
- An efficient solver for weighted Max-SAT
- Sums of squares based approximation algorithms for MAX-SAT
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4550772)
