TY - GEN A1 - Orlowski, Sebastian A1 - Wessäly, Roland T1 - An Integer Programming Model for Multi-Layer Network Design N2 - We present an integer linear programming model for the design of multi-layer telecommunication networks. The formulation integrates hardware, capacity, routing, and grooming decisions in \emph{any} n umber of network layers. Practical hardware restrictions and cost can accurately be taken into account for technologies based on connection-oriented routing protocols. T3 - ZIB-Report - 04-49 KW - multi-layer networks KW - integer programming KW - network design KW - routing KW - grooming Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8248 ER - TY - GEN A1 - Orlowski, Sebastian A1 - Wessäly, Roland T1 - Comparing Restoration Concepts using Optimal Network Configurations with Integrated Hardware and Routing Decisions N2 - We investigate the impact of link and path restoration on the cost of telecommunication networks. The surprising result is the following: the cost of an optimal network configuration is almost independent of the restoration concept if (i) the installation of network elements (ADMs, DXCs, or routers) and interface cards, (ii) link capacities, and (iii) working and restoration routings are simultaneously optimized. We present a mixed-integer programming model which integrates all these decisions. Using a branch-and-cut algorithm (with column generation to deal with all potential routing paths), we solve structurally different real-world problem instances and show that the cost of optimal solutions is almost independent of the used restoration concept. In addition, we optimize spare capacities for given shortest working paths which are predetermined with respect to different link metrics. In comparison to simultaneous optimization of working and restoration routings, it turns out that this approach does not allow to obtain predictably good results. T3 - ZIB-Report - 03-09 KW - survivable network design KW - link and path restoration KW - hardware configuration KW - branch-and-cut algorithm KW - routing Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7316 ER - TY - GEN A1 - Koster, Arie M.C.A. A1 - Zymolka, Adrian A1 - Jäger, Monika A1 - Hülsermann, Ralf A1 - Gerlach, Christoph T1 - Demand-wise Shared Protection for Meshed Optical Networks N2 - In this paper, a new shared protection mechanism for meshed optical networks is presented. Significant network design cost reductions can be achieved in comparison to the well-known 1+1 protection scheme. Demand-wise Shared Protection (DSP) bases on the diversification of demand routings and exploits the network connectivity to restrict the number of backup lightpaths needed to provide the desired level of prorection. Computational experiments approve the benefits of the concept DSP for cost efficient optical network designs. T3 - ZIB-Report - 03-24 KW - optical network design KW - shared protection KW - meshed optical networks KW - diversification Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7461 ER - TY - GEN A1 - Orlowski, Sebastian A1 - Wessäly, Roland T1 - The Effect of Hop Limits on Optimal Cost in Survivable Network Design N2 - We investigate the impact of hop-limited routing paths on the total cost of a telecommunication network. For different survivability settings (dedicated protection, link and path restoration), the optimal network cost without restrictions on the admissible path set is compared to the results obtained with two strategies to impose hop limits on routing paths. In a thorough computational study on optimal solutions for nine real-world based problem instances, we show that hop limits should be avoided if the technology allows it and network cost is a major planning issue. In this case, column generation should be employed to deal with all routing paths. If hop-limits are required, these should be defined for each demand individually and as large as possible. T3 - ZIB-Report - 04-23 KW - survivable network design KW - hop limits KW - routing KW - restoration KW - branch-and-cut algorithm KW - mixed-integer programming Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7980 ER - TY - GEN A1 - Kröller, Alexander A1 - Wessäly, Roland T1 - Integrated Optimization of Hardware Configuration and Capacity. Dimensioning in SDH and opaque WDM networks N2 - We suggest a new model for the design of telecommunication networks which integrates decisions about the topology, configuration of the switching hardware, link dimensioning, and protected routing of communication demands. Applying the branch-and-cut-algorithm implemented in our network planning and optimization tool DISCNET, we demonstrate that real-world based network planning instances of such an enhanced model can be solved. T3 - ZIB-Report - 03-49 KW - Survivable Network Design KW - Integer Programming KW - Hardware Configuration KW - Routing KW - Network Models KW - Network Planning KW - Resource Allocation KW - Surviva Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7714 ER - TY - GEN A1 - Bley, Andreas A1 - Koch, Thorsten A1 - Wessäly, Roland T1 - Large-scale hierarchical networks: How to compute an optimal architecture? N2 - In this article, we present a mathematical model and an algorithm to support one of the central strategic planning decisions of network operators: How to organize a large number of locations into a hierarchical network? We propose a solution approach that is based on mixed-integer programming and Lagrangian relaxation techniques. As major advantage, our approach provides not only solutions but also worst-case quality guarantees. Real-world scenarios with more than 750 locations have been solved within 30 minutes to less than 1\% off optimality. T3 - ZIB-Report - 04-04 KW - Hierarchical Networks KW - Mixed-Integer Programming KW - Lagrangian Relaxation Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7799 ER - TY - GEN A1 - Koster, Arie M.C.A. A1 - Zymolka, Adrian T1 - Minimum Converter Wavelength Assignment in All-Optical Networks N2 - Finding conflict-free wavelength assignments with a minimum number of required conversions for a routing of the lightpaths is one of the important tasks within the design of all-optical networks. We consider this problem in multi-fiber networks with different types of WDM systems. We give a detailed description of the problem and derive its theoretical complexity. For practical application, we propose several sequential algorithms to compute appropriate wavelength assignments. We also perform computational experiments to evaluate their performance. For the iterative algorithms, we identify characteristic patterns of progression. Two of these algorithms qualify for application in practice. T3 - ZIB-Report - 03-45 KW - minimum converter wavelength assignment KW - optical networks KW - generalized coloring KW - complexity KW - heuristics Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7673 ER - TY - GEN A1 - Orlowski, Sebastian A1 - Pióro, Michal T1 - On the complexity of column generation in survivable network design with path-based survivability mechanisms N2 - This survey concerns optimization problems arising in the design of survivable communication networks. It turns out that such problems can be modeled in a natural way as non-compact linear programming formulations based on multicommodity flow network models. These non-compact formulations involve an exponential number of path flow variables, and therefore require column generation to be solved to optimality. We consider several path-based survivability mechanisms and present results, both known and new, on the complexity of the corresponding column generation problems (called the pricing problems). We discuss results for the case of the single link (or node) failures scenarios, and extend the considerations to multiple link failures. Further, we classify the design problems corresponding to different survivability mechanisms according to the structure of their pricing problem. Finally, we show that almost all encountered pricing problems are hard to solve for scenarios admitting multiple failures. T3 - ZIB-Report - 08-51 KW - Netzplanung KW - Dimensionierung KW - Spaltengenerierung KW - Mehrfachausfälle KW - survivable network design KW - routing KW - column generation KW - pricing KW - complexity Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11058 SN - 1438-0064 ER - TY - GEN A1 - Gruber, Claus G. A1 - Koster, Arie M.C.A. A1 - Orlowski, Sebastian A1 - Wessäly, Roland A1 - Zymolka, Adrian T1 - A new model and a computational study for Demand-wise Shared Protection N2 - This report combines the contributions to INOC 2005 (Wessälly et al., 2005) and DRCN 2005 (Gruber et al., 2005). A new integer linear programming model for the end-to-end survivability concept deman d-wise shared protection (DSP) is presented. DSP is based on the idea that backup capacity is dedicated to a particular demand, but shared within a demand. It combines advantages of dedicated and shared protection: It is more cost-efficient than dedicated protection and operationally easier than shared protection. In a previous model for DSP, the number of working and backup paths to be configured for a particular demand has been an input parameter; in the more general model for DSP investigated in this paper, this value is part of the decisions to take. To use the new DSP model algorithmically, we suggest a branch-and-cut approach which employs a column generation procedure to deal with the exponential number of routing variables. A computational study to compare the new resilience mechanism DSP with dedicated and shared path protection is performed. The results for five realistic network planning scenarios reveal that the best solutions for DSP are on average 15\% percent better than the corresponding 1+1 dedicated path protection solutions, and only 15\% percent worse than shared path protection. T3 - ZIB-Report - 05-55 KW - demand-wise shared protection KW - resilience KW - network design KW - integer linear programming Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8880 ER - TY - GEN A1 - Grötschel, Martin T1 - Frequency Assignment in Mobile Phone Systems N2 - Wireless communication networks employ radio frequencies to establish communication links. The available radio spectrum is very limited. To meet today's radio communication demand, this resource has to be administered and reused carefully in order to control mutual interference. The reuse can be organized via separation in space, time, or frequency, for example. The problem, therefore, arises to distribute frequencies to links in a ``reasonable manner''. This is the basic form of the frequency assignment problem. What ``reasonable'' means, how to quantify this measure of quality, which technical side constraints to consider cannot be answered in general. The exact specification of this task and its mathematical model depend heavily on the particular application considered. In this paper we discuss this issue with respect to the GSM standard for mobile communication. T3 - ZIB-Report - 00-58 KW - frequency assignment KW - telecommunication KW - mobile phone KW - integer programming KW - coloring Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6265 ER -