Topological Optimization Problem for a Network System with Separate Subsystems

Yoshihiro MURASHIMA  Taishin NAKAMURA  Hisashi YAMAMOTO  Xiao XIAO  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E104-A   No.5   pp.797-804
Publication Date: 2021/05/01
Publicized: 2020/10/27
Online ISSN: 1745-1337
DOI: 10.1587/transfun.2020EAP1066
Type of Manuscript: PAPER
Category: Reliability, Maintainability and Safety Analysis
network reliability,  all-terminal reliability,  network design,  optimization,  

Full Text: PDF(2MB)>>
Buy this Article

In a network topology design problem, it is important to analyze the reliability and construction cost of complex network systems. This paper addresses a topological optimization problem of minimizing the total cost of a network system with separate subsystems under a reliability constraint. To solve this problem, we develop three algorithms. The first algorithm finds an exact solution. The second one finds an exact solution, specialized for a system with identical subsystems. The third one is a heuristic algorithm, which finds an approximate solution when a network system has several identical subsystems. We also conduct numerical experiments and demonstrate the efficacy and efficiency of the developed algorithms.