# Design and Operation of Traffic and Telecommunication Networks

## Winter Semester 2015

LV-Nr.: 19225301

Dr. Fabio d'Andreagiovanni     Prof. Dr. Ralf Borndörfer,     Jonad Pulaj

### Content

Network-based infrastructures have deeply pervaded our everyday life. Two major examples are transport and telecommunications networks, which have become an essential part of every modern metropolis. Over the last years, these networks have grown in size and complexity and their design and networks have grown in size and complexity and their design and operation has gone beyond the capacity of traditional planning by experience-based approaches that have traditionally been adopted by industry professionals. The need for more analytical and rigorous network design approaches has been satisfied by Mathematical Optimization, which nowadays provides powerful optimization methods that help to cut costs, improve the quality of service, and increase the robustness of our infrastructure.

Ths course provides an introduction to modern mathematical optimization techniques for network design and operation. The goal is to convey the capabilities to model, analyze, and solve such problems. We will study several important types of network problems and the most common models associated with them. We will analyze their complexity and investigate the quality of these models, their combinatorial structure, and learn about exact, heuristic, and approximative algorithms for their solution. A focus of this course is the application of these results in the tutorials using mathematical optimization software.

The course will cover the following topics.

Problems: median problems, stop location problems, set covering problem, coloring problems, facility location problems, network interdiction problems, spanning trees, Steiner tree problem, Steiner connectivity problem, k-connectivity problem, periodic event scheduling problem, coloring problems.

Mathematical methods: greedy algorithm, primal-dual (approximation) algorithms, linear and integer programming, local search, polyhedral combinatorics, network flows, Menger theorem, Japanese theorem, column generation, Bertsimas Sim method, robust optimization, and multiband robustness.

Applications: network desigh, line planning, timetabling, toll enforcement, and frequency assignment.

### Prerequisites

Disrete Mathematics I or similar knowledge, linear and integer programming is advantageous but not necessary.

### Hours

The is an integrated course of 4+2 SWH..

### Credits

The course is classified as an Ergänzungsmodul Ausgewählte Forschungsthemen at FU Berlin and as an Advanced Course of the Berlin Mathematical School in Teaching Area 4.

### Certificate

The criteria for the certificates are (i) the successful participation in the tutorials, (ii) 50% of points in the homeworks, (iii) to pass the exam.

### Exam

The exam takes place in the last lecture on 11.02.16, 16:00-18:00, in the usual lecture room SR 007/008, Arnimallee 6. The review takes place on Wednesday, 17.02.16, 14:00-16:00, in room R 3034 on the first floor of ZIB. The 2nd exam will take place at the time of the lecture on Th 14.04.16, 16:00-18:00, in a room TBA.

### Location and Timing

 Tutorial Mo 12-14 SR 005 (A3) Lecture Tu 16-18 SR 005 (A3) Lecture Th 16-18 SR 007/008 (A6)

### Remarks

This course is in English.

### Material

Mathematical optimization software:

### Contact

 Office hours Room Phone Email Prof. Dr. Ralf Borndörfer by appointment ZIB 84185-243 borndoerferzib.de Dr. Fabio d'Andreagiovanni by appointment ZIB 84185- d.andreagiovannizib.de Jonad Pulaj by appointment ZIB 84185- pulajzib.de

Last changed: 03.03.2016