Optimization Tools for Next Generation Telecommunication Networks

March 06, 2013
Austrian Academy of Sciences (Theatersaal, 1st Floor)
Sonnenfelsgasse 19
1010 Vienna, Austria

Workshop Program:

09:00 – 09:15 Welcome

Session 1: Biobjective Optimization (Chair: Markus Leitner)
09:15 – 09:45 Axel Werner, Zuse-Institut Berlin: FTTx network planning with multiple objectives (Abstract)
In the planning of fiber optic access (FTTx) networks, there is the possibility of a mixed FTTH/FTTC deployment, i.e., connecting some customers via fiber-to-the-home, others via DSL technology. We present a variant of the Connected Facility Location (ConFL) Problem that models this choice, the 2-Architecture-ConFL. We give MIP formulations and discuss some theoretical and practical issues. We further show how the latter in fact lead to bi- and multi-objective optimization problems.

Axel Werner, Zuse-Institut Berlin
Michael Kreutz, Zuse-Institut Berlin
Markus Leitner, TU Wien
Ivana Ljubic, Uni Wien
Markus Sinnl, Uni Wien

09:45 – 10:15 Markus Sinnl, Uni Wien: The Biobjective Prize-Collecting Steiner Tree Problem (Abstract)
In this talk, we consider the bi-objective prize collecting Steiner tree problem, whose goal is to find a subtree that minimizes the edge costs for building that tree, on the one hand, and that maximizes the collected node revenues, on the other hand. From a practical perspective, the problem is important, whenever node revenues and edge costs cannot be easily expressed using the same (e.g., monetary) units. The problem can be used to model the design of FTTH networks, but also has uses outside of telecommunication, e.g., in wildlife corridor design.
We present a thorough computational study of five iterative mixed integer programming (MIP) frameworks that identify the complete Pareto front, i.e., one efficient solution for every point on the Pareto front. Furthermore, we investigate methods that exploit information gained in previous iterations to speed up the whole process. More precisely, the studied frameworks build upon branch-and-cut approaches for single-objective variants. These are further enhanced with procedures for: (i) generating feasible solutions, (ii) generating violated cutting planes, and (iii) guiding the branching process. Standard benchmark instances from the literature are used to assess the efficacy of the proposed methods.

Markus Leitner, TU Wien
Ivana Ljubic, Uni Wien
Markus Sinnl, Uni Wien

10:15 – 10:35 Coffee Break

Session 2: Robust Optimization (Chair: Petra Mutzel)
10:35 – 11:00 Grit Claßen, RWTH Aachen: Chance-Constrained Optimization of Reliable Fixed Broadband Wireless Networks (Abstract)
We investigate reliable fixed point-to-point wireless networks under outage probability constraints. Since the performance of microwave links is prone to variations due to external factors, e.g., weather, we introduce a chance-constrained programming approach to determine the optimal bandwidth assignment and routing of traffic demands. The reliability criterion requires that the computed network flows remain feasible with high probability. Furthermore, we present a reformulation to a standard Integer Linear Programming (ILP) model as well as a budget constrained formulation. To improve the solving performance, we propose valid inequalities and a primal heuristic and analyze their effectiveness in a computational study. Finally, the correlation between budget and network reliability is evaluated.

Grit Claßen, RWTH Aachen, Lehrstuhl II für Mathematik
David Coudert, Project-team Mascotte, INRIA Sophia Antipolis
Arie M. C. A. Koster, RWTH Aachen University, Lehrstuhl II für Mathematik
Napoleão Nepomuceno, Universidade de Fortaleza, Programa de Pós-Graduação em Informática Aplicada

11:00 – 11:25 Fabio D’Andreagiovanni, Zuse-Institut Berlin: Multi-band Robust Optimization of Time Offset in Digital Broadcasting Networks (Abstract)
The design of new generation OFDM-based digital audio and video broadcasting networks has introduced novel decision dimensions that add up to classical ones like power emission and antenna diagram. A new design opportunity is in particular given by setting time offset of transmitters: signal emissions of distinct transmitters can indeed be coordinated in time, in order to reduce mutual interference and enhance service quality. In this work, we focus our attention on the problem of setting the time offset of each transmitter of a broadcasting network, in order to maximize coverage while meeting quality of service requirements. Though its solution would sensibly increase network performance, this optimization problem is typically neglected in real network deployments, since it results too complicated to tackle by the trial-and-error design approach (still surprisingly) adopted by network engineers. We present the first compact formulation for the problem and derive a family of valid inequalities to strengthen the basic formulation. We then define a Robust Counterpart for the nominal problem, by considering the time uncertainty that naturally affects signal propagation in a real environment. Such Robust Counterpart is defined according to the new Multi-band Uncertainty paradigm (Büsing and D’Andreagiovanni, 2012, arXiv:1301.2734). The performance of the models is assessed through computational experiments on realistic network instances.

Christina Büsing, RWTH Aachen
Fabio D’Andreagiovanni, Department of Optimization, Zuse-Institut Berlin and Department of Computer, Control, and Management Engineering, Sapienza Università di Roma

11:25 – 11:50 Daniel Schmidt, Uni Köln: Single-Commodity Network Design with Uncertain Demands (Abstract)
We present a single-commodity robust network design model with dynamic routing. The model is meant as an intermediate step between deterministic minimum cost flows and multi-commodity network loading. It has the benefit of allowing for a polynomial time separable capacity based IP formulation while still being realistic. Based on this formulation, we show a branch-and-cut algorithm and introduce two heuristic separation routines for 3-partition inequalities. The algorithm undergoes experimental evaluation.

Valentina Cacchiani, University of Bologna
Michael Jünger, Universität zu Köln
Frauke Liers, Universität Erlangen-Nürnberg
Andrea Lodi, University of Bologna
Daniel Schmidt, Universität zu Köln
11:50 – 12:15 Valentina Cacchiani, Uni Bologna: A Heuristic Algorithm for Single-Commodity Network Design with Uncertain Demands (Abstract)
We study a single-commodity Robust Network Design (RND) problem with dynamic routing. We present complexity results on special classes of instances including hypercubes. We propose a heuristic algorithm for RND, which consists of two phases: in the first phase a feasible solution is built, and in the second one it is improved through neighborhood search. The second phase is based on an Integer Linear Programming flow formulation for RND on a reduced graph. The heuristic is tested on instances generated on random graphs and compared to Cplex.
Eduardo Álvarez-Miranda, University of Bologna
Valentina Cacchiani, University of Bologna
Andrea Lodi, University of Bologna
Tiziano Parriani, University of Bologna
Daniel R. Schmidt, Universität zu Köln

12:15 – 13:45 Lunch Break

Invited Talk (Chair: Ivana Ljubic)
13:45 – 14:45 Martin Grötschel, Zuse-Institut and TU Berlin: Telecom Network Design: A review of the past quarter century (Abstract)
My involvement in telecommunication optimization problems started about a quarter century ago. I will review in my lecture the development of models for telecom network design and of approaches for their solution over this time period. Due to technological (r)evolutions, shifts in the cost structures, and customer demands the optimization models are subject to continual change. All aspects become more and more complex. There is no end in sight and significant challenges for the optimization technology (theory and computational practice) are ahead of us.

14:45 – 15:00 Coffee Break

Session 3: Miscellaneous Applications (Chair: Immanuel Bomze)
15:00 – 15:25 Luis Gouveia, Uni Lisbon: Models for optimal survivable routing with a minimum number of hops (Abstract)
Given an undirected network with link capacities and a set of commodities with known demands, this talk addresses the problem of determining D (with D=2, 3, 4) hop-constrained node disjoint paths for each commodity while minimizing the average or the maximum number of hops. These paths are defined according to two survivability mechanisms - Path Diversity and Path Protection, the latter guaranteeing total demand protection in the event of n failures (with n<D). We study these problems in the context of a traffic engineering task over pre-dimensioned networks where the real traffic demands are inevitably different from the estimated traffic demands that were assumed in the network dimensioning task. We present two classes of ILP models, disaggregated and aggregated, for both problems, study the relationship between their linear programming relaxations and compare their effectiveness through a set of computational experiments. The results show that, in practice, there is no gain in using the disaggregated models.

Luis Gouveia, Universidade de Lisboa, Portugal
Pedro Patricio, Universidade da Beira Interior, Portugal
Amaro de Sousa, Universidade de Aveiro, Portugal

15:25 – 15:50 Andreas Bley, TU Berlin: Upgrading a network with minimum disturbance (Abstract)
We consider the problem of scheduling the upgrade of the WDM transmission technology on the links of a fiber optic communication network in such a way that the disruption of existing services is minimized.Given an optical network consisting of fiber links and switching nodes, unprotected and protected virtual connections of single paths or pairs of disjoint paths, respectively, and a discretized planning horizon, the task is to decide when to replace the technology of each link. Replacing a link requires several technicians at the repeaters and terminal nodes of this link. The number of technicians available per period is limited. Since the old and the new technology are incompatible, a path will be non-operational from the period its first link is replaced until all its links are replaced, which leads to the disruption of the corresponding virtual connections. An unprotected virtual connection is disrupted when its only path is non-operational. A protected virtual connection is non-operational when both its paths are non-operational, while it is operational but unprotected when only one paths is operational. The objective is to minimize the overall time that virtual connections are disrupted or unprotected. We present an integer linear programming formulation for this problem, discuss its relation to the linear arrangement problem and the complexity of some special cases, and finally report on computational results for some real world instances.

Andreas Bley, Department of Mathematics, TU Berlin
Daniel Karch, Department of Mathematics, TU Berlin
Fabio D’Andreagiovanni, Department of Optimization, Zuse Institute Berlin

15:50 – 16:15 Mario Ruthmair, TU Wien: Network Design with Delay and Delay-Variation Constraints (Abstract)
We present mixed integer programming (MIP) approaches for solving a combinatorial optimization problem arising in network design with additional quality of service constraints. The rooted delay- and delay-variation-constrained Steiner tree problem asks for a cost-minimal Steiner tree satisfying delay constraints from source to terminals and a maximal variation bound between particular terminal path-delays. Our MIP models are based on multi-commodity flows and a layered graph transformation, respectively. For the latter model we propose some new sets of valid inequalities and an efficient separation method. Finally, we discuss some future work based on variable splitting and decomposition.

Günther Raidl, TU Wien
Mario Ruthmair, TU Wien

16:15 – 16:40 Christina Büsing, RWTH Aachen: Solving the recoverable robust knapsack problem with Gamma-Scenarios (Abstract)
In this talk I will present a recoverable robust knapsack problem, where the uncertainty of the item weights follows the approach of Bertsimas and Sim. In contrast to the classical robust setting, a limited recovery action is allowed, i.e., up to k items may be removed when the actual weights are known. This problem is motivated by the assignment of traffic nodes to antennas in wireless network planning and the bandwidth packing problem from telecommunication. I will introduce several algorithms based on an integer linear programming formulation, different robustness cuts and robust extended cover inequalities and compare their run-time w.r.t. the recovery action and the scenario set.

Christina Büsing, RWTH Aachen
Sebastian Goderbauer, RWTH Aachen
Arie Koster, RWTH Aachen
Manuel Kutschka, RWTH Aachen

16:40 – 17:00 Coffee Break

Session 4: Industry Applications (Chair: Günther Raidl)
17:00 – 17:25 Markus Prossegger, FH Kärnten, Generating high quality graphs that represent the real world (Abstract)
Most of the optimization tools for telecommunication networks rely on weighted graphs, representing spatial objects as well as infrastructure data of the project regions. Next to the consideration of strategic, technical, regulatory and legal constraints in the graph generation process, especially the number of vertices and edges in the resulting graph determines its applicability. Furthermore, the quality of the graph is determined by the inclusion of all economically reasonable routing combinations and the correct assignment of routing and royalty costs. We present the challenges of using spatial data originating from hybrid sources featuring different levels of quality. The process of preprocessing the spatial data followed by the generation and weighting of a graph is presented using data from a recent telecommunication project.

Markus Prossegger, FH Kärnten

17:25 – 17:50 Andreas Chwatal, Destion, Wien: Fiber-Network Planning in Austria — Challenges and Achievements (Abstract)
Implementing successful commercial operations research solutions requires, besides the solution of the underlying optimization problem, the consideration of various further issues like user acceptance, product lifecycle, data quality, integration, and many others. In addition the possibility of changing requirements asks for robust models and algorithms. Motivated by recent developments in a telecommunications project I will cover these issues from a practicioners perspective. Moreover, parts of the given problem will be presented together with general considerations regarding modelling and algorithmic tradeoffs.

Andreas Chwatal, Destion, Wien
Sandro Pirkwieser, Destion, Wien

17:50 – 18:15 Roland Wessäly, Atesio, Berlin: Cost optimized optical fiber access network design (Abstract)
In this talk we will provide a short introduction into fiber access network design from a practical perspective. We will talk about methods practically used – at Deutsche Telekom and by several municipalities in Germany – to assess and optimize the infrastructure cost for a planning area. Finally, we will elaborate on some key issues to boost the business case of a network operator from the planning side.

Roland Wessäly, Atesio, Berlin

18:15 – 18:40 Discussion: Future Trends (Moderation: Roland Wessäly)

18:40 Oliver Fabel (Dean of the Faculty of Business, Economics, and Statistics, Uni Wien)

19:30 Workshop Dinner DETAILS

The workshop dinner will take place at the Zwölfapostel Keller (Twelve-apostle’s cellar).
Please REGISTER HERE if you plan to attend the dinner.

Sponsored by:
Alumni Verein der Österreichischen Akademie der Wissenschaften
Faculty of Business, Economics, and Statistics, University of Vienna

Organized by:
Ivana Ljubic, Uni Wien
Markus Leitner, TU Wien & Uni Wien