Rui Maranhão

Citation:

Abreu R, Van Gemund AJC.  2009.  A low-cost approximate minimal hitting set algorithm and its application to model-based diagnosis. Abstraction, Reformulation, and Approximation (SARA).

Abstract:

Generating minimal hitting sets of a collection of sets is known to be NP-hard, necessitating heuristic approaches to handle large problems. In this paper a low-cost, approximate minimal hitting set (MHS) algorithm, coined Staccato, is presented. Staccato uses a heuristic function, borrowed from a lightweight, statistics-based software fault localization approach, to guide the MHS search. Given the nature of the heuristic function, Staccato is specially tailored to model-based diagnosis problems (where each MHS solution is a diagnosis to the problem), although well-suited for other application domains as well. We apply Staccato in the context of model-based diagnosis and show that even for small problems our approach is orders of magnitude faster than the brute-force approach, while still
capturing all important solutions. Furthermore, due to its low cost complexity, we also show that Staccato is amenable to large problems including millions of variables.

Citation Key: