M. Shakeri et al., OPTIMAL AND NEAR-OPTIMAL ALGORITHMS FOR MULTIPLE-FAULT DIAGNOSIS WITHUNRELIABLE TESTS, IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART C-APPLICATIONS AND REVIEWS, 28(3), 1998, pp. 431-440
In this paper, we consider the problem of constructing optimal and nea
r-optimal multiple fault diagnosis (MFD) in bipartite systems with unr
eliable (imperfect) tests, It is known that exact computation of condi
tional probabilities for MFD is NP-hard. The novel feature of our diag
nostic algorithms is the use of Lagrangian relaxation and subgradient
optimization methods to provide 1) near-optimal solutions for the MFD
problem and 2) upper bounds for an optimal branch-and-bound algorithm.
The proposed method is illustrated using several examples. Computatio
nal results indicate the following. 1) Our algorithm has superior comp
utational performance to the existing algorithms (approximately three
orders of magnitude improvement over the algorithm in [3]), 2) Near-op
timal algorithm generates the most likely candidates with a very high
accuracy. 3) Our algorithm can find the most likely candidates in syst
ems,vith as many as 1000 faults.