Design of survivable networks with bounded rings (Q4515976)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1535630
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Design of survivable networks with bounded rings |
scientific article; zbMATH DE number 1535630 |
Statements
26 November 2000
0 references
network optimization
0 references
telecommunication
0 references
branch-and-cut methods
0 references
heuristics
0 references
0.8788006901741028
0 references
0.8503867387771606
0 references
0.839359700679779
0 references
Design of survivable networks with bounded rings (English)
0 references
The book deals with models to design reliable (or survivable) communication networks in which re-routing of communication due to failure of a link is not too costly. The reliability part is modeled by 2-connected networks - an area well considered in the literature. The cost objective is modeled by bounded rings meaning that each link should be contained in a cycle (= ring) with bounded length. This model is new and has not been considered before. After introducing the model and various integer programming formulations, the author provides tools to tackle the problem using branch-and-cut methods. For this purpose the polyhedral structure is investigated. In particular, various classes of facet-defining inequalities are identified. For the case of unit lengths (i.e. where the number of links per ring is bounded) a lower bound of the number of links which have to be used in any feasible solution is found. After working out more details on the implementation of the branch-and-cut algorithm, including solution procedures for the separation problem, the book is concluded by suggesting various heuristics (some with performance guarantees) and extensive numerical test. For future work in this area a test bed of problems is provided.
0 references