Online Optimization: Probabilistic Analysis and Algorithm Engineering
| dc.contributor.advisor | Grötschel, Martin | en |
| dc.contributor.author | Hiller, Benjamin | en |
| dc.contributor.grantor | Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften | en |
| dc.date.accepted | 2009-12-15 | |
| dc.date.accessioned | 2015-11-20T19:21:50Z | |
| dc.date.available | 2010-02-26T12:00:00Z | |
| dc.date.issued | 2010-02-26 | |
| dc.date.submitted | 2010-02-26 | |
| dc.description.abstract | Diese Arbeit beschäftigt sich mit Online-Optimierung, also der Steuerung von Systemen, bei denen die für die optimierte Steuerung relevanten Daten erst mit der Zeit, d. h. online, bekannt werden. Wir konzentrieren uns dabei auf kombinatorische Online-Optimierungsprobleme, bei denen die Steuerungsentscheidungen diskret sind. Im ersten, praktisch orientierten Teil der Arbeit werden Reoptimie- rungsalgorithmen für die Online-Steuerung komplexer realer Systeme vorgestellt. Ein Reoptimierungsalgorithmus trifft seine Steuerungsentscheidung so, dass sie in einem bestimmten Sinn “günstig” für di aktuelle Situation ist. Wir benutzen Techniken der mathematischen Optimierung, insbesondere ganzzahlige Optimierung, um fortgeschr ttene Reoptimierungsalgorithmen zu entwickeln. Unsere erste Anwendung ist die automatische Disposition von Pannenhilfefahrzeugen des ADAC. Hier zeigt sich, dass mathematische Optimierungsmethoden den Dispositionsprozess gegenüber der Planung mit einfachen Heuristiken verbessern und kürzere Wartezeiten für die Kunden erzielen. Für die zweite Anwendung, die Steuerung von Gruppen von Personenaufzügen in Hochhäusern, entwickeln wir ebenfalls Reoptimierungsalgorithmen. Diese sind speziell auf die Steuerung von Zielrufsystemen, bei denen Passagiere ihre Zieletage bereits auf der Startetage eingeben, zugeschnitten. Zusätzlich zur Steuerung der Aufzugsgruppe unter Ausnutzung der Freiheitsgrade des Systems versuchen die Algorithmen, langfristig ungünstige Steuerungen zu vermeiden, was durch eine geeignete Modellierung erreicht wird. Unsere Simulationen zeigen, dass die Anzahl der Passagiere, die mit akzeptabler Servicequalität bedient werden kann, durch die Verwendung von Zielrufsystemen um 50% gesteigert werden kann. Im theoretischen zweiten Teil stellen wir einen neuen Ansatz zur probabilistischen Analyse von Onlinealgorithmen vor. Im Gegensatz zu bestehenden Analysen bewerten wir die Güte eines Algorithmus nicht anhand des Erwartungswertes der Zielfunktion, sondern anhand der Verteilung der Zielfunktionswerte auf allen möglichen Eingaben, die eine globalere Beschreibung der Güte des Algorithmus darstellt. Mithilfe des Konzepts der stochastischen Dominanz können wir z. B. zeigen, dass der bekannte Paging-Algorithmus LRU eine bezüglich der stochastischen Dominanz optimale Verteilung erreicht, wenn die Eingabe bestimmte praktisch häufig vorkommende Lokalitätseigenschaften aufweist. Für das Online-Bin-Coloring-Problem (Krumke et al. 2001) beweisen wir eine Aussage, die das in Simulationen beobachtete Verhalten erklärt und damit eine offene Frage aus (Krumke et al. 2001) beantwortet. | de |
| dc.description.abstract | The subject of this thesis is online optimization, which deals with making decisions in an environment where the data describing the process to optimize becomes available over time, i. e., online. In particular, we study combinatorial online optimization problems involving discrete decisions both from a practical and a theoretical point of view. The first part of the thesis is devoted to reoptimization algorithms for the online control of complex real-world systems. A reoptimization algorithm obtains its online control decision by determining a decision that is in some sense “good” for the current state of the system. We apply rigorous mathematical modelling and optimization methods based on Integer Progamming to develop advanced reoptimization algorithms. Our first application concerns the automatic dispatching of a large fleet of service vehicles to serve waiting customers. We find that rigorous methods improve the performance of the dispatching process, leading to shorter waiting times for the customers. In our second application we consider the scheduling of groups of passenger elevators in high rise buildings. We suggest advanced control algorithms for destination call systems, in which a passenger enters his desired destination floor already at his current floor. In addition to exploiting all degrees of freedom offered by the system, our reoptimization algorithms feature means to avoid decisions that will lead to undesirable online behavior. Our simulation experiments indicate that the number of passengers that can be served with an acceptable service level increases by 50% by using a destination call system controlled by our algorithms instead of a conventional system. The second part introduces a novel kind of probabilistic analysis for online algorithms. In contrast to existing probabilistic analyses, we do not judge the quality of an online algorithm using the expectation of the objective. Instead, we consider the distribution of the objective value on all inputs which gives a more global description of the performance of the algorithm. Using the notion of stochastic dominance, we are able to establish that certain online algorithms obtain better objective value distributions than others. For instance, we can show that the famous paging algorithm LRU achieves a distribution that is optimal w. r. t. the stochastic dominance order if the request sequences exhibit locality of reference. We also apply this approach to the analysis of algorithms for online bin coloring (Krumke et al. 2001), obtaining a result that explains the behavior observed in simulations, thus resolving an open problem posed in (Krumke et al. 2001). | en |
| dc.identifier.uri | urn:nbn:de:kobv:83-opus-25649 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/2683 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-2386 | |
| dc.language | English | en |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | Analyse von Algorithmen | de |
| dc.subject.other | Aufzugssteuerung | de |
| dc.subject.other | Online-Optimierung | de |
| dc.subject.other | Stochastische Dominanz | de |
| dc.subject.other | Tourenplanung | de |
| dc.subject.other | Analysis of algorithms | en |
| dc.subject.other | Elevator control | en |
| dc.subject.other | Online optimization | en |
| dc.subject.other | Stochastic dominance | en |
| dc.subject.other | Vehicle routing | en |
| dc.title | Online Optimization: Probabilistic Analysis and Algorithm Engineering | en |
| dc.title.translated | Online-Optimierung: Probabilistische Analyse und Algorithm Engineering | de |
| dc.type | Doctoral Thesis | en |
| dc.type.version | publishedVersion | en |
| tub.accessrights.dnb | free | * |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.identifier.opus3 | 2564 | |
| tub.identifier.opus4 | 2445 | |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
Files
Original bundle
1 - 1 of 1