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
an hierarchy of network levels? We propose a mixed-integer program and a Lagrangian relaxation
based algorithm to model and solve this planning task. As one big advantage of this approach, not
only solutions but also worst-case quality gurarantees can be provided. We present a solution for
a G-WiN planning instance of DFN with 759 locations which has been computed in less than 30
minutes and which is (provably) less than 0.5 percent away from optimality.
Der scharfeWettbewerb innerhalb der Telekommunikationsbranche zwingt die Netzbetreiber dazu,
ihre Investitionen genau zu planen und immer wieder Einsparungsmaßnahmen 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 Qualitätsgarantie liefern, mit der sich die Lösungen fundiert bewerten lassen. Die dokumentierten
Ergebnisse aus verschiedenen Industrieprojekten belegen die Eignung und Güte der
mathematischen Optimierung für die Praxis.
Most data networks nowadays use shortest path protocols to route the traffic. Given administrative routing lengths for the links of the network, all data packets are sent along shortest paths with respect to these lengths from their source to their destination.
In this paper, we present an integer programming algorithm for the minimum congestion unsplittable shortest path routing problem, which arises in the operational planning of such networks. Given a capacitated directed graph and a set of communication demands, the goal is to find routing lengths that define a unique shortest path for each demand and minimize the maximum congestion over all links in the resulting routing. We illustrate the general decomposition approach our algorithm is based on, present the integer and linear programming models used to solve the master and the client problem, and discuss the most important implementational aspects. Finally, we report computational results for various benchmark problems, which demonstrate the efficiency of our algorithm.
In this paper we investigate the performance of several out-of-the box solvers for mixed-integer quadratically constrained programmes (MIQCPs) on an open pit mine production scheduling problem with mixing constraints. We compare the solvers BARON, Couenne, SBB, and SCIP to a problem-specific algorithm on two different MIQCP formulations. The computational results presented show that general-purpose solvers with no particular knowledge of problem structure are able to nearly match the performance of a hand-crafted algorithm.
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.
We consider the problem of designing a network that employs a non-bifurcated shortest path routing
protocol. The network's nodes and the set of potential links are given together with a set of forecasted endto-
end traffc demands. All relevant hardware components installable at links or nodes are considered. The
goal is to simultaneously choose the network's topology, to decide which hardware components to install
on which links and nodes, and to find appropriate routing weights such that the overall network cost is
minimized.
In this paper, we present a mathematical optimization model for this problem and an algorithmic solution
approach based on a Lagrangian relaxation. Computational results achieved with this approach for several
real-world network planning problems are reported.
In diesem Artikel werden die Optimierungsmodelle und -verfahren beschrieben, die bei der Pla-
nung des Kernnetzes und der Zugangsinfrastruktur des X-WiN verwendet wurden. Bis spätestens Januar 2006 wird das
G-WiN als technische Plattform des Deutschen Forschungsnetzes durch das Nachfolgenetz X-WiN abgelöst. Bei der Pla-
nung des X-WiN müssen zahlreiche Entscheidungen getroffen werden, um ein
funktionstüchtiges, qualitativ hochwertiges und wirtschaftliches Netz zu erhalten. Die Auswahl der Kernnetzstandorte
ist dabei von besonderer Bedeutung, da
diese Entscheidung langfristige und große Auswirkungen auf den Netzbetrieb
sowie alle nachfolgenden Planungsschritte hat.
Die dabei zu berücksichtigenden technischen und organisatorischen Alternativen
und Randbedingungen sind jedoch so vielfältig und komplex, dass eine manuelle
Planung mit großen methodischen Unzulänglichkeiten behaftet wäre. Nur durch
den Einsatz mathematisch fundierter Lösungsansätze und weitgehend automatisierter
Verfahren können eine hohe Planungsqualität und -sicherheit gewährleistet und
die vorhandenen Optimierungspotentiale voll ausgeschöpft werden.
In this paper, we present a model-based optimization approach for the design of multi-layer networks. The proposed framework is based on a series of increasingly abstract models – from a general technical system model to a problem specific mathematical model – which are used in a planning cycle to optimize the multi-layer networks. In a case study we show how central design questions for an IP-over-WDM network architecture can be answered
using this approach. Based on reference networks from the German research project EIBONE, we investigate the influence of various planning parameters on the total design cost. This includes a comparison of point-to-point vs. transparent optical layer architectures, different traffic distributions, and the use of PoS vs. Ethernet interfaces.
We consider the design of a passive optical telecommunication access network, where clients have to be connected to an intermediate level of distribution points (DPs) and further on to some central offices (COs) in a tree-like fashion. Each client demands a given number of fiber connections to its CO. Passive optical splitters installed at the DPs allow k connections to share a single common fiber between the DP and the CO. We consider fixed charge costs for the use of an edge of the underlying street network, of a DP, and of a CO and variable costs for installing fibers along the street edges and for installing splitters at the DPs. We present two Lagrangian decomposition approaches that decompose the problem based on the network structure and on the cost structure, respectively. The subproblems are solved using MIP techniques. We report computational results for realistic instances and compare the efficiency of the Lagrangian approaches to the solutions of an integrated MIP model.