Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-3125
Main Title: The Power of Recourse in Online Optimization: Robust Solutions for Scheduling, Matroid and MST Problems
Translated Title: Die Kraft der rückwirkenden Veränderung in der Online-Optimirung: robuste Lösungen für Scheduling-, Matroide-, und Spannbaum-Problem
Author(s): Verschae Tannenbaum, Jose Claudio
Advisor(s): Skutella, Martin
Granting Institution: Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: Unsicherheit der Eingabedaten ist eine der größten Herausforderungen in der Optimierung. Zwei bekannte Paradigmen der Optimierung mit unvollständiger Information sind das Online und das multi-stage robust Modell. In Online-Problemen wird die Information stückweise in verschiedenen Phasen bekannt gemacht, in denen Optimierer unabänderbare Entscheidungen treffen müssen. Die Qualität von Online-Algorithmen wird mit dem Kompetitivitätsfaktor gemessen, d. h. mit dem Worst-Case Verhältnis zwischen der gefundenen Lösung und der optimalen Lösung. Im Falle der robusten multi-stage Optimierung wird der Input ebenfalls nacheinander bekanntgegeben, der Optimierer kann jedoch die Lösung durch Recourse anpassen. Das Ziel ist, den Recourse optimal zu wählen. Abgesehen von ihrem Nutzen in vielen Situationen können die ermittelten Schranken aber in Online-Problemen zu konservativ sein und multi-stage robust Probleme leiden an der extrem hohen Komplexität der Berechnung. In dieser Arbeit analysieren wir ein relaxiertes Online-Framework in dem Recourse in einem begrenzten Umfang erlaubt ist. Wir können für einige relevante Probleme zeigen, dass bereits ein sehr geringer Recourse ermöglicht, fast-optimale Lösungen zu berechnen. Für diese Probleme behebt unser Modell die obengenannten, den zwei Paradigmen inhärenten Probleme. In der Arbeit werden drei Optimierungsprobleme behandelt. Zuerst betrachten wir Online-Maschinen-Scheduling-Probleme, in denen die Jobs nacheinander ankommen. Sobald ein Job auftaucht müssen wir ihn einer Maschine zuteilen. Der Recourse wird durch den \emph{Migrationsfaktor} kontrolliert, der das Worst-Case-Verhältnis zwischen der gesamten Bearbeitungsdauer von migrierten Jobs in einer Phase und der Größe des ankommenden Jobs beschreibt. Die amortisierte Variante des Maßes ist der Reassignmentfaktor. Wir untersuchen eine allgemeine Klasse von Zielfunktionen in diesem Framework, die uns u.\,A. erlaubt, das bekannte Minimum-Makespan-Problem und das Machine-Covering-Problem zu modellieren. Wir zeigen, dass konstante Reassignmentfaktoren ausreichen, um eine fast-optimale Lösung in jeder Phase zu erhalten. Andererseits erlaubt das Migrationsfaktor-Modell kein solches Ergebnis. Als zweites untersuchen wir Matroid-Schnitt-Probleme. Matroide sind kombinatorische Strukturen, die fundamentale Eigenschaften einiger Optimierungsprobleme abdecken. Wir untersuchen eine Online-Variante, in der in jeder Phase ein Bündel von Elementen bekanntgegeben wird. In jeder Phase ist es uns erlaubt, eine bestimmte Anzahl von Elementen zur Lösung hinzuzufügen. In diesem Framework ist das Worst-Case Verhältnis von konstruierten Lösungen zum Offline-Optimum unbeschränkt. Daher vergleichen wir unseren Algorithmus mit der besten Folge von Lösungen, die den gleichen Recourse-Bedingungen unterliegt. Unser wichtigstes Ergebnis ist ein O(c^2)-kompetitiver Algorithmus für den Schnitt von c Matroiden. Zuletzt betrachten wir das Problem, einen minimalen Spannbaum zu finden. In unserem Online-Szenario werden die Knoten eines metrischen Graphen nacheinander bekanntgegeben. Der Recourse ist durch die Anzahl k der Kanten, die in jeder Phase eingefügt werden können, beschränkt. Mit einer amortisierten Version dieser Einschränkung können wir für konstantes k eine fast-optimale Lösung bestimmen. Dies steht im Gegensatz zum nicht-amortisierten Szenario, in dem bestenfalls 2-Kompetivität erreicht werden kann. Weiterhin stellen wir eine Vermutung auf, die die Existenz eines Algorithmus mit konstantem Kompetivitätsfaktor im nicht-amortisierten Szenario implizieren würde. Darüber hinaus zeigen wir, dass alle diese Ergebnisse auf eine Online-Variante des Problems des Handlungsreisenden übertragen werden können, wobei der Kompetetivitätsfaktor und k um eine Konstante erhöht werden.
Uncertainty on the input data is one of the most challenging problems in optimization. Two well known paradigms of optimization under lack of information are the online and the multi-stage robust models. In online problems the information is revealed piece by piece in several stages, and the optimizer must take irrevocable decisions when a new piece of information is revealed. The quality of algorithms is measured with the competitive factor, that compares solutions to the offline optimum in the worst case. In multi-stage robust problems the input is also revealed in several stages, and the optimizer can adjust the solution to the input data by the use of recourse. The objective is to choose the recourse optimally. Despite their usefulness in several situations, both models have often be subject to criticism: the bounds obtained in online problems can be over conservative, and multi-stage robust problems suffer from a excessively high computational complexity. In this thesis, we study a relaxed online framework where a limited amount of recourse is permitted. For several relevant problems, we can show that a very limited amount of recourse allows to obtain near-optimal solutions. For these problems, our model cope with the inherent problems of the two paradigms discussed above. We propose two general models for bounding the recourse allowed. In the first one, we bound the amount of recourse independently in each stage. The second one bounds the recourse in an amortized manner. Both models find applications in different areas. Three different problems are considered in this thesis. First we study online machine scheduling problems, where jobs arrive one by one. Whenever a job appears we must assign it to some machine. The amount of recourse is controlled with the migration factor, that is, the worst case ratio between the total processing time of jobs migrated and the size of the arriving job. The amortized variant of this measure is the reassignment factor. We study a general class of objective functions in this framework, that allows us to model the prominent minimum makespan problem and the machine covering problem, among many others. We show that constant reassignment factors are enough to maintain near optimal solutions in every stage. On the other hand, the migration factor model does not allow such result. Secondly, we study matroid intersection problems. Matroids are combinatorial structures that capture fundamental properties of several optimization problems. We study an online variant where batches of elements are revealed in every stage. In each stage we are allowed to insert to the solution a given number of elements. In this framework, comparing the constructed solutions to the offline optimum give unbounded competitive ratios. Therefore we compare our algorithms against the best sequence of solutions that have our same recourse power. Our main result in an O(c^2)-competitive algorithm for the intersection of c matroids. Last, we consider the minimum spanning tree problem. In our online setting, nodes of a metric graph are revealed one by one. In every stage we must construct a spanning tree of small cost. The recourse is bounded by limiting the number of edges k to insert in each stage. With an amortized version of this idea, we can obtain near optimal solutions with constant k. This contrasts the non-amortized setting where the best possible competitive guarantee is 2. Also, we show a conjecture that would imply the existence of a constant competitive algorithm in the non-amortized setting. Moreover, we show that all these results transfer to an online version of the traveling salesmen problem by increasing by a constant competitive ratio and k.
URI: urn:nbn:de:kobv:83-opus-34337
http://depositonce.tu-berlin.de/handle/11303/3422
http://dx.doi.org/10.14279/depositonce-3125
Exam Date: 6-Feb-2012
Issue Date: 17-Feb-2012
Date Available: 17-Feb-2012
DDC Class: 510 Mathematik
Subject(s): Diskrete Optimierung
Matroid
Scheduling
Spannbaum
Discrete Optimization
Matroid
Scheduling
Spanning Tree
Usage rights: Terms of German Copyright Law
Appears in Collections:Institut für Mathematik » Publications

Files in This Item:
File Description SizeFormat 
Dokument_50.pdf1.26 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.