Robust and Survivable Network Design Considering Uncertain Node and Link Failures

摘要: The network design is a planning process of placing system components to provide service or meet certain needs in an economical way. It has strong links real application areas, such as transportation network, communication supply chain, power grid, water distribution systems, etc. In practice, these infrastructures are very vulnerable any failures components. Therefore, the infrastructure networks should be robust and survivable caused by many factors, for example, natural disasters, intentional attacks, limits, this dissertation, we first summarize background motivations our research topic on problems. Different from literatures design, consider both uncertain node link during process. part with mixed connectivity requirements, (k, l)-connectivity. designed can still connected after k vertices (l − 1) edges (k l edges. After formally proving its relationships edge vertex disjoint paths, present two integer programming (IP) formulations, valid inequalities strengthen IP cutting plane algorithm. Numerical experiments performed randomly generated graphs compare approaches. Special cases problem include: when = 0, 1, becomes well-known minimum spanning tree problem; ≥ find minimum-cost l-edge-connected subgraph, while 2, k-vertex-connected subgraph. As generalization k-minimum λ-edge-connected span-