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.
In the connected facility location problem with buy-at-bulk edge costs we are given a set of clients with positive demands and a set of potential facilities with opening costs in an undirected graph with edge lengths obeying the triangle inequality. Moreover, we are given a set of access cable types, each with a cost per unit length and a capacity such that the cost per capacity decreases from small to large cables, and a core cable type of innite capacity. The task is to open some facilities and to connect them by a Steiner tree using core cables, and to build a forest network using access cables such that the edge capacities suce to simultaneously route all client demands unsplit to the open facilities. The objective is to minimize the total cost of opening facilities, building the core Steiner tree, and installing the access cables. In this paper, we devise a constant-factor approximation algorithm for this problem based on a random sampling technique.
We consider a generalization of the connected facility location problem where the clients must be connected to the open facilities via shared capacitated (tree) networks instead of independent shortest paths. This problem arises in the planning of ber optic telecommunication access networks, for example. Given a set of clients with positive demands, a set of potential facilities with opening costs, a set of capacitated access cable types, and a core cable type of innite capacity, one has to decide which facilities to open, how to interconnect them using a Steiner tree of innite capacity core cables, and which access cable types to install on which potential edges such that these edges form a forest and the installed capacities suce to simultaneously route the client demands to the open facilities via single paths. The objective is to minimize the total cost of opening facilities, building the core Steiner tree among them, and installing the access cables. In this paper, we devise a constant-factor approximation algorithm for problem instances where the access cable types obey economies of scale. In the special case where only multiples of a single cable type can be installed on the access edges, a variant of our algorithm achieves a performance guarantee of 6.72.
We consider a generalized version of the rooted connected facility location problem which occurs in planning of telecommunication networks with both survivability and hop-length constraints. Given a set of client nodes, a set of potential facility nodes including one predetermined root facility, a set of optional Steiner nodes, and the set of the potential connections among these nodes, that task is to decide which facilities to open, how to assign the clients to the open facilities, and how to interconnect the open facilities in such a way, that the resulting network contains at least edge-disjoint paths, each containing at most H edges, between the root and each open facility and that the total cost for opening facilities and installing connections is minimal. We study two IP models for this problem and present a branch-and-cut algorithm based on Benders decomposition for nding its solution. Finally, we report computational results.