Loading…
Flows over time and submodular function minimization
Schlöter, Miriam
Many parts of our daily routine that we expect to "just work" rely on certain optimization processes that most of the time take place in a network. Ranging from streets, railroads or power networks to the telecommunications network used by the Internet and the networks induced by social networks: the list of structures that can be modeled as a network goes on and on and optimization processes on these networks are vital throughout our daily life.
In many network optimization problems the goal is to transport a commodity through the network in an efficient manner, e.g., people, objects, or more abstract commodities like the information you receive over a social network, or the movie you want to stream. Often a huge amount of the same commodity needs to be transported at once, like the large number of newspapers that are delivered each morning, the amount of data that travels through the communications network when you stream the latest episode of your favorite TV show, or the electricity that is needed to power the local hospital.
Such transportation problems gave rise to the development of static network flows more than 90 years ago. For many optimization problems on networks it is essential that a certain deadline is met and also that it takes time for a commodity to travel along an arc of the network, e.g. a street or a power cable. Such properties are not incorporated in the classical static network model. Here dynamic networks and flows over time come into play which are capable of modeling temporal aspects of transportation problems. In this thesis we study such network flows over time. In particular we concentrate on two classical flow over time problems that are especially useful in the context of evacuation planning. For both problems we give new and more efficient algorithms for solving them that exploit connections between the specific flow over time problem and suitably chosen submodular functions.
When evacuating people from a dangerous situation the main objective that comes to mind immediately is to save all people as quickly as possible. This property is incorporated by quickest transshipments, which are the first class of flows over time that we concentrate on throughout this thesis. In the quickest transshipment problem we are given a dynamic network with sources and sinks, and supplies and demands, respectively, and the goal is to find a flow over time that fulfills these supplies and demands as quickly as possible. The first main result in this thesis is a new strongly polynomial time algorithm for the quickest transshipment problem that significantly improves upon the so far best known algorithm for this problem, the algorithm by Hoppe and Tardos. Our algorithm exploits a connection between quickest transshipments and certain submodular functions and we use this connection to show that a solution to the quickest transshipment problem can essentially be found by only one parametric submodular function minimization. With our algorithm we achieve the first improvement for solving the quickest transshipment problem in more than 20 years.
When evacuating people using quickest transshipments, all people are rescued as quickly as possible. However, in many dangerous situation it is not clear, when the actual disaster will occur, e.g. after a bomb threatening it is usually not known if or when the bomb will detonate. In such a situation evacuating people using quickest transshipments is not a good idea as it is not clear whether it is even possible to evacuate all people. Better suited for such situations are earliest arrival transshipments, which additionally have the property that as much flow as possible has arrived at the sinks at every point in time simultaneously. Thus, even if it is not possible to save all endangered people, when using earliest arrival transshipments, it is at least ensured that as many people as possible are rescued. However, the problem with earliest arrival transshipments is that they do not always exist. Furthermore, it is unlikely that polynomial time algorithms for earliest arrival transshipment problems do exist as it was recently shown that computing them is NP-hard.
One special case of dynamic networks in which earliest arrival transshipments do exist in general, are dynamic networks with only a single sink. For this special class of networks we present the first polynomial space algorithm for solving earliest arrival transshipment problems. In particular our algorithm does not require any form of expansion of the original dynamic network. This solves a problem which has been open for more than ten years.
In dynamic networks with multiple sinks, earliest arrival transshipments do not exist in general and so far not much research has been put into developing efficient algorithms for computing earliest arrival transshipments in multiple sink networks (in case of existence). We present the first polynomial space algorithm that checks whether an earliest arrival transshipment does exist and computes it in case of existence for the special case of earliest arrival transshipment problems in dynamic networks with multiple sinks and a single source, and tight problems in general networks.
Viele Aspekte unseres Alltags, von denen wir erwarten, dass sie "einfach funktionieren", sind auf bestimmte Optimierungsprozesse angewiesen, die oft in einem Netzwerk stattfinden. Von Straßennetzen, Eisenbahnnetzen oder Stromnetzen bis hin zum Telekommunikationsnetz des Internets und den von sozialen Netzwerken induzierten Netzwerken: Die Liste der Strukturen, die als Netzwerke modelliert werden können, ist lang und Optimierungsprozesse in diesen Netzwerken sind essenziell in unserem täglichen Leben.
In vielen Netzwerkoptimierungsproblemen besteht das Ziel darin, Dinge effizient durch das Netzwerk zu transportieren, z. B. Menschen, Objekte oder abstraktere Dinge wie die Informationen, die Sie über ein soziales Netzwerk erhalten oder den Film, den man streamen möchte. Oft muss eine große Menge des gleichen Gutes auf einmal transportiert werden, wie die große Anzahl von Zeitungen, die jeden Morgen geliefert werden, die Menge an Daten, die durch das Kommunikationsnetz fließen, wenn man die letzte Folge der Lieblingsfernsehsendung streamt, oder die Elektrizität, die benötigt wird, um das örtliche Krankenhaus zu versorgen.
Solche Transportprobleme führten vor mehr als 90 Jahren zur Entwicklung von statischen Netzwerkflüssen. Im Kontext vieler Optimierungsprobleme in Netzwerken ist es wesentlich, dass eine bestimmte Frist eingehalten wird und dass es Zeit braucht, eine Ware entlang einer Kante des Netzes, z.B. entlang einer Straße oder eines Stromkabels, zu transportieren. Solche Eigenschaften sind im klassischen statischen Netzwerkmodell nicht enthalten. Hier kommen dynamische Netzwerke und zeitabhängige Flüsse zum Tragen, die in der Lage sind, zeitliche Aspekte von Transportproblemen zu modellieren. In dieser Arbeit untersuchen wir solche zeitabhängigen Flüsse. Insbesondere konzentrieren wir uns auf zwei klassische zeitabhängige Flussprobleme, die besonders im Kontext der Evakuierungsplanung nützlich sind. Für beide Probleme präsentieren wir neue und effizientere Algorithmen für deren Lösung, welche Verbindungen zwischen dem spezifischen Flussproblem und geeignet ausgewählten submodularen Funktionen ausnutzen.
Wenn man Menschen aus einer gefährlichen Situation evakuiert, ist es das wichtigste Ziel, alle Menschen so schnell wie möglich zu retten. Diese Eigenschaft wird von Quickest-Transshipments modelliert, der ersten Klasse von zeitabhängigen Flüssen, auf die wir uns in dieser Arbeit konzentrieren. Der Input eines Quickest-Transshipment-Problems ist ein dynamisches Netzwerk mit Quellen und Senken mit Angebot und Nachfrage und das Ziel ist es, einen zeitabhängigen Fluss zu finden, der Angebot und Nachfrage so schnell wie möglich erfüllt. Das erste Hauptresultat in dieser Arbeit ist ein neuer stark polynomieller Algorithmus für das Quickest-Transshipment-Problem, der den bisher besten Algorithmus für dieses Problem, den Algorithmus von Hoppe und Tardos, wesentlich verbessert. Unser Algorithmus nutzt eine Verbindung zwischen Quickest-Transshipments und bestimmten submodularen Funktionen aus und wir beweisen, dass eine Lösung für das Quickest-Transshipment-Problem im Wesentlichen nur durch eine parametrische Minimierung einer parametrisierten submodularen Funktion gefunden werden kann. Mit unserem Algorithmus erreichen wir die erste Verbesserung für das Lösen des Quickest-Transshipment-Problems in mehr als 20 Jahren.
Bei der Evakuierung von Personen mit Quickest-Transshipments werden alle Menschen so schnell wie möglich gerettet. In vielen gefährlichen Situationen ist jedoch nicht klar, wann die tatsächliche Katastrophe eintreten wird, z.B. ist nach einer Bombendrohung nicht bekannt, ob und wann genau die Bombe explodieren wird. In einer solchen Situation ist die Evakuierung von Menschen mit Quickest-Transshipments eine schlechte Strategie, da man nicht weiß, ob es überhaupt möglich ist, alle Menschen zu evakuieren. Besser geeignet für solche Situationen sind Earliest-Arrival-Transshipments, die zusätzlich die Eigenschaft haben, dass sie an jedem Zeitpunkt maximal sind, also, dass zu jedem Zeitpunkt so viel Fluss wie möglich an den Senken angekommen ist. Selbst wenn es nicht möglich ist, alle gefährdeten Personen zu retten, ist bei der Verwendung von Earliest-Arrival-Transshipments zumindest sichergestellt, dass so viele Menschen wie möglich gerettet werden. Ein Problem im Kontext von Earliest-Arrival-Transshipments ist allerdings, dass sie nicht immer existieren. Darüber hinaus ist es unwahrscheinlich, dass polynomielle Algorithmen für Earliest-Arrival-Transshipment-Probleme existieren, denn es wurde kürzlich gezeigt, dass ihre Berechnung NP-schwer ist.
Ein spezieller Fall von dynamischen Netzwerken, in denen Earliest-Arrival-Transshipments immer existieren, sind dynamische Netzwerke mit nur einer einzigen Senke. Für diese spezielle Klasse von Netzwerken präsentieren wir den ersten PSPACE Algorithmus für die Lösung von Earliest-Arrival-Transshipment-Problemen. Insbesondere benötigt unser Algorithmus keine Form der Expandierung des ursprünglichen dynamischen Netzwerks. Dies löst ein Problem, das seit mehr als zehn Jahren offen ist. In dynamischen Netzwerken mit mehreren Senken gibt es im Allgemeinen keine Earliest-Arrival-Transshipments. Deshalb wurde bisher nicht viel Forschung in die Entwicklung effizienter Algorithmen zur Berechnung von Earliest-Arrival-Transshipments in Netzwerken mit mehreren Senken investiert (für den Fall, dass diese existieren). In dieser Arbeit präsentieren wir den ersten PSPACE Algorithmus, der prüft, ob ein Earliest-Arrival-Transshipment existiert und ein solches Transshipment im Falle der Existenz berechnet für den Spezialfall von dynamischen Netzwerken mit nur einer Quelle und mehreren Senken und für spezielle Earliest-Arrival-Transshipment-Probleme in allgemeinen Netzwerken.
