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

      0 references
      26 November 2000
      0 references
      network optimization
      0 references
      telecommunication
      0 references
      branch-and-cut methods
      0 references
      heuristics
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references