Data for the article "A New Efficient Algorithm Addressing the (d, c)-MC Problem"

Citation Author(s):
Submitted by:
Paul Kozyra
Last updated:
Mon, 05/17/2021 - 13:56
0 ratings - Please login to submit your rating.


Many real-world systems can be modeled by multistate flow networks (MFNs) and their reliability evaluation features in designing and control of these systems. Considering the cost constraint makes the problem of reliability evaluation of an MFN more realistic. For a given demand value $d$ and a given cost limit $c$, the reliability of an MFN at level $(d, c)$ is the probability of transmitting at least $d$ units from the source node to the sink node through the network within the cost of $c$.  This article addresses this so-called $(d, c)$-MC problem in terms of minimal cuts. It presents new results on which a new algorithm is based. This algorithm finds all $(d, c)$-MC candidates without duplicates and verifies them more efficiently than existing ones. The complexity results for this algorithm and an example of its use are provided. Finally, numerical experiments with R implementations of the presented algorithm and other competitive algorithms are considered. Both, the time complexity analysis and numerical experiments demonstrate the presented algorithm to be more efficient than other existing ones in the majority of cases.


The data set contains two folders: 'MCs lists' and 'd_c_MCs lists', and two additional files Params.csv and t_aux.csv.

The folder 'MCs lists' contains 7 files in the csv format. Each of these files the list of all minimal cuts for appropriate multistate flow network (MFN) from figures 2-6. The arcs in networks 1,2,3,5,6,7 are ordered firstly according to the order of their beginning nodes and secondly on the order of their ending nodes. Only in the network Id 4 from Fig. 3 the order of the arcs is another, and this order is visible in Fig. 3.

The folder 'd_c_MCs lists' contains 126 files in the csv format. Each of these files has the name of the form i_j_(d,c)-MCs, where i denotes the MFN ID, j - the number of the variant of the greatest state vector, d - demand level, and c- cost constraint. Each of these files contains all (d,c)-MCs determined for given MFN ID - i, and the greatest state vector of the number of the variant - j.

The file 'Params.csv' contains experimental results of numerical experiments conducted on a computer with Intel(R) Core(TM) i7-8750H CPU and 16 GB of RAM.The first column contains MFN ID; the second - the number of the variant of the greatest state vector;the third - demand level d; the fourth - the total budget c;the fifth - the number of elements of set Q_1 defined by (20) in Lemma 8 in the related article;the sixth - the number of elements of set Q_2 defined by (21) in Lemma 8 in the related article; the seventh - the number of all (d,c)-MCs; the eight - the mean computational time T_{FK} of the algorithm described in the article M. Forghani-elahabad, N. Kagan, Assessing Reliability of Multistate Flow Networks Under Cost Constraint in Terms of Minimal Cuts Int. J. Reliab. Qual. Saf. Eng.2019,26, 1950025; the ninth - the mean computational time T of the presented algorithm;the tenth - the ratio T_{FK}/T.

The file 't_aux' contains the means of the computational times of the introductory algorithm.

Computational times in columns 8 and 9 in file 'Params.csv' and in file 't_aux' are expressed in nanoseconds and are results of the use of the microbenchmark procedure from the microbenchmark library implemented in R.