A Divide-And-Conquer-Method for Computing Multiple Conflicts for Diagnosis.
Kostyantyn M. Shchekotykhin, Dietmar Jannach, Thomas Schmitz · 2015
In classical hitting set algorithms for ModelBased Diagnosis (MBD) that use on-demand conflict generation, a single conflict is computed whenever needed during tree construction. Since such a strategy leads to a full “restart” of the conflict-generation algorithm on each call, we propose a divide-and-conquer algorithm called MERGEXPLAIN which efficiently searches for multiple conflicts during a single call. The design of the algorithm aims at scenarios in which the goal is to find a few leading diagnoses and the algorithm can – due to its non-intrusive design – be used in combination with various underlying reasoners (theorem provers). An empirical evaluation on different sets of benchmark problems shows that our proposed algorithm can lead to significant reductions of the required diagnosis times when compared to a “one-conflict-ata-time” strategy.