@misc{BleyKosterKroelleretal., author = {Bley, Andreas and Koster, Arie M.C.A. and Kr{\"o}ller, Alexander and Wess{\"a}ly, Roland and Zymolka, Adrian}, title = {Kosten- und Qualit{\"a}tsoptimierung in Kommunikationsnetzen}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7537}, number = {03-31}, abstract = {Der scharfe Wettbewerb innerhalb der Telekommunikationsbranche zwingt die Netzbetreiber dazu, ihre Investitionen genau zu planen und immer wieder Einsparungsmanahmen durchzuf{\"u}hren. Gleichzeitig ist es jedoch wichtig, die Qualit{\"a}t der angebotenen Dienste zu verbessern, um neue Kunden zu gewinnen und langfristig an sich zu binden. Die mathematische Optimierung bietet sich f{\"u}r viele solcher Aufgabenstellungen als hervorragend geeignetes Planungswerkzeug an. Ziel dieses Artikels ist es, ihre Methodik und ihre Anwendung speziell zur Kosten- und Qualit{\"a}tsoptimierung in Kommunikationsnetzen vorzustellen. Anhand von vier konkreten Planungsaufgaben aus dem Bereich der Festnetzplanung wird aufgezeigt, wie sich komplexe Zusammenh{\"a}nge in flexiblen mathematischen Modellen abbilden lassen und welche Verfahren zur automatisierten Bearbeitung der Probleme eingesetzt werden k{\"o}nnen. Die hier vorgestellten Methoden zeichnen sich insbesondere dadurch aus, dass sie neben hochwertigen L{\"o}sungen auch eine Qualittsgarantie liefern, mit der sich die Lsungen fundiert bewerten lassen. Die dokumentierten Ergebnisse aus verschiedenen Industrieprojekten belegen die Eignung und G{\"u}te der mathematischen Optimierung f{\"u}r die Praxis.}, language = {de} } @misc{BodlaenderKoster, author = {Bodlaender, Hans L. and Koster, Arie M.C.A.}, title = {Safe separators for treewidth}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7544}, number = {03-32}, abstract = {A set of vertices \$S\subseteq V\$ is called a safe separator for treewidth, if \$S\$ is a separator of \$G\$, and the treewidth of \$G\$ equals the maximum of the treewidth over all connected components \$W\$ of \$G-S\$ of the graph, obtained by making \$S\$ a clique in the subgraph of \$G\$, induced by \$W\cup S\$. We show that such safe separators are a very powerful tool for preprocessing graphs when we want to compute their treewidth. We give several sufficient conditions for separators to be safe, allowing such separators, if existing, to be found in polynomial time. In particular, every minimal separator of size one or two is safe, every minimal separator of size three that does not split off a component with only one vertex is safe, and every minimal separator that is an almost clique is safe; an almost clique is a set of vertices \$W\$ such that there is a \$v\in W\$ with \$W-\{v\}\$ a clique. We report on experiments that show significant reductions of instance sizes for graphs from proba! bilistic networks and frequency assignment.}, language = {en} } @misc{KosterZymolka, author = {Koster, Arie M.C.A. and Zymolka, Adrian}, title = {Polyhedral Investigations on Stable Multi-Sets}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7324}, number = {03-10}, abstract = {Stable multi-sets are an evident generalization of the well-known stable sets. As integer programs, they constitute a general structure which allows for a wide applicability of the results. Moreover, the study of stable multi-sets provides new insights to well-known properties of stable sets. In this paper, we continue our investigations started in [{\sl Koster and Zymolka 2002}] and present results of three types: on the relation to other combinatorial problems, on the polyhedral structure of the stable multi-set polytope, and on the computational impact of the polyhedral results. First of all, we embed stable multi-sets in a framework of generalized set packing problems and point out several relations. The second part discusses properties of the stable multi-set polytope. We show that the vertices of the linear relaxation are half integer and have a special structure. Moreover, we strengthen the conditions for cycle inequalities to be facet defining, show that the separation problem for these inequalities is polynomial time solvable, and discuss the impact of chords in cycles. The last result allows to interpret cliques as cycles with many chords. The paper is completed with a computational study to the practical importance of the cycle inequalities. The computations show that the performance of state-of-the-art integer programming solvers can be improved significantly by including these inequalities.}, language = {en} } @misc{KosterZymolkaJaegeretal., author = {Koster, Arie M.C.A. and Zymolka, Adrian and J{\"a}ger, Monika and H{\"u}lsermann, Ralf and Gerlach, Christoph}, title = {Demand-wise Shared Protection for Meshed Optical Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7461}, number = {03-24}, abstract = {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.}, language = {en} } @misc{KosterZymolka, author = {Koster, Arie M.C.A. and Zymolka, Adrian}, title = {Minimum Converter Wavelength Assignment in All-Optical Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7673}, number = {03-45}, abstract = {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.}, language = {en} } @misc{EisenblaetterGroetschelKoster, author = {Eisenbl{\"a}tter, Andreas and Gr{\"o}tschel, Martin and Koster, Arie M.C.A.}, title = {Frequenzplanung im Mobilfunk}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6762}, number = {02-09}, abstract = {Telekommunikation ist seit Jahren \glqq in\grqq. Zun{\"a}chst gab es einen enormen Aufschwung; neue Technologien und Dienste haben eine {\"u}berw{\"a}ltigende, nicht vorhersehbare Akzeptanz gefunden. Derzeit ist -- ausgel{\"o}st durch die UMTS-Lizenzversteigerungen, Rezessions- und S{\"a}ttigungstendenzen -- eine Krise zu verzeichnen. Viele (auch wir) sind davon {\"u}berzeugt, dass technischer Fortschritt und n{\"u}tzliche Dienste demn{\"a}chst die Stimmung wieder {\"a}ndern werden. Wenigen ist allerdings bewusst, welche Rolle Mathematik bei der Entwicklung und dem effizienten Einsatz vieler der neuen Kommunikationstechnologien spielt. In diesem Artikel soll kein {\"U}berblick {\"u}ber diesen umfangreichen Themenkreis gegeben werden. Wir zeigen lediglich an einem konkreten Beispiel aus dem Mobilfunk, der Frequenzplanung in GSM-Funknetzen, was man durch geeignete Modellierung der praktischen Fragestellung und den Einsatz problemad{\"a}quater Algorithmen erreichen kann.}, language = {de} } @misc{ZymolkaKosterWessaely, author = {Zymolka, Adrian and Koster, Arie M.C.A. and Wess{\"a}ly, Roland}, title = {Transparent optical network design with sparse wavelength conversion}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7017}, number = {02-34}, abstract = {We consider the design of transparent optical networks from a practical perspective. Network operators aim at satisfying the communication demands at minimum cost. Such an optimization involves three interdependent planning issues: the dimensioning of the physical topology, the routing of lightpaths, and the wavelength assignment. Further topics include the reliability of the configuration and sparse wavelength conversion for efficient use of the capacities. In this paper, we investigate this extensive optical network design task. Using a flexible device-based model, we present an integer programming formulation that supports greenfield planning as well as expansion planning on top of an existing network. As solution method, we propose a suitable decomposition approach that separates the wavelength assignment from the dimensioning and routing. Our method in particular provides a lower bound on the total cost which allows to rate the solution quality. Computational experiments on realistic networks approve the solution approach to be appropriate.}, language = {en} } @misc{EisenblaetterFuegenschuhKochetal., author = {Eisenbl{\"a}tter, Andreas and F{\"u}genschuh, Armin and Koch, Thorsten and Koster, Arie M.C.A. and Martin, Alexander and Pfender, Tobias and Wegel, Oliver and Wess{\"a}ly, Roland}, title = {Modelling Feasible Network Configurations for UMTS}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6837}, number = {02-16}, abstract = {A model for the optimisation of the location and configuration of base stations in a UMTS network is described. The focus is primarily on modelling the configuration problem sufficiently accurate using mixed-integer variables and (essentially) linear constraints. These constraints reflect the limited downlink code capacity in each cell, the interference limitations for successful up- and downlink transmissions, the need for sufficiently strong (cell) pilot signals, and the potential gain for mobiles from being in soft(er) hand-over. It is also explained how to use the model as a basis for rating network configurations.}, language = {en} } @misc{EijkhofBodlaenderKoster, author = {Eijkhof, Frank van den and Bodlaender, Hans L. and Koster, Arie M.C.A.}, title = {Safe reduction rules for weighted treewidth}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7164}, number = {02-49}, abstract = {Several sets of reductions rules are known for preprocessing a graph when computing its treewidth. In this paper, we give reduction rules for a weighted variant of treewidth, motivated by the analysis of algorithms for probabilistic networks. We present two general reduction rules that are safe for weighted treewidth. They generalise many of the existing reduction rules for treewidth. Experimental results show that these reduction rules can significantly reduce the problem size for several instances of real-life probabilistic networks.}, language = {en} } @misc{EisenblaetterKosterWallbaumetal., author = {Eisenbl{\"a}tter, Andreas and Koster, Arie M.C.A. and Wallbaum, Randolf and Wess{\"a}ly, Roland}, title = {Load Balancing in Signaling Transfer Points}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7179}, number = {02-50}, abstract = {Signaling is crucial to the operation of modern telecommunication networks. A breakdown in the signaling infrastructure typically causes customer service failures, incurs revenue losses, and hampers the company image. Therefore, the signaling network has to be highest reliability and survivability. This in particular holds for the routers in such a network, called \textit{signaling transfer points\/} (STPs). The robustness of an STP can be improved by equally distributing the load over the internal processing units. Several constraints have to be taken into account. The load of the links connected to a processing unit changes over time introducing an imbalance of the load. In this paper, we show how integer linear programming can be applied to reduce the imbalance within an STP, while keeping the number of changes small. Two alternative models are presented. Computational experiments validate the integer programming approach in practice. The GSM network operator E-Plus saves substantial amounts of time and money by employing the proposed approach.}, language = {en} } @misc{KosterBodlaenderHoesel, author = {Koster, Arie M.C.A. and Bodlaender, Hans L. and Hoesel, Stan P.M. van}, title = {Treewidth: Computational Experiments}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6644}, number = {01-38}, abstract = {Many {\cal NP}-hard graph problems can be solved in polynomial time for graphs with bounded treewidth. Equivalent results are known for pathwidth and branchwidth. In recent years, several studies have shown that this result is not only of theoretical interest but can successfully be applied to find (almost) optimal solutions or lower bounds for diverse optimization problems. To apply a tree decomposition approach, the treewidth of the graph has to be determined, independently of the application at hand. Although for fixed \$k\$, linear time algorithms exist to solve the decision problem ``treewidth \$\leq k\$'', their practical use is very limited. The computational tractability of treewidth has been rarely studied so far. In this paper, we compare four heuristics and two lower bounds for instances from applications such as the frequency assignment problem and the vertex coloring problem. Three of the heuristics are based on well-known algorithms to recognize triangulated graphs. The fourth heuristic recursively improves a tree decomposition by the computation of minimal separating vertex sets in subgraphs. Lower bounds can be computed from maximal cliques and the minimum degree of induced subgraphs. A computational analysis shows that the treewidth of several graphs can be identified by these methods. For other graphs, however, more sophisticated techniques are necessary.}, language = {en} } @misc{BodlaenderKosterEijkhofetal., author = {Bodlaender, Hans L. and Koster, Arie M.C.A. and Eijkhof, Frank van den and Gaag, Linda C. van der}, title = {Pre-processing for Triangulation of Probabilistic Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6655}, number = {01-39}, abstract = {The currently most efficient algorithm for inference with a probabilistic network builds upon a triangulation of a network's graph. In this paper, we show that pre-processing can help in finding good triangulations for probabilistic networks, that is, triangulations with a minimal maximum clique size. We provide a set of rules for stepwise reducing a graph, without losing optimality. This reduction allows us to solve the triangulation problem on a smaller graph. From the smaller graph's triangulation, a triangulation of the original graph is obtained by reversing the reduction steps. Our experimental results show that the graphs of some well-known real-life probabilistic networks can be triangulated optimally just by preprocessing; for other networks, huge reductions in their graph's size are obtained.}, language = {en} } @misc{AardalHoeselKosteretal., author = {Aardal, Karen I. and Hoesel, Stan P.M. van and Koster, Arie M.C.A. and Mannino, Carlo and Sassano, Antonio}, title = {Models and Solution Techniques for Frequency Assignment Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6667}, number = {01-40}, abstract = {{\begin{rawhtml} Revised Version unter http://dx.doi.org/10.1007/s10479-007-0178-0 \end{rawhtml}} Wireless communication is used in many different situations such as mobile telephony, radio and TV broadcasting, satellite communication, and military operations. In each of these situations a frequency assignment problem arises with application specific characteristics. Researchers have developed different modelling ideas for each of the features of the problem, such as the handling of interference among radio signals, the availability of frequencies, and the optimization criterion. This survey gives an overview of the models and methods that the literature provides on the topic. We present a broad description of the practical settings in which frequency assignment is applied. We also present a classification of the different models and formulations described in the literature, such that the common features of the models are emphasized. The solution methods are divided in two parts. Optimization and lower bounding techniques on the one hand, and heuristic search techniques on the other hand. The literature is classified according to the used methods. Again, we emphasize the common features, used in the different papers. The quality of the solution methods is compared, whenever possible, on publicly available benchmark instances.}, language = {en} } @misc{EisenblaetterGroetschelKoster, author = {Eisenbl{\"a}tter, Andreas and Gr{\"o}tschel, Martin and Koster, Arie M.C.A.}, title = {Frequency Planning and Ramifications of Coloring}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6152}, number = {00-47}, abstract = {This paper surveys frequency assignment problems coming up in planning wireless communication services. It particularly focuses on cellular mobile phone systems such as GSM, a technology that revolutionizes communication. Traditional vertex coloring provides a conceptual framework for the mathematical modeling of many frequency planning problems. This basic form, however, needs various extensions to cover technical and organizational side constraints. Among these ramifications are \$T\$-coloring and list coloring. To model all the subtleties, the techniques of integer programming have proven to be very useful. The ability to produce good frequency plans in practice is essential for the quality of mobile phone networks. The present algorithmic solution methods employ variants of some of the traditional coloring heuristics as well as more sophisticated machinery from mathematical programming. This paper will also address this issue. Finally, this paper discusses several practical frequency assignment problems in detail, states the associated mathematical models, and also points to public electronic libraries of frequency assignment problems from practice. The associated graphs have up to several thousand nodes and range from rather sparse to almost complete.}, language = {en} } @misc{KosterZymolka, author = {Koster, Arie M.C.A. and Zymolka, Adrian}, title = {Stable Multi-Sets}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6047}, number = {00-36}, abstract = {In this paper we introduce a generalization of stable sets: stable multi-sets. A stable multi-set is an assignment of integers to the vertices of a graph, such that specified bounds on vertices and edges are not exceeded. In case all vertex and edge bounds equal one, stable multi-sets are equivalent to stable sets. For the stable multi-set problem, we derive reduction rules and study the associated polytope. We state necessary and sufficient conditions for the extreme points of the linear relaxation to be integer. These conditions generalize the conditions for the stable set polytope. Moreover, the classes of odd cycle and clique inequalities for stable sets are generalized to stable multi-sets and conditions for them to be facet defining are determined. The study of stable multi-sets is initiated by optimization problems in the field of telecommunication networks. Stable multi-sets emerge as an important substructure in the design of optical networks.}, language = {en} } @misc{Koster, author = {Koster, Arie M.C.A.}, title = {Re-Optimization of Signaling Transfer Points}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5863}, number = {00-18}, abstract = {In this paper we describe the results of a computational study towards the (re)optimization of signaling transfer points (STPs) in telecommunication networks. The best performance of an STP is achieved whenever the traffic load is evenly distributed among the internal components. Due to the continuously changing traffic pattern, the load of the components has to be re-optimized on a regular basis. Besides the balancing objective also the number of rearrangements have to be taken into account. In this paper we present two alternative formulations to deal with both requirements. Computational results show that for both formulations (near) optimal solutions can be obtained within reasonable time limits.}, language = {en} } @misc{HoeselKosterLeenseletal., author = {Hoesel, Stan P.M. van and Koster, Arie M.C.A. and Leensel, Robert L.M.J. van de and Savelsbergh, Martin W.P.}, title = {Polyhedral Results for the Edge Capacity Polytope}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5907}, number = {00-22}, abstract = {Network loading problems occur in the design of telecommunication networks, in many different settings. The polyhedral structure of this problem is important in developing solution methods for the problem. In this paper we investigate the polytope of the problem restricted to one edge of the network (the edge capacity problem). We describe classes of strong valid inequalities for the edge capacity polytope, and we derive conditions under which these constraints define facets. As the edge capacity problem is a relaxation of the network loading problem, their polytopes are intimately related. We, therefore, also give conditions under which the inequalities of the edge capacity polytope define facets of the network loading polytope. Furthermore, some structural properties are derived, such as the relation of the edge capacity polytope to the knapsack polytope. We conclude the theoretical part of this paper with some lifting theorems, where we show that this problem is polynomially solvable for most of our classes of valid inequalities. In a computational study the quality of the constraints is investigated. Here, we show that the valid inequalities of the edge capacity polytope are not only important for solving the edge capacity problem, but also for the network loading problem, showing that the edge capacity problem is an important subproblem.}, language = {en} }