@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{BodlaenderFominKosteretal., author = {Bodlaender, Hans L. and Fomin, Fedor V. and Koster, Arie M.C.A. and Kratsch, Dieter and Thilikos, Dimitrios M.}, title = {On exact algorithms for treewidth}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9265}, number = {06-32}, abstract = {We give experimental and theoretical results on the problem of computing the treewidth of a graph by exact exponential time algorithms using exponential space or using only polynomial space. We first report on an implementation of a dynamic programming algorithm for computing the treewidth of a graph with running time \$O^\ast(2^n)\$. This algorithm is based on the old dynamic programming method introduced by Held and Karp for the {\sc Tra veling Salesman} problem. We use some optimizations that do not affect the worst case running time but improve on the running time on actual instances and can be seen to be practical for small instances. However, our experiments show that the space use d by the algorithm is an important factor to what input sizes the algorithm is effective. For this purpose, we settle the problem of computing treewidth under the restriction that the space used is only polynomial. In this direction we give a simple \$O^\ast(4^n)\$ al gorithm that requires {\em polynomial} space. We also show that with a more complicated algorithm, using balanced separators, {\sc Treewidth} can be computed in \$O^\ast(2.9512^n)\$ time and polynomial space.}, 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} } @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{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{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{Koster, author = {Koster, Arie M.C.A.}, title = {Wavelength Assignment in Multi-Fiber WDM Networks by Generalized Edge Coloring}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8478}, number = {05-13}, abstract = {In this paper, we study wavelength assignment problems in multi-fiber WDM networks. We focus on the special case that all lightpaths have at most two links. This in particular holds in case the network topology is a star. As the links incident to a specific node in a meshed topology form a star subnetwork, results for stars are also of interest for general meshed topologies. We show that wavelength assignment with at most two links per lightpath can be modeled as a generalized edge coloring problem. By this relation, we show that for a network with an even number of fibers at all links and at most two links per lightpath, all lightpaths can be assigned a wavelength without conversion. Moreover, we derive a lower bound on the number of lightpaths to be converted for networks with arbitrary numbers of fibers at the links. A comparison with linear programming lower bounds reveals that the bounds coincide for problems with at most two links per lightpath. For meshed topologies, the cumulative lower bound over all star subnetworks equals the best known solution value for all realistic wavelength assignment instances available, by this proving optimality.}, language = {en} } @misc{BodlaenderKosterWolle, author = {Bodlaender, Hans L. and Koster, Arie M.C.A. and Wolle, Thomas}, title = {Contraction and Treewidth Lower Bounds}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8042}, number = {04-29}, abstract = {Edge contraction is shown to be a useful mechanism to improve lower bound heuristics for treewidth. A successful lower bound for treewidth is the degeneracy: the maximum over all subgraphs of the minimum degree. The degeneracy is polynomial time computable. We introduce the notion of contraction degeneracy: the maximum over all minors of the minimum degree. We show that the contraction degeneracy problem is NP-complete, even for bipartite graphs, but for fixed \$k\$, it is polynomial time decidable if a given graph \$G\$ has contraction degeneracy at least \$k\$. Heuristics for computing the contraction degeneracy are proposed and evaluated. It is shown that these can lead in practice to considerable improvements of the lower bound for treewidth, but can perform arbitrarily bad on some examples. A study is also made for the combination of contraction with Lucena's lower bound based on Maximum Cardinality Search (Lucena, 2003). Finally, heuristics for the treewidth are proposed and! evaluated that combine contraction with a treewidth lower bound technique by Clautiaux et al (2003).}, language = {en} } @misc{KosterZymolka, author = {Koster, Arie M.C.A. and Zymolka, Adrian}, title = {Provably Good Solutions for Wavelength Assignment in Optical Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8155}, number = {04-40}, abstract = {In this paper, we study the minimum converter wavelength assignment problem in optical networks. To benchmark the quality of solutions obtained by heuristics, we derive an integer programming formula tion by generalizing the formulation of Mehrotra and Trick (1996) for the vertex coloring problem. To handle the exponential number of variables, we propose a column generation approach. Computational experiments show that the value of the linear relaxation states a good lower bound and can often prove optimality of the best solution generated heuristically.}, language = {en} } @misc{KosterZymolka, author = {Koster, Arie M.C.A. and Zymolka, Adrian}, title = {Linear Programming Lower Bounds for Minimum Converter Wavelength Assignment in Optical Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8160}, number = {04-41}, abstract = {In this paper, we study the conflict-free assignment of wavelengths to lightpaths in an optical network with the opportunity to place wavelength converters. To benchmark heuristics for the problem, we develop integer programming formulations and study their properties. Moreover, we study the computational performance of the column generation algorithm for solving the linear relaxation of the most promising formulation. In many cases, a non-zero lower bound on the number of required converters is generated this way. For several instances, we in fact prove optimality since the lower bound equals the best known solution value.}, language = {en} } @misc{WolleKosterBodlaender, author = {Wolle, Thomas and Koster, Arie M.C.A. and Bodlaender, Hans L.}, title = {A Note on Contraction Degeneracy}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8180}, number = {04-43}, abstract = {The parameter contraction degeneracy -- the maximum minimum degree over all minors of a graph -- is a treewidth lower bound and was first defined in (Bodlaender, Koster, Wolle, 2004). In experiments it was shown that this lower bound improves upon other treewidth lower bounds. In this note, we examine some relationships between the contraction degeneracy and connected components of a graph, block s of a graph and the genus of a graph. We also look at chordal graphs, and we study an upper bound on the contraction degeneracy and another lower bound for treewidth. A data structure that can be used for algorithms computing the degeneracy and similar parameters, is also described.}, language = {en} } @misc{KosterWolleBodlaender, author = {Koster, Arie M.C.A. and Wolle, Thomas and Bodlaender, Hans L.}, title = {Degree-Based Treewidth Lower Bounds}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8193}, number = {04-44}, abstract = {Every lower bound for treewidth can be extended by taking the maximum of the lower bound over all subgraphs or minors. This extension is shown to be a very vital idea for improving treewidth lower bounds. In this paper, we investigate a total of nine graph parameters, providing lower bounds for treewidth. The parameters have in common that they all are the vertex-degree of some vertex in a subgra ph or minor of the input graph. We show relations between these graph parameters and study their computational complexity. To allow a practical comparison of the bounds, we developed heuristic algorithms for those parameters that are NP-hard to compute. Computational experiments show that combining the treewidth lower bounds with minors can considerably improve the lower bounds.}, language = {en} } @misc{BodlaenderKoster, author = {Bodlaender, Hans L. and Koster, Arie M.C.A.}, title = {On the Maximum Cardinality Search Lower Bound for Treewidth}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8201}, number = {04-45}, abstract = {The Maximum Cardinality Search algorithm visits the vertices of a graph in some order, such that at each step, an unvisited vertex that has the largest number of visited neighbors becomes visited. An MCS-ordering of a graph is an ordering of the vertices that can be generated by the Maximum Cardinality Search algorithm. The visited degree of a vertex \$v\$ in an MCS-ordering is the number of neighbors of \$v\$ that are before \$v\$ in the ordering. The visited degree of an MCS-ordering \$\psi\$ of \$G\$ is the maximum visited degree over all vertices \$v\$ in \$\psi\$. The maximum visited degree over all MCS-orderings of graph \$G\$ is called its {\em maximum visited degree}. Lucena (2003) showed that the treewidth of a graph \$G\$ is at least its maximum visited degree. We show that the maximum visited degree is of size \$O(\log n)\$ for planar graphs, and give examples of planar graphs \$G\$ with maximum visited degree \$k\$ with \$O(k!)\$ vertices, for all \$k\in \Bbb{N}\$. Given a graph \$G\$, it is NP-complete to determine if its maximum visited degree is at least \$k\$, for any fixed \$k\geq 7\$. Also, this problem does not have a polynomial time approximation algorithm with constant ratio, unless P=NP. Variants of the problem are also shown to be NP-complete. We also propose and experimentally analyses some heuristics for the problem. Several tiebreakers for the MCS algorithm are proposed and evaluated. We also give heuristics that give upper bounds on the value of the maximum visited degree of a graph, which appear to give results close to optimal on many graphs from real life applications.}, language = {en} } @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{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} }