Abstract
This paper proposes a new algorithm for solving MAX2SAT problems based on combining search methods with semidefinite programming approaches. Semidefinite programming techniques are well-known as a theoretical tool for approximating maximum satisfiability problems, but their application has traditionally been very limited by their speed and randomized nature. Our approach overcomes this difficulty by using a recent approach to low-rank semidefinite programming, specialized to work in an incremental fashion suitable for use in an exact search algorithm. The method can be used both within complete or incomplete solvers, and we demonstrate on a variety of problems from recent competitions. Our experiments show that the approach is faster (sometimes by orders of magnitude) than existing state-of-the-art complete and incomplete solvers, representing a substantial advance in search methods specialized for MAX2SAT problems.
Introduction
The Maximum Satisfiability (MAXSAT) problem is a fundamental challenge in combinatorial optimization. While the standard 2-SAT problem is solvable in polynomial time, MAX2SAT—where each clause contains at most two variables—is NP-complete. For decades, Semidefinite Programming (SDP) has been recognized as a powerful theoretical tool for approximating MAX2SAT. However, standard "interior point" methods for solving SDPs scale poorly ($O(n^6)$), making them computationally prohibitive for use within the thousands of nodes of a search tree. Consequently, modern solvers have largely relied on discrete search methods.
This work introduces MIXSAT, an algorithm that bridges this gap by utilizing a fast, low-rank SDP solver within a branch-and-bound search framework.
Methodology
The core of MIXSAT lies in three integrated components designed to make continuous optimization practical for discrete search:
- The Mixing Method: Instead of computationally heavy interior-point methods, MIXSAT employs a specialized block coordinate descent algorithm for low-rank SDPs. This "Mixing method" is highly efficient, requiring only $O(k \cdot \text{nnz})$ time per update, where $k$ is the rank and $nnz$ is the number of non-zero entries.
- Branch-and-Bound Framework: The SDP solver is embedded within a standard search tree. The SDP relaxation provides a high-quality lower bound that allows for effective pruning of the search space.
- Warm-starts and Dual Bounds: To minimize overhead, the solver is "warm-started" at each node using the solution from its parent. Furthermore, a valid dual bound is calculated using a simple update formula, often allowing for immediate pruning without executing the full SDP solver.
Experimental Evaluation
The authors evaluated MIXSAT against top-performing solvers from the MAXSAT 2016 Competition. The datasets included:
- Random MAX2SAT: 228 unweighted random instances.
- Crafted MAXCUT: 107 instances (MAXCUT reduces to MAX2SAT).
- Random MAX3SAT: 144 instances to test generalization to longer clauses.
Key Results
MIXSAT demonstrated significant performance gains over state-of-the-art solvers across multiple tracks. In the Complete Track, MIXSAT solved 169 out of 228 instances within a 30-minute limit, compared to 145 by the best competition solvers. In the Incomplete Track, MIXSAT was 8.72x faster on average at finding optimal solutions. Even on MAXCUT instances, optimal solutions were recovered 3x faster than specialized solvers.
Discussion and Conclusion
The success of MIXSAT proves that SDP relaxations are no longer "too slow" for exact solvers. By specializing the optimization method and leveraging warm-starts, the authors transformed a theoretical curiosity into a practical, state-of-the-art engine. While the relaxation is tightest for MAX2SAT, the method showed surprising robustness on MAX3SAT instances. Future work will focus on extending this approach to weighted clauses and larger-scale problems with millions of variables.
Summary updated