An Improved Vectorization Algorithm to Solve the d-MP Problem
DOI:
https://doi.org/10.5540/tcam.2022.024.01.00019Keywords:
Vectorization techniques, Network reliability, d-MP problem, Stochastic-flow networksAbstract
The d-minimal path (d-MP) problem is to find all the system state vectors (SSV) under which d units of data can be transmitted from a source node to a destination node in a stochastic-flow network (SFN). This problem has been very attractive in the last decades as one can compute the exact amount of the network’s reliability through the d-MPs. Although several algorithms have been proposed in the literature to address the problem, the research continues because it is NP-hard. Since the number of d-MPs grows exponentially with the size of the network, the available algorithms in the literature are not so practical. Hence, we employ the vectorization techniques for proposing an improved algorithm to address the problem. We conduct many experimental results on the known benchmarks and two hundred randomly generated SFNs in the sense of performance profile introduced by Dolan and Moré. The experimental results show the vectorization algorithm to be considerably more efficient than the non-vectorization ones.
References
Z. Hao, W.-C. Yeh, M. Zuo, and J. Wang, “Multi-distribution multi-commodity multistate flow network model and its reliability evaluation algorithm,” Reliability Engineering & System Safety, vol. 193, p. 106668, 2020.
Y.-F. Niu, Z.-Y. Gao, and W. H. Lam, “Evaluating the reliability of a stochastic distribution network in terms of minimal cuts,” Transportation Research Part E: Logistics and Transportation Review, vol. 100, pp. 75–97, 2017.
M. Forghani-elahabad and N. Mahdavi-Amiri, “A new efficient approach to search for all multi-state minimal cuts,” IEEE Transactions on Reliability, vol. 63, no. 1, pp. 154–166, 2014.
Z. Hao, W.-C. Yeh, Z. Liu, and M. Forghani-elahabad, “General multi-state rework network and reliability algorithm,” Reliability Engineering & System Safety, vol. 203, p. 107048, 2020.
Y.-F. Niu, X.-Z. Xu, C. He, D. Ding, and Z.-Z. Liu, “Capacity reliability calculation and sensitivity analysis for a stochastic transport network,” IEEE Access, vol. 8, pp. 133161–133169, 2020.
M. Forghani-elahabad and N. Mahdavi-Amiri, “An efficient algorithm for the multi-state two separate minimal paths reliability problem with budget constraint,” Reliability Engineering & System Safety, vol. 142, pp. 472–481, 2015.
W.-C. Yeh, Z. Hao, M. Forghani-elahabad, G.-G. Wang, and Y.-L. Lin, “Novel binary-addition tree algorithm for reliability evaluation of acyclic multistate information networks,” Reliability Engineering & System Safety, vol. 210, p. 107427, 2021.
X. Chen, J. Tao, G. Bai, and Y. Zhang, “Search for d-mps without duplications in multistate two-terminal networks,” in 2017 Second International Conference on Reliability Systems Engineering (ICRSE), pp. 1–7, IEEE, 2017.
M. Forghani-elahabad and N. Mahdavi-Amiri, “On search for all d-mcs in a network flow,” Iranian Journal of Operations Research, vol. 4, no. 2, pp. 108–126, 2013.
D.-H. Huang, C.-F. Huang, and Y.-K. Lin, “Reliability evaluation for a stochastic flow network based on upper and lower boundary vectors,” Mathematics, vol. 7, no. 11, p. 1115, 2019.
J.-S. Lin, C.-C. Jane, and J. Yuan, “On reliability evaluation of a capacitated-flow network in terms of minimal pathsets,” Networks, vol. 25, no. 3, pp. 131–138, 1995.
M. Forghani-elahabad and L. H. Bonani, “Finding all the lower boundary points in a multistate two-terminal network,” IEEE Transactions on Reliability, vol. 66, no. 3, pp. 677–688, 2017.
W.-C. Yeh and M. J. Zuo, “A new subtraction-based algorithm for the d-mps for all d problem,” IEEE Transactions on Reliability, vol. 68, no. 3, pp. 999–1008, 2019.
Y. Lamalem, K. Housni, and S. Mbarki, “An efficient method to find all d-mps in multistate two-terminal networks,” IEEE Access, vol. 8, pp. 205618–205624, 2020.
M. Forghani-elahabad and N. Kagan, “Reliability evaluation of a stochastic-flow network in terms of minimal paths with budget constraint,” IISE Transactions, vol. 51, no. 5, pp. 547–558, 2019.
W.-C. Yeh, “A simple minimal path method for estimating the weighted multi-commodity multistate unreliable networks reliability,” Reliability Engineering & System Safety, vol. 93, no. 1, pp. 125–136, 2008.
M. Forghani-elahabad, N. Kagan, and N. Mahdavi-Amiri, “An mp-based approximation algorithm on reliability evaluation of multistate flow networks,” Reliability Engineering & System Safety, vol. 191, p. 106566, 2019.
X.-Z. Xu, Y.-F. Niu, and Y.-F. Song, “Computing the reliability of a stochastic distribution network subject to budget constraint,” Reliability Engineering & System Safety, vol. 216, p. 107947, 2021.
Y.-F. Niu, X.-Y. Wan, X.-Z. Xu, and D. Ding, “Finding all multi-state minimal paths of a multi-state flow network via feasible circulations,” Reliability Engineering & System Safety, vol. 204, p. 107188, 2020.
M. Forghani-Elahabad, N. Mahdavi-Amiri, and N. Kagan, “On multi-state two separate minimal paths reliability problem with time and budget constraints,” International Journal of Operational Research, vol. 37, no. 4, pp. 479–490, 2020.
G. Bai, Z. Tian, and M. J. Zuo, “Reliability evaluation of multistate networks: An improved algorithm using state-space decomposition and experimental comparison,” IISE Transactions, vol. 50, no. 5, pp. 407–418, 2018.
E. Datta and N. K. Goyal, “Evaluation of stochastic flow networks susceptible to demand requirements between multiple sources and multiple destinations,” International Journal of System Assurance Engineering and Management, vol. 10, no. 5, pp. 1302–1327, 2019.
M. Forghani-elahabad, “1 exact reliability evaluation of multistate flow networks,” in Systems Reliability Engineering, pp. 1–24, De Gruyter, 2021.
S. M. Mansourzadeh, S. H. Nasseri, M. Forghani-elahabad, and A. Ebrahimnejad, “A comparative study of different approaches for finding the upper boundary points in stochastic-flow networks,” International Journal of Enterprise Information Systems (IJEIS), vol. 10, no. 3, pp. 13–23, 2014.
M. Forghani-elahabad and N. Kagan, “An approximate approach for reliability evaluation of a multistate flow network in terms of minimal cuts,” Journal of Computational Science, vol. 33, pp. 61–67, 2019.
Y.-F. Niu, Z.-Y. Gao, and W. H. Lam, “A new efficient algorithm for finding all d-minimal cuts in multi-state networks,” Reliability Engineering & System Safety, vol. 166, pp. 151–163, 2017.
W.-C. Yeh, “A new method for verifying d-mc candidates,” Reliability Engineering & System Safety, vol. 204, p. 107202, 2020.
M. Forghani-elahabad and N. Mahdavi-Amiri, “An improved algorithm for finding all upper boundary points in a stochastic-flow network,” Applied Mathematical Modelling, vol. 40, no. 4, pp. 3221–3229, 2016.
Y.-K. Lin and S.-G. Chen, “A maximal flow method to search for d-mps in stochastic-flow networks,” Journal of computational science, vol. 22, pp. 119–125, 2017.
A. O. Balan and L. Traldi, “Preprocessing minpaths for sum of disjoint products,” IEEE Transactions on Reliability, vol. 52, no. 3, pp. 289–295, 2003.
W.-C. Yeh, “Fast algorithm for searching d-mps for all possible d,” IEEE Transactions on Reliability, vol. 67, no. 1, pp. 308–315, 2018.
E. D. Dolan and J. J. Moré, “Benchmarking optimization software with performance profiles,” Mathematical programming, vol. 91, no. 2, pp. 201–213, 2002.
T. Rauber and G. Rünger, Parallel programming: for multicore and cluster systems. Springer-Verlag, 2010.
J. L. Hennessy and D. A. Patterson, Computer architecture: a quantitative approach. Elsevier, 2011.
J. L. Bentley, “Multidimensional divide-and-conquer,” Communications of the ACM, vol. 23, no. 4, pp. 214–229, 1980.
Downloads
Published
How to Cite
Issue
Section
License
Copyright
Authors of articles published in the journal Trends in Computational and Applied Mathematics retain the copyright of their work. The journal uses Creative Commons Attribution (CC-BY) in published articles. The authors grant the TCAM journal the right to first publish the article.
Intellectual Property and Terms of Use
The content of the articles is the exclusive responsibility of the authors. The journal uses Creative Commons Attribution (CC-BY) in published articles. This license allows published articles to be reused without permission for any purpose as long as the original work is correctly cited.
The journal encourages Authors to self-archive their accepted manuscripts, publishing them on personal blogs, institutional repositories, and social media, as long as the full citation is included in the journal's website version.
