A New Algorithm for Weighted Partial MaxSAT

Carlos Ansótegui, Maria Luisa Bonet, Jordi LevyAAAI 2010 · DOI

Abstract

Weighted Partial MaxSAT (WP-MaxSAT) is a critical optimization problem in automated reasoning, requiring solvers to satisfy all hard constraints while minimizing the total weight of falsified soft clauses. This paper introduces WPM2, a core-guided algorithm that addresses the "formula explosion" problem prevalent in earlier solvers. By using a single auxiliary variable per soft clause and managing optimization via pseudo-Boolean constraints, WPM2 maintains a compact formula. Experimental results from the MaxSAT Evaluation 2009 and the International Timetabling Competition 2007 demonstrate that WPM2 is exceptionally effective for hard industrial instances, often solving problems that other state-of-the-art solvers cannot.

Introduction

In Boolean Satisfiability (SAT), the goal is to determine if a formula can be made true. MaxSAT extends this to optimization: when a formula is unsatisfiable, the goal is to satisfy the maximum number of clauses. Weighted Partial MaxSAT further refines this by distinguishing between "hard" constraints (mandatory) and "soft" constraints (optional), where each soft constraint has an associated penalty weight for falsification.

While SAT solvers have seen massive performance gains in industrial applications, MaxSAT solvers have historically struggled with scalability. Many SAT-based MaxSAT solvers rely on "core-guided" search, which identifies unsatisfiable subsets of clauses (cores). However, these solvers often suffer from formula bloat, duplicating clauses or adding excessive variables with each new core discovered, eventually overwhelming the underlying SAT engine.

The WPM2 Algorithm

The WPM2 algorithm is designed to mitigate formula explosion by maintaining a sparse representation of the optimization problem. Its core strategy relies on three main components:

  1. Blocking Variables: Each soft clause $C_i$ is transformed into $C_i \lor b_i$, where $b_i$ is a unique "blocking variable." Setting $b_i$ to true satisfies the clause but incurs a cost equal to the clause's weight $w_i$.
  2. Pseudo-Boolean Constraints: WPM2 avoids clause duplication by using two sets of linear constraints: At-Least (AL) constraints, which force a minimum falsification weight based on identified cores, and At-Most (AM) constraints, which bound the maximum cost.
  3. Core-Guided Iteration: The solver iteratively calls a SAT engine. If the formula is unsatisfiable, the engine returns a core, which WPM2 uses to update the AL and AM sets, effectively refining the lower bound of the optimal solution.
The WPM2 algorithm pseudocode.

A key innovation in WPM2 is the newbound function. When a conflict is detected, the algorithm calculates the next mathematically possible cost level by solving a variation of the Subset Sum Problem. This allows the solver to "jump" through the search space more efficiently than solvers that increment costs by the smallest possible unit.

Experimental Evaluation

The authors benchmarked WPM2 against several leading solvers, including WPM1, WBO, and MiniMaxSat. The evaluation focused on two challenging datasets: the industrial category of the MaxSAT Evaluation 2009 and Track 3 of the International Timetabling Competition (ITC 2007).

Performance comparison of WPM2 against other solvers on industrial and timetabling benchmarks.

The results highlight WPM2's strength in handling complex, highly constrained problems. In the TimeTabling Competition, WPM2 dominated the field, solving several "comp" instances that remained out of reach for all other SAT-based and Branch-and-Bound solvers within the one-hour time limit. On the MaxSAT 2009 industrial benchmarks, WPM2 remained highly competitive, particularly as problem complexity increased.

Key Insights and Discussion

WPM2’s success stems from its efficiency through sparsity. By keeping the working formula size manageable and treating optimization as a global budgeting problem, it allows the SAT solver to focus on the logical structure of the problem rather than bookkeeping overhead.

However, the current implementation faces a bottleneck in system overhead. WPM2 relies on an external tool (minisat+) to translate pseudo-Boolean constraints into Conjunctive Normal Form (CNF). This process involves file-swapping and external calls, which adds significant latency, especially on easier problems that require many iterations.

Future work aims to integrate the pseudo-Boolean translation directly into the solver's core to eliminate this overhead. Additionally, researchers are exploring more sophisticated core extraction techniques to further reduce the number of iterations required to reach an optimal assignment.

Summary updated

BibTeX
@inproceedings{ansotegui2010new,
  author = {Carlos Ansótegui and Maria Luisa Bonet and Jordi Levy},
  title = {{A New Algorithm for Weighted Partial MaxSAT}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7545},
}

Loading related content...

Figure