期刊名称：IAENG International Journal of Computer Science
印刷版ISSN：1819-656X
电子版ISSN：1819-9224
出版年度：2020
卷号：47
期号：1
语种：English
出版社：IAENG - International Association of Engineers
摘要：Recently, extensive real-world networks have emerged astounding structural properties, such as highrobustness, tree-hierarchies and low-cost, which bring deep insights into studying graph theory, combinatorics and topology, to name a few. In this paper, we investigate how to design an economical (or low-cost) networks with special graph structures as requirement. Our specific objective is to design a network with minimum construction cost while at least two basic but fundamental graph conditions are required as constraints: (i) network connectivity, implying no isolated subgraph exists in the network; (ii) minimum level of capacity requirement at each node must be satisfied. We propose a mixed-integer programming (MIP) method to efficiently construct optimal economical networks. Our computational results show that no more than n edges are required for designing a network satisfying the above two conditions. We also tackle a special network design case when network structure is a spanning tree. Such an economical spanning tree design problem (ESTDP) which has been proved to a NP-hard problem in S. Nakano’s previous work. Three different MIP formulations are proposed and evaluated on extensive numerical studies. Our computational results demonstrate Martin’s formation outperforms the subtour elimination formulation and cutset formulation due to their non-exponential increasing constraints in terms of computational time and optimality gap.
