Paula Carroll

Abstract

The aim of this work is to introduce the Ring Spur Assignment Problem (RSAP). It is a new and interesting challenging combinatorial optimisation problem that has not to our knowledge previously been described in the literature. It arises in the context of exploiting existing resources efficiently in the strategic development of survivable telecommunications networks.

The RSAP is described and positioned in relation to problems previously addressed in the literature, and the business context for the RSAP is justified. Significant amounts of money are involved in maintaining and upgrading telecommunications infrastructure. The RSAP topology offers solutions when no solution topologies are available from existing approaches. The RSAP design parameters are discussed and the RSAP topology is fully specified. The RSAP problem seeks to find a minimum cost network of disjoint bounded local ring spur partitions interconnected by a tertiary ring.

A survey of literature on survivable telecommunications network design problems and associated technologies and protocols is presented. The RSAP complements well known network optimisation problems such as the SONET Ring Assignment Problem (SRAP) and has similarities to the Ring Star Problem (RSP) and Connected Network Bounded Ring (CNBR) problems.

A survey of literature on related theoretical issues is also presented. Building on existing complexity theory, the RSAP is shown to be NP-hard. An empirical polyhedral study of the RSAP polytope with some theorems and conjectures is given.

Well-grounded theoretical ideas and mathematical models are presented and linked to practical settings by implementing a set of algorithms and a branch-and-cut framework to produce practical results on a set of benchmark data. The thesis describes a cut-and-branch decomposition heuristic algorithm suitable for solving RSAP problem instances in a reasonable time. Two complete IP formulations are also proposed and described in detail. Additional valid inequalities based on modifications of generic inequalities from the literature are described. Specialised inequalities for the RSAP which have broader applicability to network design problems are also given. The separation procedures including a modification to the Stoer Wagner min cut algorithm are described. Min cut algorithms have been described as the bottleneck in polyhedral algorithms, and so are crucial to any effective polyhedral algorithm.

Promising computational results on benchmark data for Survivable Network Designs (SNDs) are presented and analysed. Small problems are solved to optimality using the RSAP algorithms given in the thesis. Solutions on problems of up to 65 nodes are solved but with some optimality gap. These results provide answers to the business community looking for solution topologies for survivable telecommunications network re-designs.

Lastly, the value of our work to the research community interested in the theoretical aspects of our work is outlined. This thesis extends the study of multi-ring network design problems. The RSAP offers much potential for future work.