Optimization models and methods for telecommunication network design with varying and uncertain demands
Final Report Abstract
The construction of modern telecommunication networks requires an extended period of time, usually in the range of years, and hence has to be planned in multiple periods. During this time, economic prerequisites are subject to changes, a fact that must be taken into account in the planning phase. This introduces an uncertainty aspect for the parameters that determine the input to the mathematical models used for addressing the network design problem. In the project, models and methods were developed to cope with the long-term aspect as well as the resulting uncertainty in the planning problem. For long time horizons, mathematical models tend to get large and are therefore hard to solve by general algorithms. Hence it is important to develop suitable special algorithms to efficiently use these models. In particular, primal methods (which quickly compute possible solutions) and dual methods (which, when possible, ascertain optimality of found solutions) were the focus of our research. For the model developed early in the project, which covers realistic long-term scenarios, a successful dual method was devised, which is based on the well-known Lagrange duality theory. The necessary computations for the algorithm can be carried out quickly, due to a simple characterization of the dual optimum, and this leads to better dual bounds than using the general methods of state-of-the-art solvers. By considering a very special case of the general problem, an extension of the classical Knapsack Problem can be studied. Furthermore, for a generalization of the original model, an efficient primal method was obtained, which is surprisingly simple, but provides already much better solutions than a commercial solver, as test computations suggest. Introducing the uncertainty aspect complicates models even further. This is because the description of those possible solutions to the model that are robust against any uncertain input data (i.e., that are still feasible when the input data changes in a controlled way) requires new restrictions that have to be satisfied by the variables of the model. At the same time, this adds more structure to the problem, which can be exploited when designing primal solution methods. This was done for the multiperiod problem considered in the project, where certain other assumptions were taken, following the expertise of our Polish partners. The resulting algorithm, which makes use of various mathematical techniques such as duality, total unimodularity, randomized rounding, and shortest paths, manages to find much better solutions than the state-of-the-art commercial solver CPLEX; the corresponding paper won the Best Paper Award at the EvoComNet 2014 conference. Test computations were carried out using examples of real-world networks throughout, as provided by the SNDlib, a library of telecommunication networks that is widely used both by practitioners and in academia.
Publications
-
The multiperiod network design problem: Lagrangianbased solution approaches. Technical report, ZIB, Takustr. 7, 14195 Berlin, 2011. ZIB Report 11-31
A. Giovanidis and J. Pulaj
-
Models for network design under varied demand structures. 21st International Symposium on Mathematical Programming (ISMP) 2012, Berlin
J. Pulaj
-
A Hybrid Heuristic for Robust Multiperiod Network Design. Presentation at the 12th INFORMS Telecommunications Conference 2014, Lisboa
J. Pulaj
-
A hybrid primal heuristic for robust multiperiod network design. In A. I. Esparcia-Alcazar and A. M. Mora, editors, Applications of Evolutionary Computation, pages 15–26. Springer Verlag, 2014. Winner of the Evostar-EvoComNet Best Paper Award 2014. ZIB Report 13-78
F. D’Andreagiovanni, J. Krolikowski, and J. Pulaj
-
A fast hybrid primal heuristic for multiband robust capacitated network design with multiple time periods. Applied Soft Computing, 26:497–507, 2015. ZIB Report 14-40
F. D’Andreagiovanni, J. Krolikowski, and J. Pulaj
