Within-problem Learning for Efficient Lower Bound Computation in Max-SAT Solving

Abstract

This paper focuses on improving branch-and-bound Max-SAT solvers by speeding up the lower bound computation. We notice that the existing propagation-based computing methods and the resolution-based computing methods, which have been studied intensively, both suffer from several drawbacks. In order to overcome these drawbacks, we propose a new method with a nice property that guarantees the increment of lower bounds. The new method exploits within-problem learning techniques. More specifically, at each branch point in the search-tree, the current node is enabled to inherit inconsistencies from its parent and learn information about effectiveness of the lower bound computing procedure from previous nodes. Furthermore, after branching on a new variable, the inconsistencies may shrink by applying unit propagation to them, and such process increases the probability of getting better lower bounds. We graft the new techniques into maxsatz and the experimental results demonstrate that the new solver outperforms the best state-of-the-art solvers on a wide range of instances including random and structured ones.