Refine
Language
- English (7)
Keywords
- Knapsack Problem (2)
- Robust Optimization (2)
- multi-layer network design (2)
- Cutset inequalities (1)
- Multi-layer network design (1)
- Packing integer programming (1)
- SNDlib (1)
- branch-and-cut (1)
- capacitated network design (1)
- cutset-polyhedra (1)
Application Area
- B (7)
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.
This paper deals with MIP-based primal heuristics to be used within a branch-and-cut approach for solving multi-layer telecommunication network design problems. Based on a mixed-integer programming formulation for two network layers, we present three heuristics for solving important subproblems, two of which solve a sub-MIP. On multi-layer planning instances with many parallel logical links, we show the effectiveness of our heuristics in finding good solutions early in the branch-and-cut search tree.
In this article we study capacitated network design problems. We unify and extend polyhedral results for directed, bidirected and undirected link capacity models. Based on valid inequalities for a network cut we show that regardless of the link capacity model, facets of the polyhedra associated with such a cut translate to facets of the original network design polyhedra if the two subgraphs defined by the network cut are (strongly) connected. Our investigation of the facial structure of the cutset polyhedra allows to complement existing polyhedral results for the three variants by presenting facet-defining flow-cutset inequalities in a unifying way. In addition, we present a new class of facet-defining inequalities, showing as well that flow-cutset inequalities alone do not suffice to give a complete description for single-commodity, single-module cutset polyhedra in the bidirected and undirected case – in contrast to a known result for the directed case. The practical importance of the theoretical investigations is highlighted in an extensive computational study on 27 instances from the Survivable Network Design Library (SNDlib).
We study a planning problem arising in SDH/WDM multi-layer telecommunication network design. The goal is to find a minimum cost
installation of link and node hardware of both network layers such that traffic demands can be realized via grooming and a survivable routing. We present a mixed-integer programming formulation that takes many practical side constraints into account, including node hardware, several bitrates, and survivability against single physical node or link failures. This model is solved using a branch-and-cut approach with problem-specific preprocessing and cutting planes based on either of the two layers. On several realistic two-layer planning scenarios, we show that these cutting planes are still useful in the multi-layer context,
helping to increase the dual bound and to reduce the optimality gaps.
In this paper we study a certain cardinality constrained packing integer program which is motivated by the problem of dimensioning a cut in a two-layer network. We prove NP-hardness and consider the facial structure of the corresponding polytope. We provide a complete description for the smallest nontrivial case and develop two general classes of facet-defining inequalities. This approach extends the
notion of the well known cutset inequalities to two network layers.
In this paper, we investigate the recoverable robust knapsack problem,
where the uncertainty of the item weights follows the approach of Bertsimas and
Sim. In contrast to the robust approach, a limited recovery action is allowed,
i.e., up to k items may be removed when the actual weights are known. This problem
is motivated by the assignment of traffic nodes to antennas in wireless network
planning. Starting from an exponential min-max optimization model, we derive an
integer linear programming formulation of quadratic size. In a preliminary computational
study, we evaluate the gain of recovery using realistic planning data.
The knapsack problem is one of the basic problems in combinatorial optimization. In real-world applications it is often part of a more complex problem. Examples are machine capacities in production planning or bandwidth restrictions in telecommunication network design. Due to unpredictable future settings or erroneous data, parameters of such a subproblem are subject to uncertainties.
In high risk situations a robust approach should be chosen to deal with these uncertainties.
Unfortunately, classical robust optimization outputs solutions with little profit by prohibiting any adaption of the solution when the actual realization of the uncertain parameters is known.
This ignores the fact that in most settings minor changes to a previously determined solution are possible. To overcome these drawbacks we allow a limited recovery of a previously fixed item set as soon as the data are known by deleting at most k items and adding up to l new items.
We consider the complexity status of this recoverable robust knapsack problem and extend the classical concept of cover inequalities to obtain stronger polyhedral descriptions. Finally, we present two extensive computational studies to investigate the influence of parameters k and l to the objective and evaluate the effectiveness of our new class of valid inequalities.