TY - GEN A1 - Hiller, Benjamin A1 - Vredeveld, Tjark T1 - Probabilistic alternatives for competitive analysis N2 - In the last 20 years competitive analysis has become the main tool for analyzing the quality of online algorithms. Despite of this, competitive analysis has also been criticized: It sometimes cannot discriminate between algorithms that exhibit significantly different empirical behavior, or it even favors an algorithm that is worse from an empirical point of view. Therefore, there have been several approaches to circumvent these drawbacks. In this survey, we discuss probabilistic alternatives for competitive analysis. T3 - ZIB-Report - 11-55 KW - online algorithms KW - probabilistic analysis KW - competitive analysis KW - survey Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-15131 SN - 1438-0064 ER - TY - GEN A1 - D'Andreagiovanni, Fabio A1 - Krolikowski, Jonatan A1 - Pulaj, Jonad T1 - A hybrid primal heuristic for Robust Multiperiod Network Design N2 - 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. T3 - ZIB-Report - 13-78 KW - Multiperiod Network Design, Traffic Uncertainty, Robust Optimization, Multiband Robustness, Hybrid Heuristics Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-44081 SN - 1438-0064 ER - TY - GEN A1 - D'Andreagiovanni, Fabio A1 - Raymond, Annie T1 - Multiband Robust Optimization and its Adoption in Harvest Scheduling N2 - A central assumption in classical optimization is that all the input data of a problem are exact. However, in many real-world problems, the input data are subject to uncertainty. In such situations, neglecting uncertainty may lead to nominally optimal solutions that are actually suboptimal or even infeasible. Robust optimization offers a remedy for optimization under uncertainty by considering only the subset of solutions protected against the data deviations. In this paper, we provide an overview of the main theoretical results of multiband robustness, a new robust optimization model that extends and refines the classical theory introduced by Bertsimas and Sim. After introducing some new results for the special case of pure binary programs, we focus on the harvest scheduling problem and show how multiband robustness can be adopted to tackle the uncertainty affecting the volume of produced timber and grant a reduction in the price of robustness. T3 - ZIB-Report - 13-76 KW - Data Uncertainty KW - Robust Optimization KW - Multiband Robustness KW - Harvest Scheduling Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-43380 SN - 1438-0064 ER - TY - GEN A1 - Büsing, Christina A1 - D'Andreagiovanni, Fabio A1 - Raymond, Annie T1 - 0-1 Multiband Robust Optimization N2 - 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. T3 - ZIB-Report - 13-77 KW - Combinatorial Optimization, Robust Optimization, Multiband Robustness, Network Design Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-44093 SN - 1438-0064 ER - TY - GEN A1 - Bley, Andreas A1 - D'Andreagiovanni, Fabio A1 - Karch, Daniel T1 - Scheduling technology migration in WDM Networks N2 - The rapid technological evolution of telecommunication networks demands service providers to regularly update their technology, with the aim of remaining competitive in the marketplace. However, upgrading the technology in a network is not a trivial task. New hardware components need to be installed in the network and during the installation network connectivity may be temporarily compromised. The Wavelength Division Multiplexing (WDM) technology, whose upgrade is considered in here, shares fiber links among several optical connections and tearing down a single link may disrupt several optical connections at once. When the upgrades involve large parts of a network, typically not all links can be upgraded in parallel, which may lead to an unavoidable longer disruption of some connections. A bad scheduling of the overall endeavor, however, can dramatically increase the disconnection time of parts of the networks, causing extended service disruption. In this contribution, we study the problem of finding a schedule of the fiber link upgrades that minimizes the total service disruption time. To the best of our knowledge, this problem has not yet been formalized and investigated. The aim of our work is to close this gap by presenting a mathematical optimization model for the problem and an innovative solution algorithm that tackles the intrinsic difficulties of the problem. Computational experience on realistic instances completes our study. Our original investigations have been driven by real needs of DFN, operator of the German National Research and Education Network and our partner in the BMBF research project ROBUKOM (http://www.robukom.de/). T3 - ZIB-Report - 13-62 KW - Scheduling, Extended Formulations, Network Migration, WDM Networks Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42654 UR - http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6507677&isnumber=6507670 SN - 1438-0064 ER - TY - GEN A1 - Büsing, Christina A1 - D'Andreagiovanni, Fabio T1 - A new theoretical framework for Robust Optimization under multi-band uncertainty N2 - 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. T3 - ZIB-Report - 13-61 KW - Robust Optimization, Uncertainty Set, Multiband Robustness, Network Design Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42644 UR - http://www.springer.com/business+%26+management/operations+research/book/978-3-319-00794-6 SN - 1438-0064 ER - TY - GEN A1 - Zakrzewska, Anna A1 - D'Andreagiovanni, Fabio A1 - Ruepp, Sarah A1 - Berger, Michael S. T1 - Biobjective Optimization of Radio Access Technology Selection and Resource Allocation in Heterogeneous Wireless Networks N2 - 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. T3 - ZIB-Report - 13-63 KW - Heterogeneous Wireless Networks, Biobjective Optimization, Mixed Integer Linear Programming, Simulation Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42675 UR - http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6576416&isnumber=6576384 SN - 1438-0064 ER - TY - GEN A1 - Bauschert, Thomas A1 - Büsing, Christina A1 - D'Andreagiovanni, Fabio A1 - Koster, Arie M.C.A. A1 - Kutschka, Manuel A1 - Steglich, Uwe T1 - Network Planning under Demand Uncertainty with Robust Optimization N2 - The planning of a communication network is inevitably depending on the quality of both the planning tool and the demand forecast used. In this article, we show exemplarily how the emerging area of Robust Optimization can advance the network planning by a more accurate mathematical description of the demand uncertainty. After a general introduction of the concept and its application to a basic network design problem, we present two applications: multi-layer and mixed-line-rate network design. We conclude with a discussion of extensions of the robustness concept to increase the accuracy of handling uncertainties. T3 - ZIB-Report - 13-59 KW - Network Design, Demand Uncertainty, Robust Optimization, Telecommunications Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42557 SN - 1438-0064 ER - TY - THES A1 - Witzig, Jakob T1 - Effiziente Reoptimierung in Branch&Bound-Verfahren für die Steuerung von Aufzügen N2 - Heutzutage ist eine Vielzahl der mehrstöckigen Gebäude mit Personenaufzugsgruppen ausgestattet. Uns wohl bekannt sind die sogenannten konventionellen Systeme. Bei diesen Systemen betätigt jeder ankommende Passagier eine der beiden Richtungstasten und teilt dem dahinterstehenden Steuerungsalgorithmus seine gewünschte Startetage und Fahrtrichtung mit. Betreten wird der zuerst auf der Startetage ankommende Aufzug mit gleicher Fahrtrichtung und ausreichend Kapazitä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ünschte Zieletage angibt und eine Rückmeldung vom System erhä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äne ist das momentane Verkehrsmuster. Eine Einteilung der Verkehrsszenarien lässt sich am besten bei Bürogebäuden vornehmen. So ist es typisch fü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äteren Verkauf als Schnappschussproblem bezeichnen. Jeder Passagier bekommt im Anschluss an die Lösung des Schnappschussproblems eine Mitteilung vom System, z. B. über ein Display, welchen Aufzug er benutzen soll. Zum anderen gibt es verzögert zuweisende (VZ-) Systeme. In diesen Systemen wird die Erstellung und Lösung eines Schnappschussproblems bis kurz vor Ankunft eines Aufzuges auf einer Etage verzögert. In einem VZ-System teilt das System allen wartenden Passagieren die geplanten Zieletagen des ankommenden Aufzugs mit. Jeder Passagier, der einen Ruf getätigt hat und zu einer dieser Zieletagen fahren will, kann jetzt diesen Aufzug betreten. Durch die Verzögerung muss im Vergleich zu einem UZ-System eine weitaus größere Menge von Passagieren zugewiesen werden. Dadurch kann der Lösungsprozess bedeutend aufwändiger werden. Vorteil eines VZ-Systems ist hingegen der größere Freiheitsgrad bei der Optimierung, da aufgrund der späten Zuweisung die weitere Verkehrsentwicklung mit einbezogen werden kann. VZ-Systeme sind aufgrund des größeren Freiheitsgrades interessant für die Praxis ist, wir uns demzufolge in dieser Arbeit mit einer effizienteren Lösung dieser Art von Schnappschussproblemen befassen. Es genügt dabei den Lösungsprozess eines Schnappschussproblems zu betrachten. Das Ziel ist eine Reduzierung der benötigten Rechenzeit. Unter Reoptimierung verstehen wir die Konstruktion zulässiger Spalten in den jeweiligen Iterationsrunden der Spaltengenerierung innerhalb eines Schnappschussproblems. Als eine Iterationsrunde bezeichnet wir einer Menge zulä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ört der konstruierte Suchbaum der vorherigen Iterationsrunde mit seinen ausgeloteten (abgeschnittenen) Blättern sowie konstruierten Touren bzw. Spalten, welche in der Iterationsrunde ihrer Konstruktion nicht zur Lösung des Teilproblems der Spaltengenerierung beitrugen. Eine solche Wiederverwendung und Aufbereitung von Informationen nennen wir Warmstart. Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42210 ER - TY - GEN A1 - Shinano, Yuji A1 - Heinz, Stefan A1 - Vigerske, Stefan A1 - Winkler, Michael T1 - FiberSCIP - A shared memory parallelization of SCIP N2 - Recently, parallel computing environments have become significantly popular. In order to obtain the benefit of using parallel computing environments, we have to deploy our programs for these effectively. This paper focuses on a parallelization of SCIP (Solving Constraint Integer Programs), which is a MIP solver and constraint integer programming framework available in source code. There is a parallel extension of SCIP named ParaSCIP, which parallelizes SCIP on massively parallel distributed memory computing environments. This paper describes FiberSCIP, which is yet another parallel extension of SCIP to utilize multi-threaded parallel computation on shared memory computing environments, and has the following contributions: First, the basic concept of having two parallel extensions and the relationship between them and the parallelization framework provided by UG (Ubiquity Generator) is presented, including an implementation of deterministic parallelization. Second, the difficulties to achieve a good performance that utilizes all resources on an actual computing environment and the difficulties of performance evaluation of the parallel solvers are discussed. Third, a way to evaluate the performance of new algorithms and parameter settings of the parallel extensions is presented. Finally, current performance of FiberSCIP for solving mixed-integer linear programs (MIPs) and mixed-integer non-linear programs (MINLPs) in parallel is demonstrated. T3 - ZIB-Report - 13-55 KW - parallel KW - branch-and-bound KW - deterministic parallelism KW - constraint integer programming KW - mixed integer programming KW - mixed integer nonlinear programming KW - SCIP KW - MIP KW - MINLP Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42595 SN - 1438-0064 ER -