---
title: "Computing Minimum-Cardinality Diagnoses by Model Relaxation"
authors:
  - "Sajjad Ahmed Siddiqi"
doi: "10.5591/978-1-57735-516-8/IJCAI11-186"
url: "https://ijcai.org/proceedings/2011/186"
pdf: "https://ijcai.org/proceedings/2011/0186.pdf"
venue: "Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence"
year: 2011
pages: "1087-1091"
track: ""
keywords:
---

# Computing Minimum-Cardinality Diagnoses by Model Relaxation

Sajjad Ahmed Siddiqi

*Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence*, pages 1087-1091. DOI: [10.5591/978-1-57735-516-8/IJCAI11-186](https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-186)

## Abstract

We propose a new approach based on model relaxation to compute minimum-cardinality diagnoses of a (faulty) system: We obtain a relaxed model of the system by splitting nodes in the system and compile the abstraction of the relaxed model into DNNF. Abstraction is obtained by treating self-contained sub-systems called cones as single components. We then use a novel branch-and-bound search algorithm and compute the abstract minimum-cardinality diagnoses of the system, which are later refined hierarchically, in a careful manner, to get all minimum-cardinality diagnoses of the system. Experiments on ISCAS-85 benchmark circuits show that the new approach is faster than the previous state-of-the-art hierarchical approach, and scales to all circuits in the suite for the first time.