Refine
Year of publication
Document Type
- ZIB-Report (37)
Has Fulltext
- yes (37) (remove)
Is part of the Bibliography
- no (37)
Keywords
- integer programming (7)
- treewidth (7)
- lower bounds (4)
- contraction degeneracy (3)
- heuristics (3)
- mixed integer programming (3)
- network design (3)
- optical networks (3)
- wavelength assignment (3)
- computations (2)
Institute
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.
Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations with respect to different concepts. Perfect graphs are, for instance, precisely those graphs $G$ where the stable set polytope $STAB(G)$ coincides with the fractional stable set polytope $QSTAB(G)$. For all imperfect graphs $G$ it holds that $STAB(G) \subset QSTAB(G)$. It is, therefore, natural to use the difference between the two polytopes in order to decide how far an imperfect graph is away from being perfect; we discuss three different concepts, involving the facet set of $STAB( G)$, the disjunctive index of $QSTAB(G)$, and the dilation ratio of the two polytopes. Including only certain types of facets for $STAB(G)$, we obtain graphs that are in some sense close to perfect graphs, for example minimally immperfect graphs, and certain other classes of so-called rank-perfect graphs. The imperfection ratio has been introduced by (Gerke and McDiarmid, 2001) as the dilation ratio of $STAB(G)$ and $QSTAB(G)$, whereas (Aguilera et al., 2003) suggest to take the disjunctive index of $Q STAB(G)$ as the imperfection index of $G$. For both invariants there exist no general upper bounds, but there are bounds known for the imperfection ratio of several graph classes (Coulonges et al. 2005, Gerke and McDiarmid, 2001). Outgoing from a graph-theoretical interpretation of the imperfection index, we conclude that the imperfection index is NP-hard to compute and we prove that there exists no upper bound on the imperfect ion index for those graph classes with a known bounded imperfection ratio. Comparing the two invariants on those classes, it seems that the imperfection index measures imperfection much more roughly than the imperfection ratio; therefoe, discuss possible directions for refinements.
In this paper we present a new technique for computing lower bounds for graph treewidth. Our technique is based on the fact that the treewidth of a graph $G$ is the maximum order of a bramble of $G$ minus one. We give two algorithms: one for general graphs, and one for planar graphs. The algorithm for planar graphs is shown to give a lower bound for both the treewidth and branchwidth that is at most a constant factor away from the optimum. For both algorithms, we report on extensive computational experiments that show that the algorithms give often excellent lower bounds, in particular when applied to (close to) planar graphs.
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.
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).
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.
Linear Programming Lower Bounds for Minimum Converter Wavelength Assignment in Optical Networks
(2004)
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.
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.
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.
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.
Der scharfe Wettbewerb innerhalb der Telekommunikationsbranche zwingt die Netzbetreiber dazu, ihre Investitionen genau zu planen und immer wieder Einsparungsmanahmen durchzuführen. Gleichzeitig ist es jedoch wichtig, die Qualität der angebotenen Dienste zu verbessern, um neue Kunden zu gewinnen und langfristig an sich zu binden. Die mathematische Optimierung bietet sich für viele solcher Aufgabenstellungen als hervorragend geeignetes Planungswerkzeug an. Ziel dieses Artikels ist es, ihre Methodik und ihre Anwendung speziell zur Kosten- und Qualitätsoptimierung in Kommunikationsnetzen vorzustellen. Anhand von vier konkreten Planungsaufgaben aus dem Bereich der Festnetzplanung wird aufgezeigt, wie sich komplexe Zusammenhänge in flexiblen mathematischen Modellen abbilden lassen und welche Verfahren zur automatisierten Bearbeitung der Probleme eingesetzt werden können. Die hier vorgestellten Methoden zeichnen sich insbesondere dadurch aus, dass sie neben hochwertigen Lösungen auch eine Qualittsgarantie liefern, mit der sich die Lsungen fundiert bewerten lassen. Die dokumentierten Ergebnisse aus verschiedenen Industrieprojekten belegen die Eignung und Güte der mathematischen Optimierung für die Praxis.
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.
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.
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.
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.
Frequenzplanung im Mobilfunk
(2002)
Telekommunikation ist seit Jahren \glqq in\grqq. Zunächst gab es einen enormen Aufschwung; neue Technologien und Dienste haben eine überwältigende, nicht vorhersehbare Akzeptanz gefunden. Derzeit ist -- ausgelöst durch die UMTS-Lizenzversteigerungen, Rezessions- und Sättigungstendenzen -- eine Krise zu verzeichnen. Viele (auch wir) sind davon überzeugt, dass technischer Fortschritt und nützliche Dienste demnächst die Stimmung wieder ä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 Überblick ü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äquater Algorithmen erreichen kann.
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.
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.
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.
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.