Advancing robust optimization methodologies to foster energy efficiency in future wireless networks
Final Report Abstract
In this project, we have investigated several robust optimization approaches to improve the energy efficiency in cellular wireless networks which are subject to uncertainty. Uncertainties occur quite frequently in radio networks as, for instance, the quality of the transmission signal varies or user demands fluctuate. The investigated mathematical optimization approaches which are able to tackle such deviations comprise chance constraints (a more general but less tractable concept), Γ-robustness, multi-band robustness, and the two-stage approach recoverable robustness. While chance constraints are suitable in case that the uncertain data obeys a previously known probability distribution, the robust optimization approaches are able to handle uncertain data which can be modeled by a so-called uncertainty set constructed, e.g., from historical information. One reason for the popularity of robust optimization is that the theoretical complexity of the original problem is not increased by the incorporation of uncertainty. We have developed miscellaneous (linear) formulations based on chance constraints to obtain reliable fixed broadband wireless networks as preparatory work. We then have applied all three robustness concepts to the planning problem of energy-efficient cellular wireless networks and proposed ILP formulations for each robust problem. For the Γ-robust WNPP, we have additionally developed valid inequalities and evaluated the so-called price of robustness revealing energy savings either by deploying less BSs or serving more users with the same amount of energy. Moreover, we have proposed an alternative formulation via a complete branch-and-price framework including problem specific branching rules and several performance improvements. As the KP, which is one of the most fundamental combinatorial problems, is a subproblem of the WNPP, we have studied the multi-band robust KP theoretically and derived new complexity results via dynamic programming algorithms. A numerical evaluation showed that the improved dynamic program outperforms the compact ILP formulation. Due to these convincing results, we have solved the two-band robust user assignment problem by this algorithm in a Lagrangian relaxation. Additionally, we have incorporated recoverable robustness via discrete scenario sets to the WNPP to model the option of switching base stations off during low traffic times. A computational study has demonstrated energy savings by switching up to three BSs off during the night. In our last work package, we have developed novel approximate as well as exact approaches and discussed modifications of existing formulations to model interference in the WNPP. The most promising models are two exact formulations, one from a user’s point of view and the other one exploits discrete channel quality values. This part of the project has additionally revealed a great potential for future research topics as intended in our follow-up proposal.
Publications
-
A Robust Optimisation Model and Cutting Planes for the Planning of Energy-Efficient Wireless Networks. Computers and Operations Research, 40 (1): 80–90, January 2013
G. Claßen, A.M.C.A. Koster, and A. Schmeink
-
Speeding up column generation for robust wireless network planning. EURO Journal on Computational Optimization, 1 (3-4): 253–281, 2013
G. Claßen, A.M.C.A. Koster, and A. Schmeink
-
Chance-Constrained Optimization of Reliable Fixed Broadband Wireless Networks. INFORMS Journal on Computing, 26 (4): 893–909, 2014
G. Claßen, D. Coudert, A.M.C.A. Koster, and N. Nepomuceno
-
Optimisation under Data Uncertainty in Wireless Communication Networks PhD thesis, RWTH Aachen University, 2015
G. Claßen
