Empirical Evaluation of the Implicit Hitting Set Approach for Weighted CSPs
This work addresses the optimization of Weighted CSPs for researchers in constraint satisfaction, but it is incremental as it builds on existing methods without major breakthroughs.
The paper tackled the problem of applying the Implicit Hitting Set approach to Weighted CSPs by exploring 32 alternative implementations, focusing on trade-offs in computing low-cost hitting vectors and transforming them into high-cost cores, with results indicating that cost-function merging encoding and extracting maximal cores is a robust approach, though no single best alternative was easily identified.
SAT technology has proven to be surprisingly effective in a large variety of domains. However, for the Weighted CSP problem dedicated algorithms have always been superior. One approach not well-studied so far is the use of SAT in conjunction with the Implicit Hitting Set approach. In this work, we explore some alternatives to the existing algorithm of reference. The alternatives, mostly borrowed from related boolean frameworks, consider trade-offs for the two main components of the IHS approach: the computation of low-cost hitting vectors, and their transformation into high-cost cores. For each one, we propose 4 levels of intensity. Since we also test the usefulness of cost function merging, our experiments consider 32 different implementations. Our empirical study shows that for WCSP it is not easy to identify the best alternative. Nevertheless, the cost-function merging encoding and extracting maximal cores seems to be a robust approach.