A Branch-and-Cut Approach to Solve the Fault Diagnosis Problem with Lazy Spread and Imperfect System Information

This paper presents a new approach to solving the Fault Diagnosis Problem with Lazy Spread (FDPL) that arises in many fault-tolerant real-world systems with few opportunities for maintenance during their operations and significant failure interactions between the subsystems/components. As opposed to cascading faults that spread to most of the system almost instantaneously, FDPL considers fault resistant systems where the spread of failures is relatively slow (lazy), i.e., only a small fraction of the components are faulty at the time of inspection, and accurate diagnosis of the faulty components is of critical importance to restore system performance and stop further damage. Introducing an extra level of difficulty, FDPL needs to be solved under imperfect (missing and wrong) system information in most realworld settings. To address this challenging prediction problem, we use graph theory concepts to develop an integer programming formulation and devise an efficient branch-and-cut algorithm for its solution. Extensive numerical experiments on realistic problem instances attest to the superior performance of our approach, in terms of both computational efficiency and prediction accuracy, compared to the state-ofthe-art in the literature