A novel minimal cut-based algorithm to find all minimal capacity vectors for multi-state flow networks

Ding Hsiang Huang, Cheng Fu Huang, Yi Kuei Lin*

*Corresponding author for this work

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

Real systems, such as computer systems, can be modeled as network topologies with vertices and edges. Owing to equipment failures and maintenance requirements, the capacities of edges have several states. Such systems are regarded as multi-state flow networks (MSFN). System reliability of an MSFN is the probability that the required flow (i.e., demand) can successfully be sent from the source to the sink. By adopting a minimal path (MP) approach, system reliability can be computed in terms of all minimal capacity vectors meeting the demand d. A minimal capacity vector is called a d-MP. Although several algorithms have been presented in the literature for finding all d-MP, improving efficiency in the search for all d-MP is always a challenge. A group approach with both the concepts of minimal cut and MP is developed in this study, narrowing the search range of feasible flow vectors. An algorithm based on the group approach is then proposed to improve the efficiency of the d-MP search. According to the structure of the proposed algorithm, parallel computing can be implemented with significant improvement in the efficiency of the d-MP generation, where the proposed algorithm is compared with previous ones based on three benchmarks, in terms of CPU time.

Original languageEnglish
Pages (from-to)1107-1114
Number of pages8
JournalEuropean Journal of Operational Research
Volume282
Issue number3
DOIs
StatePublished - 1 May 2020

Keywords

  • d-MP
  • Minimal cuts
  • Multi-state flow network
  • Parallel computing
  • Reliability

Fingerprint Dive into the research topics of 'A novel minimal cut-based algorithm to find all minimal capacity vectors for multi-state flow networks'. Together they form a unique fingerprint.

  • Cite this