MergeXplain: Fast Computation of Multiple Conflicts for Diagnosis
Abstract
The computation of minimal conflict sets is a central task when the goal is to find relaxations or explanations for overconstrained problem formulations and in particular in the context of Model-Based Diagnosis (MBD) approaches. In this paper we propose MergeXPlain, a non-intrusive conflict detection algorithm which implements a divide-and-conquer strategy to decompose a problem into a set of smaller independent subproblems. Our technique allows us to efficiently determine multiple minimal conflicts during one single problem decomposition run, which is particularly helpful in MBD problem settings. An empirical evaluation on various benchmark problems shows that our method can lead to a significant reduction of the required diagnosis times.
Cite
Text
Shchekotykhin et al. "MergeXplain: Fast Computation of Multiple Conflicts for Diagnosis." International Joint Conference on Artificial Intelligence, 2015.Markdown
[Shchekotykhin et al. "MergeXplain: Fast Computation of Multiple Conflicts for Diagnosis." International Joint Conference on Artificial Intelligence, 2015.](https://mlanthology.org/ijcai/2015/shchekotykhin2015ijcai-mergexplain/)BibTeX
@inproceedings{shchekotykhin2015ijcai-mergexplain,
title = {{MergeXplain: Fast Computation of Multiple Conflicts for Diagnosis}},
author = {Shchekotykhin, Kostyantyn M. and Jannach, Dietmar and Schmitz, Thomas},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2015},
pages = {3221-3228},
url = {https://mlanthology.org/ijcai/2015/shchekotykhin2015ijcai-mergexplain/}
}