Optimal and near-optimal algorithms for multiple fault diagnosiswith unreliable tests

摘要

We consider the problem of constructing optimal and near-optimalnmultiple fault diagnosis (MFD) in bipartite systems with unreliablen(imperfect) tests. It is known that exact computation of conditionalnprobabilities for MFD is NP hard. The novel feature of our diagnosticnalgorithms is the use of Lagrangian relaxation and subgradientnoptimization methods to provide: 1) near optimal solutions for the MFDnproblem and 2) upper bounds for an optimal branch and bound algorithm.nThe proposed method is illustrated using several examples. Computationalnresults indicate the following: 1) our algorithm has superiorncomputational performance to the existing algorithms (approximatelynthree orders of magnitude improvement over the algorithm by Z. Binglinnet al. (1993)); 2) near optimal algorithm generates the most likelyncandidates with a very high accuracy; 3) our algorithm can find the mostnlikely candidates in systems with as many as 1000 faults