A Classification Tree Based Approach for the Development of Minimal Cut and Path Vectors of a Capacitated Network

A holistic method that links together Monte-Carlo simulation, exact algorithms, and a data mining technique, to develop approximate bounds on the reliability of capacitated two-terminal networks is presented.

Abstract

This paper presents a holistic method that links together Monte-Carlo simulation, exact algorithms, and a data mining technique, to develop approximate bounds on the reliability of capacitated two-terminal networks. The method uses simulation to generate network configurations that are then evaluated with exact algorithms to investigate if they correspond to a network success or failure. Subsequently, the method implements commercially available software to generate a classification tree that can then be analyzed, and transformed into capacitated minimal cut or path vectors. These vectors correspond to the capacitated version of binary minimal cuts & paths of a network. This is the first time that these vectors are obtained from a decision tree, and in this respect, research efforts have been focused on two main directions: 1) deriving an efficient yet intuitive approach to simulate network configurations to obtain the most accurate information; and given that the classification tree method could for some applications provide imperfect or incomplete information without the explicit knowledge of the reliability engineer, 2) understand the relationship between the obtained vectors, and the real capacitated minimal cut & path vectors of the network, and its reliability. The proposed method has been tested on a set of case networks to assess its validity & accuracy. The results obtained show that the technique described is effective, simple, and widely applicable.