Empirical Evaluation of the Implicit Hitting Set Approach for Weighted CSPs
Aleksandra Petrova, Javier Larrosa, Emma Rollón · 2025
Read Empirical Evaluation of the Implicit Hitting Set Approach for Weighted CSPs by Aleksandra Petrova, Javier Larrosa, Emma Rollón (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-07432.txt.
Introduction
Aleksandra Petrova, Javier Larrosa, and Emma Rollón test whether SAT solvers can crack weighted constraint problems through the implicit hitting set method. For such problems, dedicated algorithms have always beaten general SAT tools. The hitting set approach splits the work in two: find cheap hitting vectors, then turn them into costly cores that guide the search. The team borrowed variants of both steps from related Boolean frameworks and tried each at four levels of intensity.
With cost function merging also switched on or off, the experiments covered 32 versions of the method. No single version won across the board, which the authors say makes the best choice hard to pin down. One pairing did prove robust: the merging encoding together with pulling out maximal cores.
Catalog record
| CREATOR | Aleksandra Petrova, Javier Larrosa, Emma Rollón |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 35 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-07432
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Empirical Evaluation of the Implicit Hitting Set Approach for Weighted CSPs Aleksandra Petrova, Javier Larrosa, Emma Rollón Abstract 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. 1 Introduction The Weighted CSP problem (WCSP) is a framework for discrete optimization with many practical applications [ 7 , 24 , 25 , 4 , 7 , 24 , 25 , 4 ] that has attracted the interest of researchers for decades [ 8 , 19 , 1 , 3 ] . In this paper, we focus on the Implicit Hitting Set Approach (IHS) for WCSP solving. The idea of the IHS algorithms is to iteratively grow a set of unsatisfiable pieces of the problem (called cores ) and find if it is possible to solve the problem by avoiding ( i.e , hitting ) them. The algorithm terminates when the best way to hit the identified cores incidentally also hits the unidentified cores. The motivation for our work is that IHS is surprisingly effective for the MaxSAT problem [ 11 , 12 , 5 ] , and such success has been lifted to several generalization frameworks such as Pseudo-boolean optimization [ 22 , 23 ] , MaxSMT [ 14 ] and Answering Set Programming [ 21 ] . Although MaxSAT and WCSP are fairly similar, to the best of our knowledge the only works that consider IHS for WCSP are [ 13 , 18 ] and, in both cases, a very simple IHS strategy is used. In this paper, we test the potential of several variations of the original algorithm that have already been proposed and successfully applied in other frameworks. Here, we adapt them to WCSPs and test their effect empirically. We consider four different ways in which to obtain hitting vectors and four different ways in which to transform them into an improved core. Since we also test the effectiveness of cost-function merging [ 18 ] we end up with 4\times 4\times 2=32 different algorithms that we test on several benchmarks. The experiments show that different algorithms may have a dramatic difference in performance (up to several orders of magnitude). Most importantly, they show that no algorithm systematically dominates all the others, but merging cost-functions following [ 18 ] and computing maximal cores seems to be the most robust strategy. This configuration most of the times is the most efficient or is close to the most efficient. Regarding the computation of hitting vectors, greedy heuristics often do not pay off. Although there is no clear winner between optimal and cost-bounded hitting vectors, cost-bounded ones seem to have more potential because it offers more implementation alternatives. 2 Preliminaries A Constraint Satisfaction Problem (CSP) is a pair (X,C) where X is a set of variables taking values in a finite domain, and C is a set of constraints . Each constraint depends on a subset of variables called scope . Constraints are boolean functions that forbid some of the possible assignments of the scope variables. A solution is an assignment to every variable that satisfies all the constraints. Solving CSPs is known to be an NP-complete problem [ 16 ] . A Weighted CSP (WCSP) is a CSP augmented with a set F of cost functions . A cost function f\in F is a mapping that associates a cost to each possible assignment of the variables in its scope. The cost of a solution is the sum of costs given by the different cost functions. The WCSP problem consists of computing a solution of minimum cost w^{*} . The IHS approach for WCSP is defined in terms of vectors. The cost of vector \vec{v}=(v_{1},v_{2},\ldots,v_{m}) is cost(\vec{v})=\sum_{i=1}^{m}v_{i} . In the (partial) order among same-size vectors, \vec{u}\leq\vec{v} , holds iff for each component i we have that u_{i}\leq v_{i} . If \vec{u}\leq\vec{v} we say that \vec{v} dominates \vec{u} . We say that a set of vectors {\cal V} dominates a vector \vec{u} , noted \vec{u}\leq{\cal V} , if there is some \vec{v}\in{\cal V} that dominates \vec{u} . Further, we say that a set of vectors {\cal V} dominates a set of vectors {\cal U} , noted {\cal U}\leq{\cal V} , if {\cal V} dominates every vector of {\cal U} . Given a set of vectors {\cal U} , a vector \vec{u}\in{\cal U} is maximal if it is not dominated by any other element of {\cal U} . The set of maximal vectors in {\cal U} is noted \overline{{\cal U}} . The set of vectors in {\cal U} with cost less than w is noted {\cal U}_{(<w)} . If \vec{u} is not dominated by {\cal V} we say that it hits {\cal V} . The minimum cost hitting vector MHV of {\cal V} is a vector that hits {\cal V} with minimum cost. It is not difficult to see that MHV reduces to the classic minimum hitting set problem [ 15 ] , which is known to be NP-hard. In the following, we will consider an arbitrary WCSP (X,C,F) with m cost functions F=\{f_{1},f_{2},\ldots,f_{m}\} . A cost vector \vec{v}=(v_{1},v_{2},\ldots,v_{m}) is a vector where each component v_{i} is associated to cost function f_{i} , and value v_{i} must be a cost occurring in f_{i} . Cost vector \vec{v} induces a CSP (X,C\cup F_{\vec{v}}) where F_{\vec{v}} denotes the set of constraints (f_{i}\leq v_{i}) for 1\leq i\leq m (namely, cost functions are replaced by constraints). If the CSP induced by \vec{v} is satisfiable we will say that \vec{v} is a solution vector . Otherwise, we will say that \vec{v} is a core . The set of all cores will be denoted {Cores} . An optimal solution vector is a solution vector of minimum cost. It is easy to see that the cost of an optimal solution vector is the same as the optimum cost w^{*} of the WCSP. 3 IHS-based WCSP solving The IHS approach relies on the following observation that establish a lower bound and an upper bound condition in terms of cores and solutions, Observation 1 . Consider a solution vector \vec{h} and a set of cores {\cal K}\subseteq{Cores} . Then, MHV({\cal K})\leq w^{*}\leq cost(\vec{h}) . All the algorithms discussed in this paper will aim at finding a solution \vec{h} and a (possibly small) set of cores {\cal K} such that the two bounds meet (that is, MHV({\cal K})=cost(\vec{h}) ). This condition corresponds to \vec{h} being optimal and {\cal K} being the proof of its optimality. We will refer