TL;DR
This paper introduces SATLike, a novel dynamic local search algorithm for solving (Weighted) Partial MaxSAT (WPMS) problems. By cleverly adapting SAT local search techniques and introducing a new clause weighting scheme, SATLike significantly outperforms existing local search solvers and narrows the gap with state-of-the-art complete solvers on challenging industrial benchmarks.
What Problem Does This Paper Address?
The paper tackles the problem of solving (Weighted) Partial MaxSAT (WPMS). In essence, WPMS is about finding an assignment to Boolean variables that satisfies all "hard" constraints and maximizes the satisfaction of "soft" constraints, where soft constraints can have associated weights. This problem has broad applications, but existing solvers face challenges. While complete solvers have made strides, they can be slow on large, complex instances. Local search methods, which are often faster and more suitable for real-world scenarios where a good-enough solution is acceptable, have historically struggled with industrial WPMS benchmarks. Previous attempts to adapt local search for WPMS often involved complex, specialized heuristics for hard and soft clauses, or failed to fully leverage the power of techniques proven effective for standard SAT problems. The authors aim to bridge this gap by developing a local search solver that is both effective and simpler, by drawing inspiration from successful SAT local search algorithms.
Methods
The core innovation of this paper lies in the SATLike algorithm, which adapts dynamic local search techniques from SAT to the WPMS domain. Key components include:
- Dynamic Local Search Framework: SATLike operates within a standard local search paradigm, iteratively flipping variable assignments to improve the solution.
- Weighting-PMS Scheme: This is the paper's central contribution. It's a novel clause weighting mechanism that dynamically adjusts weights for both hard and soft clauses. Crucially, it applies a higher increment to falsified hard clauses to prioritize their satisfaction and imposes a limit on soft clause weights to prevent them from dominating the search. This scheme is designed to be simpler than previous specialized approaches.
- Variable Selection Heuristic: SATLike employs a two-mode strategy:
- If "decreasing" variables (those whose flip improves the solution) exist, it uses a probabilistic sampling method ("best from multiple selections" or BMS) to pick a high-scoring decreasing variable.
- If the search gets "stuck" (no improving flips), it first updates clause weights using Weighting-PMS and then selects a variable from a falsified clause (prioritizing hard clauses).
Datasets
The paper evaluates SATLike on benchmarks from the MaxSAT Evaluations (MSE) 2016 and 2017. These include:
- PMS benchmarks: Random, crafted, and industrial categories.
- WPMS benchmarks: Random, crafted, and industrial categories.
- The MSE 2017 merged PMS and WPMS categories into
PMS_2017andWPMS_2017benchmarks, respectively.
Key Insights and Ideas
- Leveraging SAT Techniques for WPMS: The paper demonstrates that standard local search techniques for SAT, when thoughtfully adapted, can be highly effective for WPMS, challenging the notion that WPMS requires fundamentally different, complex approaches.
- The Power of Dynamic Clause Weighting: The Weighting-PMS scheme is shown to be critical. By differentially weighting hard and soft clauses and capping soft clause weights, it effectively guides the search towards satisfying all hard constraints while still optimizing soft ones.
- Bridging the Local Search vs. Complete Solver Gap: SATLike significantly narrows the performance gap between local search and complete solvers on industrial WPMS instances, a long-standing challenge in the field.
- Complementarity of Approaches: For industrial benchmarks, SATLike is shown to be complementary to complete solvers, suggesting that hybrid approaches could be even more powerful.
Key Results
- Outperforming Local Search Solvers: SATLike significantly outperforms state-of-the-art local search solvers like Dist, DeciDist, CCEHC, and DeciCCEHC on both PMS and WPMS benchmarks, particularly on crafted and industrial instances. For instance, on WPMS industrial benchmarks, SATLike achieved approximately 5 times more winning instances than CCEHC and DeciCCEHC.
- Competitive with Complete Solvers: While complete solvers still hold an edge on some industrial benchmarks, SATLike achieves a substantial win rate (around 66-72% of the best complete solver's wins on industrial PMS/WPMS).
- Superior Performance on 2017 Benchmarks: SATLike demonstrates superior performance compared to complete solvers on the 2017 benchmarks, indicating its strong generalization capabilities.
- Effectiveness of Weighting-PMS: Experiments with alternative versions of SATLike (e.g., without soft clause weight limits) show that the proposed Weighting-PMS scheme is crucial for SATLike's success.
Limitations and Future Work
- Industrial Benchmark Gap: The authors acknowledge that SATLike still cannot fully compete with the best complete solvers on all industrial benchmarks, though it significantly narrows the gap.
- Future Work: The authors suggest exploring more advanced local search methods from SAT to further enhance their algorithm and propose that this work opens a new direction for efficiently solving structured WPMS instances.
Summary updated