Network synthesis problems (Q1592496)

The book deals with network synthesis problems typically arising in the context of telecommunication networks. The main question is: How to dimension given networks to guarantee a certain level of safety in case of damages. The book gives an overview about the modeling of network repairing for different application contexts: For single commodity flow requirements, i.e. only one, fixed set of requirements, the two basic problems: ``Line Restoration Problem'' and ``Multi-Hour Problem with Single Commodity'' are discussed. The first problem tries to protect a fixed set of edges in case of a breakdown -- then the broken edge can not be used. Whereas the similar, but different second problem treats an additional amount of network flow at minimum cost -- here all edges can be used. In general, both problems are NP-complete (a reduction to the ``Steiner Tree Problem'' is proposed), but a special case of the ``Multi-Hour Problem with Single Commodity'' can be polynomially solved. The essential difference between single commodity problems and multi-commodity problems, i.e. time varying different requirements, are listed. Here relaxations for the integer linear program formulations are stated, heuristics are examined and computational results for ``Tabu search'' algorithms are proposed. All these theoretical results are applied to the practical telecommunication problems, like restoring a set of edges or nodes for a partially equipped SDH network. For these problems various numerical results are presented. A special design feature using ``SeIf-Healing Rings'' is introduced and a literature review is given. All in all the book provides a wide overview to the topic of network synthesis and is enriched with new results in this very practical topic.