Anytime Cooperative Implicit Hitting Set Solving
This work addresses optimization in constraint satisfaction for researchers and practitioners, but it is incremental as it builds on existing Implicit Hitting Set methods.
The paper tackled the problem of improving anytime performance in solving Weighted CSP by combining lower-bound and upper-bound Implicit Hitting Set approaches in a multithreaded architecture, resulting in an algorithm (HS-lub) that consistently outperforms the individual components and sometimes beats the state-of-the-art Toulbar2 on benchmarks.
The Implicit Hitting Set (HS) approach has shown to be very effective for MaxSAT, Pseudo-boolean optimization and other boolean frameworks. Very recently, it has also shown its potential in the very similar Weighted CSP framework by means of the so-called cost-function merging. The original formulation of the HS approach focuses on obtaining increasingly better lower bounds (HS-lb). However, and as shown for Pseudo-Boolean Optimization, this approach can also be adapted to compute increasingly better upper bounds (HS-ub). In this paper we consider both HS approaches and show how they can be easily combined in a multithread architecture where cores discovered by either component are available by the other which, interestingly, generates synergy between them. We show that the resulting algorithm (HS-lub) is consistently superior to either HS-lb and HS-ub in isolation. Most importantly, HS-lub has an effective anytime behaviour with which the optimality gap is reduced during the execution. We tested our approach on the Weighted CSP framework and show on three different benchmarks that our very simple implementation sometimes outperforms the parallel hybrid best-first search implementation of the far more developed state-of-the-art Toulbar2.