Optimisation under Data Uncertainty in Wireless Communication Networks

In this thesis, we study robustness concepts of mathematical optimisation and apply these to wireless network problems which are subject to data uncertainty. Uncertainties occur quite frequently in radio networks as, for instance, the quality of the transmission signal varies or user demands fluctuate. Robust and stochastic optimisation are two methodologies to tackle such deviations already in the planning phase of the network. While stochastic optimisation is a suitable technique in case that the uncertain data obeys a previously known probability distribution, robust optimisation is able to handle uncertain data which can be modelled by a so-called uncertainty set, which may, e.g., be constructed from historical information. One reason for the popularity of robust optimisation is that the theoretical complexity of the original problem is not increased by the incorporation of uncertainty. We investigate one specific area of stochastic optimisation, chance constraints, which are related to robust optimisation, and three robustness concepts. These concepts comprise Γ-robustness, the more general multi-band robustness, and the two-stage approach recoverable robustness.For reliable fixed broadband wireless networks, we develop miscellaneous (linear) formulations based on chance constraints and propose performance improvements such as valid inequalities and a primal heuristic. Furthermore, we apply all three robustness concepts to the planning problem of mobile wireless networks and propose integer linear programming formulations for each robust problem. For the Γ-robust wireless network planning problem (WNPP), we additionally develop valid inequalities and an alternative formulation via a complete branch-and-price framework. Since the knapsack problem (KP), which is one of the most fundamental combinatorial problems, is a subproblem of the WNPP, we study the multi-band robust KP theoretically and derive new complexity results via a dynamic programming algorithm. To apply this algorithm to a variant of the multi-band robust WNPP, we adopt Lagrangian relaxation. Additionally, we incorporate recoverable robustness to the WNPP to model the option of switching base stations off during low traffic times. Furthermore, to obtain a full description of mobile wireless networks, we develop novel approaches and discuss modifications of existing formulations to model interference in the WNPP. All theoretical investigations are supported by several extensive computational studies performed on realistic test instances. Moreover, we compare the two different formulations of the Γ-robust WNPP and Γ-robust to multi-band robust solutions via a numerical evaluation. Finally, we discuss the interpretation of computational studies critically based on the so-called performance variability which is intrinsic to mixed integer linear programs. We conclude by final remarks on the investigated robustness concepts and present future research topics