An efficient parallel approach for binary-state network reliability problems

Autor(es)

Yeh, Wei-Chang ; Forghani-elahabad, Majid

• Tipo de documento: Artigo Científico
• Fonte: ANNALS OF OPERATIONS RESEARCH; v. N/A, p. 22-pg., 2024-12-04.

Resumo

Networks are ubiquitous in modern applications, with reliability being a paramount performance metric. While exact network reliability can be determined using implicit enumeration algorithms like depth-first search, breadth-first search, the universal generating function methodology, the binary decision diagram, and the binary addition tree algorithm (BAT), these methods are limited to small-scale networks. The recently introduced BAT algorithm offers a high-speed, flexible, and easily implementable exact solution for determining network reliability. Experimental results demonstrate BAT's superiority over other implicit enumeration algorithms. To address the computational challenges of larger networks, we propose a multithreaded version of BAT (mBAT). By leveraging multi-core architectures, mBAT efficiently solves medium-scale network reliability problems, as confirmed by time complexity analysis and experiments on 20 benchmark instances using up to 12 CPU threads. (AU)

• Processo FAPESP: 23/13667-5 - Avaliação da confiabilidade de redes de fluxo multiestado e algumas aplicações
• Beneficiário: Majid Forghani Elahabad
• Modalidade de apoio: Auxílio à Pesquisa - Regular