On the practical performance of minimal hitting set algorithms from a diagnostic perspective

Ingo Pill, Thomas Quaritsch, Franz Wotawa

    Research output: Contribution to journalArticlepeer-review

    Abstract

    Minimal hitting sets (MHSs) meliorate our reasoning in many applications, including AI planning, CNF/DNF conversion, and program debugging. When following Reiter’s ”theory of diagnosis from first principles”, minimal hitting sets are also essential to the diagnosis problem, since diagnoses can be characterized as the minimal hitting sets of conflicts in the behavior of a faulty system. While the large amount of application options led to the advent of a variety of corresponding MHS algorithms, for diagnostic purposes we still lack a comparative evaluation assessing performance characteristics. In this paper, we thus empirically evaluate a set of complete algorithms relevant for diagnostic purposes in synthetic and real-world scenarios. We consider in our experimental evaluation also how cardinality constraints on the solution space, as often established in practice for diagnostic purposes, influence performance in terms of run-time and memory usage.
    Original languageEnglish
    JournalInternational Journal of Prognostics and Health Management
    Volume7
    Issue number2
    DOIs
    Publication statusPublished - 2016

    Fingerprint

    Dive into the research topics of 'On the practical performance of minimal hitting set algorithms from a diagnostic perspective'. Together they form a unique fingerprint.

    Cite this