Invited Session Thu.3.H 3503

Thursday, 15:15 - 16:45 h, Room: H 3503

Cluster 23: Telecommunications & networks [...]

Robust communication networks


Chair: Arie Koster



Thursday, 15:15 - 15:40 h, Room: H 3503, Talk 1

Grit Cla├čen
A branch-and-price approach for the robust wireless network planning

Coauthors: Arie M.c.a. Koster, Anke Schmeink


In this work, we consider the problem of base station location and traffic node assignment in wireless networks. The uncertainty by user behaviour is modelled by the well-known \Gamma-robustness approach by Bertsimas and Sim.
We compare a straightforward ILP with a column generation approach. The default ILP is divided into a restricted master problem and one pricing problem per base station. If a pricing problem finds an assignment variable with negative reduced cost fulfilling the capacity constraints, this variable is added to the restricted master problem. Since the pricing problems are robust knapsack problems, we can apply well-known techniques such as cover inequalities to improve the solving performance. Due to the integrality of all variables, we develop problem specific branching rules leading to a branch-and-price approach. Finally, we present computational results comparing the branch-and-price formulation and the default ILP.



Thursday, 16:15 - 16:40 h, Room: H 3503, Talk 3

Daniel Karch
Fiber replacement scheduling

Coauthors: Andreas Bley, Fabio D'Andreagiovanni


During the operation of large telecommunication networks, it is sometimes necessary to replace components
in a big part of a network. Since a network resource, such as a router or an optical fiber cable, is usually in shared use by several connections, all of these connections will have to be shut down while the component is being replaced.
Since the number of workers that perform the upgrade is limited, not all of the affected
connections can be upgraded at the same time, and disruptions of service cannot be avoided.
Our goal is to schedule the replacement of the fibers in such a way, that the number of workers necessary
in each period of the discretized planning horizon does not exceed the given budget, and the sum of
all connections' disruption times is minimized.
We will present exact mathematical formulations for the problem, discuss its connection to
the linear arrangement problem, and give first results on the hardness of approximation.


  Illinois Payday Loans should not be obtained by people who do not have the capacity to repay the lenders. This pill gives a hand to thousands who suffer from erectile dysfunction. People who take Viagra Super Active can forget about their impotence and have a normal intimate life.