Reduced Cost Fixing for Maximum Satisfiability

Fahiem Bacchus, Antti Hyttinen, Matti Järvisalo, Paul SaikkoIJCAI 2018 · DOI

TL;DR

This paper introduces "reduced cost fixing," a technique from integer programming, to significantly speed up Maximum Satisfiability (MaxSAT) solvers. By leveraging linear programming relaxations, the authors show how to "fix" the status of soft clauses, effectively pruning the search space and achieving substantial performance gains on challenging MaxSAT instances.

What Problem Does This Paper Address?

Maximum Satisfiability (MaxSAT) is a crucial problem in optimization, aiming to find a truth assignment that maximizes the number of satisfied weighted clauses. Modern MaxSAT solvers often employ techniques from Boolean Satisfiability (SAT) and Integer Programming (IP). A recent trend involves integrating IP techniques into SAT-based MaxSAT solvers, particularly those using the "implicit hitting set" (IHS) approach. While IHS solvers are powerful, there's a continuous need to improve their efficiency. This paper addresses the challenge of further accelerating IHS-based MaxSAT solvers by exploring the application of a specific IP technique: reduced cost fixing.

Methods

The core contribution of this paper is the integration of reduced cost fixing into IHS-based MaxSAT solvers. Here's a breakdown of the approach:

  • Implicit Hitting Set (IHS) Framework: The paper builds upon the IHS paradigm, which iteratively finds unsatisfiable cores (sets of soft clauses that cannot be simultaneously satisfied) and then uses an IP solver to compute minimum-cost hitting sets (MCHS) for these cores. The optimal MaxSAT solution is found when the hitting set covers all cores.
  • Reduced Cost Fixing: This technique, borrowed from IP, leverages the linear programming (LP) relaxation of the MCHS problem. The LP solution provides a lower bound on the optimal cost. Reduced costs, derived from the LP's optimal basis, indicate the minimum increase in cost if a non-basic variable (representing a soft clause) is flipped from its current value (0 or 1).
  • Fixing Soft Clauses: If flipping a soft clause's status (from satisfied to falsified, or vice-versa) would increase the LP's lower bound beyond the current best-known upper bound for the MaxSAT problem, that soft clause can be "fixed." This means its status is permanently set, effectively hardening it (if it was a soft clause) or making it unfixable (if it was a hard clause). This process prunes the search space.
  • Bounds-Based IHS View: The authors present a bounds-based perspective on the IHS algorithm, explicitly tracking upper bounds (from feasible MaxSAT solutions) and lower bounds (from LP relaxations of MCHS). This view facilitates the integration of reduced cost fixing.
  • Modified IHS Algorithm: To obtain the necessary upper bounds for reduced cost fixing, the authors slightly modify the standard IHS algorithm. Instead of immediately computing an MCHS, they iteratively add cores to the hitting set and check satisfiability. The first satisfying assignment found provides an upper bound.

Datasets

The experiments were conducted on a comprehensive set of non-random instances collected from the MaxSAT Evaluation from 2008-2016, including additional submitted benchmarks. This resulted in 6290 instances (4361 unweighted, 1929 weighted). For longer runs, 507 unweighted instances with no hard clauses (MS instances) were omitted.

Key Insights and Ideas

  • Bridging IP and MaxSAT: The paper successfully demonstrates that established IP techniques like reduced cost fixing can be effectively adapted to significantly improve the performance of modern MaxSAT solvers, particularly those employing IHS.
  • Pruning by Fixing: Reduced cost fixing provides a principled way to "fix" the status of soft clauses. This isn't just about finding a better solution; it's about intelligently reducing the problem's complexity by eliminating large portions of the search space that cannot lead to an optimal solution.
  • LP Relaxation as a Powerful Tool: The LP relaxation of the MCHS problem is not just a source for lower bounds but also a rich source of information (reduced costs) that can guide the search more effectively than previously realized in this context.
  • Empirical Validation is Key: The paper strongly emphasizes the empirical benefits, showing that even though reduced cost fixing itself might take some time, the overall speedup on many instances is substantial, validating its practical utility.

Key Results

  • Significant Speedup: The integration of reduced cost fixing into the MaxHS solver resulted in considerable speedups. For instances where fixing took more than 10 seconds, it often paid off significantly.
  • Commonly Applied: Out of 6290 instances, reduced cost fixing was applied to 1266 instances, with 791 instances having 100 or more fixings. In some extreme cases, over a million soft clauses were fixed.
  • Performance on Hard Instances: For instances where fixing took between 10 and 100 seconds, the scatter plot clearly shows a significant speedup, indicating that the time spent on fixing was well worth it.
  • 5-Hour Performance: Under a 5-hour per-instance time limit, the histogram of speedup ratios clearly demonstrates the value of reduced cost fixing, showing a substantial improvement in solving times.

Limitations and Future Work

  • Instance-Specific Performance: While the technique shows significant speedups, it's not universally beneficial. A notable portion of instances (5024 out of 6290) had no soft clauses fixed, suggesting that the effectiveness of reduced cost fixing is instance-dependent.
  • Time Cost of Fixing: In some cases, reduced cost fixing itself can take a considerable amount of time (e.g., 214 seconds for one instance). While this was often outweighed by the overall speedup, it's a factor to consider.
  • Future Work: The paper suggests that further exploration of integrating IP techniques into IHS solvers is a promising direction. The authors' work lays the groundwork for investigating other IP-based heuristics and propagations within the MaxSAT context.

Summary updated

BibTeX
@inproceedings{bacchus2018reduced,
  author = {Fahiem Bacchus and Antti Hyttinen and Matti Järvisalo and Paul Saikko},
  title = {{Reduced Cost Fixing for Maximum Satisfiability}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/723},
}
Figure