@misc{BuesingD'AndreagiovanniRaymond, author = {B{\"u}sing, Christina and D'Andreagiovanni, Fabio and Raymond, Annie}, title = {0-1 Multiband Robust Optimization}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-44093}, abstract = {We provide an overview of new theoretical results that we obtained while further investigating multiband robust optimization, a new model for robust optimization that we recently proposed to tackle uncertainty in mixed-integer linear programming. This new model extends and refines the classical Gamma-robustness model of Bertsimas and Sim and is particularly useful in the common case of arbitrary asymmetric distributions of the uncertainty. Here, we focus on uncertain 0-1 programs and we analyze their robust counterparts when the uncertainty is represented through a multiband set. Our investigations were inspired by the needs of our industrial partners in the research project ROBUKOM.}, language = {en} } @misc{D'AndreagiovanniKrolikowskiPulaj, author = {D'Andreagiovanni, Fabio and Krolikowski, Jonatan and Pulaj, Jonad}, title = {A hybrid primal heuristic for Robust Multiperiod Network Design}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-44081}, abstract = {We investigate the Robust Multiperiod Network Design Problem, a generalization of the classical Capacitated Network Design Problem that additionally considers multiple design periods and provides solutions protected against traffic uncertainty. Given the intrinsic difficulty of the problem, which proves challenging even for state-of-the art commercial solvers, we propose a hybrid primal heuristic based on the combination of ant colony optimization and an exact large neighborhood search. Computational experiments on a set of realistic instances from the SNDlib show that our heuristic can find solutions of extremely good quality with low optimality gap.}, language = {en} } @misc{BuesingD'Andreagiovanni, author = {B{\"u}sing, Christina and D'Andreagiovanni, Fabio}, title = {A new theoretical framework for Robust Optimization under multi-band uncertainty}, issn = {1438-0064}, doi = {10.1007/978-3-319-00795-3_17}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42644}, abstract = {We provide an overview of our main results about studying Linear Programming Problems whose coefficient matrix is subject to uncertainty and the uncertainty is modeled through a multi-band set. Such an uncertainty set generalizes the classical one proposed by Bertsimas and Sim and is particularly suitable in the common case of arbitrary non-symmetric distributions of the parameters. Our investigations were inspired by practical needs of our industrial partner in ongoing projects with focus on the design of robust telecommunications networks.}, language = {en} } @misc{PfeufferWerner, author = {Pfeuffer, Frank and Werner, Axel}, title = {Adaptive telecommunication network operation with a limited number of reconfigurations}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-55547}, abstract = {Rising traffic in telecommunication networks lead to rising energy costs for the network operators. Meanwhile, increased flexibility of the networking hardware may help to realize load-adaptive operation of the networks to cut operation costs. To meet network operators' concerns over stability, we propose to switch network configurations only a limited number of times per day. We present a method for the integrated computation of optimal switching times and network configurations that alternatingly solves mixed-integer programs and constrained shortest cycle problems in a certain graph. Similarly to the Branch \& Bound Algorithm, it uses lower and upper bounds on the optimum value and allows for pivoting strategies to guide the computation and avoid the solution of irrelevant subproblems. The algorithm can act as a framework to be adapted and applied to suitable problems of different origin.}, language = {en} } @misc{ZakrzewskaD'AndreagiovanniRueppetal., author = {Zakrzewska, Anna and D'Andreagiovanni, Fabio and Ruepp, Sarah and Berger, Michael S.}, title = {Biobjective Optimization of Radio Access Technology Selection and Resource Allocation in Heterogeneous Wireless Networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42675}, abstract = {We propose a novel optimization model for resource assignment in heterogeneous wireless network. The model adopts two objective functions maximizing the number of served users and the minimum granted utility at once. A distinctive feature of our new model is to consider two consecutive time slots, in order to include handover as an additional decision dimension. Furthermore, the solution algorithm that we propose refines a heuristic solution approach recently proposed in literature, by considering a real joint optimization of the considered resources. The simulation study shows that the new model leads to a significant reduction in handover frequency, when compared to a traditional scheme based on maximum SNR.}, language = {en} } @misc{ShinanoRehfeldtKoch, author = {Shinano, Yuji and Rehfeldt, Daniel and Koch, Thorsten}, title = {Building Optimal Steiner Trees on Supercomputers by using up to 43,000 Cores}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71118}, abstract = {SCIP-JACK is a customized, branch-and-cut based solver for Steiner tree and related problems. ug [SCIP-JACK, MPI] extends SCIP-JACK to a massively par- allel solver by using the Ubiquity Generator (UG) framework. ug [SCIP-JACK, MPI] was the only solver that could run on a distributed environment at the (latest) 11th DIMACS Challenge in 2014. Furthermore, it could solve three well-known open instances and updated 14 best known solutions to instances from the bench- mark libary STEINLIB. After the DIMACS Challenge, SCIP-JACK has been con- siderably improved. However, the improvements were not reflected on ug [SCIP- JACK, MPI]. This paper describes an updated version of ug [SCIP-JACK, MPI], especially branching on constrains and a customized racing ramp-up. Furthermore, the different stages of the solution process on a supercomputer are described in detail. We also show the latest results on open instances from the STEINLIB.}, language = {en} } @misc{ItoShinano, author = {Ito, Satoshi and Shinano, Yuji}, title = {Calculation of clinch and elimination numbers for sports leagues with multiple tiebreaking criteria}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-70591}, abstract = {The clinch (elimination) number is a minimal number of future wins (losses) needed to clinch (to be eliminated from) a specified place in a sports league. Several optimization models and computational results are shown in this paper for calculating clinch and elimination numbers in the presence of predefined multiple tiebreaking criteria. The main subject of this paper is to provide a general algorithmic framework based on integer programming with utilizing possibly multilayered upper and lower bounds.}, language = {en} } @misc{BeckerHiller, author = {Becker, Kai-Helge and Hiller, Benjamin}, title = {Efficient Enumeration of Acyclic Graph Orientations with Sources or Sinks Revisited}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-77684}, abstract = {In a recent paper, Conte et al. [CGMR2017] presented an algorithm for enumerating all acyclic orientations of a graph G=(V,E) with a single source (and related orientations) with delay O(|V||E|). In this paper we revisit the problem by going back to an early paper by de Fraysseix et al. [FMR1995], who proposed an algorithm for enumerating all bipolar orientations of a graph based on a recursion formula. We first formalize de Fraysseix et al.'s algorithm for bipolar orientations and determine that its delay is also O(|V||E|). We then apply their recursion formula to the case of Conte et al.'s enumeration problem and show that this yields a more efficient enumeration algorithm with delay O(\sqrt(|V|)|E|). Finally, a way to further streamline the algorithm that leads to a particularly simple implementation is suggested.}, language = {en} } @masterthesis{Witzig, type = {Bachelor Thesis}, author = {Witzig, Jakob}, title = {Effiziente Reoptimierung in Branch\&Bound-Verfahren f{\"u}r die Steuerung von Aufz{\"u}gen}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42210}, school = {Zuse Institute Berlin (ZIB)}, pages = {111}, abstract = {Heutzutage ist eine Vielzahl der mehrst{\"o}ckigen Geb{\"a}ude mit Personenaufzugsgruppen ausgestattet. Uns wohl bekannt sind die sogenannten konventionellen Systeme. Bei diesen Systemen bet{\"a}tigt jeder ankommende Passagier eine der beiden Richtungstasten und teilt dem dahinterstehenden Steuerungsalgorithmus seine gew{\"u}nschte Startetage und Fahrtrichtung mit. Betreten wird der zuerst auf der Startetage ankommende Aufzug mit gleicher Fahrtrichtung und ausreichend Kapazit{\"a}t. Die entsprechende Zieletage wird dem System erst nach dem Betreten der Fahrgastkabine mitgeteilt. Neben diesen konventionellen Systemen gibt es Aufzugsgruppen mit Zielrufsteuerung. Die Besonderheit eines zielrufgesteuerten Systems ist, dass ein ankommender Passagier bereits auf der Startetage seine gew{\"u}nschte Zieletage angibt und eine R{\"u}ckmeldung vom System erh{\"a}lt, welchen Aufzug er nutzen soll. Diese Zuweisung durch das System hat das Ziel, die Warte- und Reisezeiten der Passagiere zu minimieren. Ein wesentlicher Faktor bei der Berechnung warte- und reisezeitminimaler Fahrpl{\"a}ne ist das momentane Verkehrsmuster. Eine Einteilung der Verkehrsszenarien l{\"a}sst sich am besten bei B{\"u}rogeb{\"a}uden vornehmen. So ist es typisch f{\"u}r die Morgenstunden, dass jeder Passagier auf einer Zugangsebene seine Fahrt beginnt und alle Passagiere die gleiche Fahrtrichtung haben. Unter einer Zugangsebene ist z. B. der Haupteingang oder ein Parkdeck zu verstehen. Ein weiterer wesentlicher Punkt bei Zielrufsystemen ist die Art der Zuweisung der Passagiere durch das System. Zum einen gibt es unmittelbar zuweisende (UZ-) Systeme. In einem UZ-System wird nach jeder Ankunft eines Passagiers eine Momentaufnahme des momentanen Verkehrs erstellt und es findet eine Neuplanung und Zuweisung statt. Eine solche Momentaufnahme werden wir im sp{\"a}teren Verkauf als Schnappschussproblem bezeichnen. Jeder Passagier bekommt im Anschluss an die L{\"o}sung des Schnappschussproblems eine Mitteilung vom System, z. B. {\"u}ber ein Display, welchen Aufzug er benutzen soll. Zum anderen gibt es verz{\"o}gert zuweisende (VZ-) Systeme. In diesen Systemen wird die Erstellung und L{\"o}sung eines Schnappschussproblems bis kurz vor Ankunft eines Aufzuges auf einer Etage verz{\"o}gert. In einem VZ-System teilt das System allen wartenden Passagieren die geplanten Zieletagen des ankommenden Aufzugs mit. Jeder Passagier, der einen Ruf get{\"a}tigt hat und zu einer dieser Zieletagen fahren will, kann jetzt diesen Aufzug betreten. Durch die Verz{\"o}gerung muss im Vergleich zu einem UZ-System eine weitaus gr{\"o}ßere Menge von Passagieren zugewiesen werden. Dadurch kann der L{\"o}sungsprozess bedeutend aufw{\"a}ndiger werden. Vorteil eines VZ-Systems ist hingegen der gr{\"o}ßere Freiheitsgrad bei der Optimierung, da aufgrund der sp{\"a}ten Zuweisung die weitere Verkehrsentwicklung mit einbezogen werden kann. VZ-Systeme sind aufgrund des gr{\"o}ßeren Freiheitsgrades interessant f{\"u}r die Praxis ist, wir uns demzufolge in dieser Arbeit mit einer effizienteren L{\"o}sung dieser Art von Schnappschussproblemen befassen. Es gen{\"u}gt dabei den L{\"o}sungsprozess eines Schnappschussproblems zu betrachten. Das Ziel ist eine Reduzierung der ben{\"o}tigten Rechenzeit. Unter Reoptimierung verstehen wir die Konstruktion zul{\"a}ssiger Spalten in den jeweiligen Iterationsrunden der Spaltengenerierung innerhalb eines Schnappschussproblems. Als eine Iterationsrunde bezeichnet wir einer Menge zul{\"a}ssiger Touren mit negativen reduzierten Kosten. Eine effiziente Reoptimierung zeichnet sich durch die Wiederverwendung und Aufbereitung von Informationen aus vorangegangenen Iterationsrunden desselben Schnappschussproblems aus. Zu den wichtigen Informationen geh{\"o}rt der konstruierte Suchbaum der vorherigen Iterationsrunde mit seinen ausgeloteten (abgeschnittenen) Bl{\"a}ttern sowie konstruierten Touren bzw. Spalten, welche in der Iterationsrunde ihrer Konstruktion nicht zur L{\"o}sung des Teilproblems der Spaltengenerierung beitrugen. Eine solche Wiederverwendung und Aufbereitung von Informationen nennen wir Warmstart.}, language = {de} } @misc{OrlowskiWernerWessaely, author = {Orlowski, Sebastian and Werner, Axel and Wess{\"a}ly, Roland}, title = {Estimating trenching costs in FTTx network planning}, issn = {1438-0064}, doi = {10.1007/978-3-642-29210-1_15}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14884}, abstract = {In this paper we assess to which extent trenching costs of an FTTx network are unavoidable, even if technical side constraints are neglected. For that purpose we present an extended Steiner tree model. Using a variety of realistic problem instances we demonstrate that the total trenching cost can only be reduced by about 5 percent in realistic scenarios. This work has been funded by BMBF (German Federal Ministry of Education and Research) within the program "KMU-innovativ".}, language = {en} }