Optimization Models and Methods for Communication Network Design and Routing

Sammanfattning: Many decision problems in communication network planning can be approached by optimization methodologies. In this thesis we study communication network design and routing. Consisting of an introductory part and nine research papers, the thesis deals with optimization models and solution methods for general network design and routing problems as well as technology specific applications.The first three papers consider general network design problems. Papers I-II address capacitated multicommodity network design models with applications in topological design of backbone networks. Paper III considers an access network design problem for locating communication facilities to serve subscribers.The next three papers concern multicommodity flow models that are frequently used in routing applications. In Papers IV-V we extend the classical minimum cost multicommodity flow model by side constraints to address network delay and reliability issues. Paper VI is devoted to the efficient solutions of very large scale multicommodity routing problems.Two specific network design applications are studied in the following two papers. Paper VII addresses optical network design with wavelength division multiplexing, where the design decisions concern not only network topology but also wavelength assignment and routing for every individual demand unit. Paper VIII considers an internet protocol network design problem where routing is operated by specific protocols which do not support classical multicommodity flow distribution.In the thesis we study the structures and characteristics of the above mentioned problems, and develop efficient solution methods using linear, nonlinear, and integer programming techniques. We present a variety of optimization methods, ranging from relaxation and decomposition schemes to branch-and-bound enumeration and heuristics. The results obtained from applying these methods demonstrate the potential benefits of using optimization techniques in communication network design and routing.Paper IX provides an annotated bibliography in communication network design and routing. With more than 600 references, the paper may serve as a valuable tool for exploring the research work which has been conducted on these two topics.