direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Nicole Megow: Advertising instance-sensitive worst-case guarantees: robust sequencing examples

Sequencing problems with an unknown covering or packing constraint appear in various applications, e.g., in real-time computing environments with uncertain run-time availability. A  sequence is called $\alpha$-robust when, for any possible constraint, the maximal or minimal prefix of the sequence that satisfies the constraint is at most a factor $\alpha$ from an optimal packing or covering. It is known that the covering problem always admits a $4$-robust solution, and there are instances for which this factor is tight. For the packing variant no such constant robustness factor over all instances is possible. However, in both cases, many problem instances allow for a much better robustness guarantee than the pathological worst-case instances. In this work we aim for more meaningful, instance-sensitive robustness guarantees. We present an algorithm that constructs for each instance a solution with a robustness factor arbitrarily close to optimal. We hope that the idea of instance-sensitive  performance guarantees inspires to revisit other optimization problems and design algorithm tailored to perform well for each individual instance.

Manuel Schneider: Pure Equilibria in Bottlenec Gongestion Games with Elastic Demands

Bottleneck congestion games with elastic demands are a class of
strategic games in which players compete over a set of resources by
assigning a variable and unsplittable demand. The congestion cost for a player is determined by her most congested resource only.
Unlike in (weighted) congestion games, players are free to adapt to
the congestion on resources by choosing a non-negative demand in which
they use resources. Bottleneck congestion games with elastic demands can be used to model many real-world computer network routing applications
in which traffic is dependent on the congestion experienced by users.
However, it is unknown if, and under which assumptions, these games
admit pure strategy equilibria. In this talk we define bottleneck congestion games with elastic demands and show that they always admit pure equilibria
if resources are identical and cost functions are continuously
differentiable, strictly increasing and convex. In addition we state an algorithm capable of computing pure strategy equilibria for these games.

Daniel Karch: Wavelength Division Multiplexing Replacement Scheduling

During the last years, Wavelength Division Multiplexing (WDM) has become the reference technology adopted in optical networks to increase system capacity. In particular, the increase in capacity derives from the possibility of establishing multiple connections on the same optical fiber, by assigning each wavelength to a distinct connection. In this work we analyze the problem of migrating a network to a new technology: a new hardware technology is available and we want to update all the relevant elements of the network. While the installation takes place, the affected network element must be switched-off and connections that use it are temporarily disrupted. The installation cannot be performed on the whole network at the same time, since the number of technicians is limited. A key issue is thus to schedule the migration of the network components in such a way that the connection disruption is minimized. In this talk, I will present several ways to model the WDM Replacement Scheduling Problem as an ILP, and discuss their respective benefits and disadvantages. This is joint work with Andreas Bley and Fabio D'Andreagiovanni.

Andreas Schütz: Congestion Games with Multi-Dimensional Demands

A strategic game models an interaction of multiple players choosing their respective strategy simultaneously with the goal to minimize their private costs. A well-known and extensively studied subclass of strategic games is the class of weighted congestion games. Here the players compete for subsets of some shared resources whose costs depend on the number of players using them at the same time. Thereby, every player has a certain unsplittable demand which is independent of the resources. However, until now no research has been devoted to the case of multi-dimensional demands in the sense that every player has a demand vector with k>1 components. This generalization of the one-dimensional case allows for the modeling of applications in which the cost of a resource depends on multiple different demands, for example the transportation cost may depend on the weight and the volume of a shipment. The purpose of my master thesis is to analyze the existence of pure Nash equilibria in congestion games with multi-dimensional demands. These are stable states of the game where no single player can deviate unilaterally in a manner which is profitable to him. In the talk we will determine necessary and sufficient conditions which the players’ strategy spaces and the set of cost functions have to fulfill such that every congestion game with multi-dimensional demands possesses a pure Nash equilibrium.

Ágnes Cseh: Noble Matchmakers

Alvin Roth and Lloyd Shapley were awarded the Nobel Prize in Economics for their work on stable allocations this year. In this talk, we will give an insight into the mathematical concept and show how it can be used for decisions on markets where profit-maximizing is not the main aim. We will also sketch our algorithm for finding stable allocations on uncoordinated markets.

Ivana Ljubic: The Maximum Node-Weight Connected Subgraph Problem

The Maximum  Node-Weight Connected Subgraph Problem (MWCS) is the problem of finding a connected subgraph with maximum total weight in a node-weighted (di)graph. It belongs to the class of network design problems and has applications in various different areas such as forestry, wildlife preservation planning, system biology, computer vision, and communication network design.
In this talk I will introduce a new ILP formulation for the MWCS based on node variables only, which uses connectivity constraints based on node-separators. A theoretical comparison of  the strength of the new model versus the previously used MIP models is provided and the connected subgraph polytope associated with our new formulation is studied.
In our computational study, applications from system biology are considered and our new ILP model (i.e, the corresponding branch-and-cut algorithm) is computationally compared against the previously used MIP approaches for the MWCS.

This is a joint work with Eduardo Alvarez-Miranda and Petra Mutzel.

Michael Müller: Algorithmen für Minimalkostenflüsse in zeitexpandierten Netzen

Das dynamische Minimalkostenfluss-Problem (MCFOTP) ist schwach NP-schwer. Man kann das Problem jedoch in pseudopolynomieller Zeit mit dem Konzept des zeitexpandierten Netzwerks lösen. Auf dieses Netzwerk lassen sich alle bekannten Netzwerkalgorithmen für statische Minimalkostenflüsse anwenden (wie z.B. Successive Shortest Path (SSP) oder Cycle Canceling). Diese Algorithmen gehen dabei nicht explizit auf die sich wiederholende Struktur des zeitexpandierten Netzwerks ein.
Wir untersuchen die Struktur zeitexpandierter Netzwerke auf algorithmische Ausnutzung für statische Minimalkostenfluss-Algorithmen. Ziel ist es konkret, Laufzeit zu sparen durch die Verwendung gefundener kürzester Pfade zu anderen Zeitpunkten. Diese Erkenntnis nutzend, passen wir den Successive-Shortest-Path-Algorithmus an das Modell des MCFOTP ohne und mit Wartekosten in den Knoten an. Wir stellen die beiden so resultierenden Time-Expanded-Successive-Shortest-Path-Algorithmen vor. Darüber hinaus betrachten wir ihre Laufleistung gegenüber dem SSP-Algorithmus für den Fall ohne bzw. dem Successive-Earliest-Arrival-Augmenting-Path-Algorithmus für den Fall mit Wartekosten.

Kerstin Bodack: Kapazitierte Standortoptimierung mit integrierter Routenplanung: Algorithmen und Komplexität

Das kapazitierte Location Routing Problem kombiniert das kapazitierte Facility Location und das Vehicle Routing Problem. Die gleichzeitige Minimierung von Depoteröffnungs- und Tourkosten unter Beachtung der Depotkapazitäten führt zu einem Zielkonflikt zwischen einer guten Depotauslastung und kostengünstigen Touren. Das Finden einer zulässigen Lösung ist bereits NP-schwer. Hierzu wurden mehrere Heuristiken, die sehr große Instanzen in kürzester Zeit lösen können, entwickelt. Diese Instanzen wurden zufällig generiert, da bisher keine vergleichbaren Instanzen dieser Größenordnung in der Literatur zu finden waren. Zur Bestimmung der Qualität der berechneten Lösung, mussten zusätzlich differenzierte untere Schranken gefunden werden.

Stefan Gnutzmann: Standortplanung der Ticketautomaten zur elektronischen LKW-Maut

Am 1. Januar 2005 wurde in Deutschland ein Strecken bezo­genes elektro­nisches Maut­system auf den Autobahnen für Lastkraftwagen ab 12 t zulässigem Gesamt­gewicht eingeführt. Neben einer Bezahlung über Internet oder spezieller Bord­computer sind überwiegend in Deutschland knapp 3.500 Ticketauto­maten aufgestellt worden, an denen die Mautgebühr entrichtet werden kann.

Der Vortrag berichtet von dem Prozess der Standortplanung dieser Ticketautomaten ab der Entscheidung im Herbst 2000, sich an der Ausschreibung zu beteiligen, bis zum Anlauf des Systems im Januar 2005.

Die Ausschreibung des Verkehrs­ministe­riums legte als Eckwert nur die gesamte Fahrtenzahl im Jahr auf den Autobahnen fest, an die sich die Anbieter halten muss­ten, und schrieb Bedingungen vor, die bei der Aufstellung der Automaten zu beach­ten waren. Beschrieben wird, wie für die Angebotserstellung eine Datenbasis aus den Vorgaben konstruiert worden ist und die sich ergebenden großen Standort­prob­leme (etwa 2.250 Autobahn-Anschlussstellen und bis zu 7.000 potenzielle Automa­ten-Standorte) heuristisch gelöst wurden.

Nach Auftragserteilung wurde der Lösungsansatz verändert und laufend an neue Anforderungen angepasst, die aufgrund weiterer Vorgaben des Bundesamtes für Güterverkehr und im Zuge des Prozesses der Automatenaufstellung entstanden.

Der Vortrag zeigt exemplarisch, mit welchen Schwierigkeiten man bei der Umsetzung gelernter Methoden in der Praxis rechnen muss. Umgekehrt liefert die Praxis interes­sante Musterdaten, an denen sich neue Verfahren zur Standort­opti­mie­rung testen lassen können.

Mohsen Rezapour: Connected facility location with buy at bulk edge cost

In the connected facility location with buy-at-bulk edge costs problem we are given a subset of clients with positive demands and a subset of potential facilities with facility opening costs in an undirected graph with edge lengths obeying the triangle inequality. Moreover, we are given a set of access cable types, each with a cost per unit length and a capacity. The cost per unit capacity decreases from small to large cables by economies of scale. For interconnecting open facilities with each other core cables of infinite capacity must be used. The task is to open some facilities, connect these facilities by a core Steiner tree and construct a network of access cables such that the capacities installed on the edges suffice to simultaneously route the entire demand of each client to an open facility via a single path. The objective is to minimize the total cost of opening facilities, building the core Steiner tree among them, and installing the access cables. In this talk, we present the first constant-factor approximation algorithm for this problem. This is joint work with Andreas Bley.

Ulf Lorenz: Problemstellung und aktueller Stand in der mathematischen Forschung über Quantifizierte Lineare Programme; Technical Operational Research

Im ersten Teil des Vortrags wird ein Überblick über den Stand unserer Forschung an Quantifizierten Linearen Programmen (QLPs) gegeben. Bei QLPs handelt es sich um lineare Programme, deren Variablen alle mit Existenz- oder Allquantoren versehen werden. Wir haben polyedrische, komplexitätstheoretische und algorithmische Fragestellungen bearbeitet, und konnten auch einen Löser, der hauptsächlich auf Benders Dekompositionsmethode und dem Alphabeta-Algorithmus für Spielbaumsuche beruht, entwickeln. Zur Zeit liegt unser Fokus auf 0/1-QIPs, die zum einen sehr große Ähnlichkeit mit QSAT-Problemen aber auch mit 0/1-IP-Optimierungsproblemen haben. Wir stellen den Alphabeta-Algorithmus mit nicht-chronologischem Backtracking vor.

Im zweiten Teil des Vortrags möchten wir ein neues Forschungsgebiet vorstellen, das sich gerade im Fachbereich Maschinenbau der Technischen Universität Darmstadt zusammen mit der Mathematik entwickelt, das Technical Operational Research (TOR). TOR ist geprägt durch die Zusammenarbeit von Angewandter Mathematik, Maschinenbau und Informatik, und es gibt viele Parallelen zum klassischen OR. So werden z.B. mathematische Optimierungsmodelle, bevorzugt MIPs, aufgestellt und mittels brauchbarer Algorithmen gelöst. Unterschiede gibt es allerdings bei den "typischen" Nebenbedingungen der mathematischen Modelle.

Das Hauptziel von TOR ist es, Mathematiker, Informatiker und Maschinenbauer an der Schnittstelle von Lösungsfindung und Management zusammenzubringen. Unserer Beobachtung nach gibt es zwar mittlerweile eine ganze Reihe von Geldquellen und Projekten, die sich dieser Frage auch widmen, es scheint uns aber einen Mangel an der systematischen Untersuchung der Fragestellung "Wie bekommen wir es hin, dass Ingenieure und Mathematiker die richtigen technischen Modelle bauen und lösen" zu geben.

Kai-Simon Goetzmann: Theory and Practice of Multicriteria Optimization

In the first two years of my PhD I have worked on the theoretical properties of compromise and reference point solutions in multicriteria optimization. From September till December last year I stayed with the DECYTEC group of Francisco Ruiz in Malaga to look at practical applications of these methods.
In this talk I will present you some of the things I've done there and share my insights. In the first part, I will talk about the application of reference point methods to calculate synthetic sustainability indicators. The second part will be about the evaluation and comparison of genetic algorithms for multicriteria optimization by pictures, approximation factors and the hypervolume
indicator.

Robert Schweitzer: Kostenverteilungsfunktionen gemeinsam genutzter Ressourcen

Beim Kostenverteilungsmodell wird angenommen, dass sich mehrere Parteien eine Ressource teilen. Diese generiert bei den Spielern einen gewissen Nutzen, dessen Höhe nur von der Menge und der individuellen Nutzenfunktion des jeweiligen Spielers abhängt. Die Spieler agieren über ihre Nachfragemenge. Jeder Spieler wird dabei versuchen seinen individuellen Gewinn zu maximieren, welcher sich aus der Differenz von Nutzen und Kosten errechnet.

Die zentrale Beobachtung bei diesem Modell ist, dass der Gesamtgewinn nicht automatisch maximiert wird, wenn jeder Spieler seinen individuellen Gewinn maximiert. Der Gesamtgewinn ergibt sich dabei aus der ungewichteten Summe der Gewinne aller Spieler. Hätte ein Außenstehender sämtliche Informationen und dürfte dieser die Ressource gewinnmaximierend auf die Spieler verteilen, so könnte er dies effizienter tun.

Das Verhalten der Spieler lässt sich durch die Kostenverteilungsfunktion beeinflussen. Deshalb werden diese auf ihre Effizienz untersucht. Die Effizienz definiert sich dabei als der Quotient aus dem Gesamtgewinn individuell agierender Spieler und dem maximalen Gesamtgewinn. Dieser wird „Price of Anarchy“ genannt. Um diese Problematik zu verdeutlichen werden die drei Kostenverteilungsmethoden „Average Cost Pricing“, „Serial Cost Sharing“ und „Incremental Cost Sharing“ vorgestellt und gezeigt, dass jede von ihnen für verschiedene Kostenfunktionen die beste Alternative darstellt. Da es im Allgemeinen keine perfekte Lösung gibt, besteht das Ziel darin möglichst gute untere Schranken für den Price of Anarchy zu finden.

Es werden verschiedene Einschränkungen für die Kostenfunktion und die Spieleranzahl angenommen und gezeigt, wie sich diese auf den Price of Anarchy auswirken. Da keine der Funktionen dominant ist, werden sämtliche Ergebnisse für alle drei Funktionen dargestellt. Ohne Einschränkung an die Kostenfunktion beträgt die beste untere Schranke 1/n , wobei n die Anzahl der Spieler ist. Betrachtet man lediglich faire Kostenverteilungsfunktionen, bei denen Spieler mit einer größeren Menge mehr Kosten tragen als Spieler mit kleineren Mengen, so ist diese Schranke scharf.

Karl Däubel: Der Preis der Stabilität in Netzwerk-Design Spielen mit fairer Kostenaufteilung

In Netzwerk-Design Spielen mit mehreren egoistischen Spielern ist es von großem Interesse die Auswirkungen von strategischem Verhalten zu verstehen und zu analysieren. Dabei erhalten wir aus dem Verhältnis zwischen einem Nash-Gleichgewicht und einer globalen optimalen Lösung eine Gütegarantie dieses Gleichgewichts. Dieses Verhältnis kann allerdings durch die Wahl eines kostenintensiven Nash-Gleichgewichts linear in der Anzahl der Spieler sein. Auf der anderen Seite ist es ebenfalls möglich durch die geschickte Wahl eines Nash-Gleichgewichts dieses Verhältnis logarithmisch in der Anzahl der Spieler nach oben zu beschränken. Die Frage nach einer oberen Schranke für das Verhältnis zwischen einem preisgünstigen Nash-Gleichgewicht und einer optimalen Lösung ist insbesondere dann von Interesse, wenn in dem Netzwerk-Design Spiel eine übergeordnete Instanz existiert die Einfluss auf die Wahl der einzelnen Strategien hat und damit Einfluss auf die Gesamtkosten des Nash-Gleichgewichts.

Das Ziel meiner Bachelorarbeit war es daher den Preis der Stabilität, also das Verhältnis eines kostengünstigsten Nash-Gleichgewichts mit einer optimalen Lösung, in Netzwerk-Design Spielen näher zu betrachten. Neben einer oberen Schranke für das allgemeine Netzwerk-Design Spiel, habe ich mich mit diversen Spezailfällen beschäftigt, in denen der Preis der Stabilität nochmals verbessert werden konnte. Dieser Vortrag wird darüber einen genaueren Überblick geben.

Norman V. Backhaus: Paarweise Gleichgewichte in minimalen Aufwandspielen

Ein Contribution Game wird gespielt in einem (sozialen) Netzwerk, in dem die Spieler durch die Knoten repräsentiert sind. Jeder Spieler kann einen Tei eines gewissen Gutes (Geld, Zeit etc.) in die Beziehungen zu den an ihn angrenzenden Spieler investieren. Der Nutzen eines Spielers hängt von den Einsätzen der Spieler auf den adjazenten Kanten ab. Wir zeigen, dass in Spielen, in denen der Ertrag einer Kante lediglich vom Minimum der Einsätze der adjazentenSpieler abhängt, stets ein paarweises Gleichgewicht existiert. Paarweise Gleich-gewichte sind eine Verschärfung reiner Nash-Gleichgewichte, die sogar robust gegenüber der gleichzeitigen Abweichung zweier Spieler sind.

Jan-Philipp Kappmeier: How to Tikz

TikZ ist kein Zeichenprogramm, but it still allows to create nice and professional looking pictures for Latex based talks, Thus, we can improve the quality of our talks and papers.

This talk presents basic features for an easy beginning, including simple drawing functions, coordinates and plotting of data. It will continue with some more sophisticated features to give an overwiew of what is possible. After the talk, everyone should be able to use the help provided in the terrific TikZ & PGF manual to find additional tips and tricks.

Philipp von Falkenhausen: Convergence of Regret-Minimizing Algorithms in Atomic Splittable Routing Games

Algorithmic Game Theory employs a range of equilibrium concepts. Narrow concepts (pure, mixed Nash) have the drawback that they are hard to compute and may not exist in a particular game. Broader concepts (such as the coarse correlated equilibrium) do not have these drawbacks and incorporate more real-world characteristics, for example they can be `learned' if each agent uses a learning algorithm to choose his strategy.

In the first part of the talk, I give an introduction to such equilibria. Then, I analyze coarse correlated equilibria in atomic splittable routing games. I show an efficiency guarantee (POA = 3/2) that is as good as previously known tight guarantees for pure, mixed and correlated equilibria.

Sabine Werner: Robuste Matroide und Polymatroide

Die robuste Optimierung befasst sich mit der optimalen Entscheidungsfindung bei unsicheren Eingangsdaten. Das Ziel ist es, die worst-case Kosten einer Lösung zu optimieren. Wir betrachten für ganzzahlige Probleme den Ansatz der Gamma-Robustheit nach Bertsimas und Sim. Der Parameter Gamma gibt an, wie viele der Daten sich höchstens gleichzeitig ändern können.

Wir wollen jeweils Optimierungsprobleme über Matroiden und über ganzzahligen Polymatroiden im Kontext der Gamma-kostenrobusten Optimierung betrachten. Matroide sind fundamentale Objekte der reinen und angewandten Kombinatorik, da sie bereits durch den kanonischen Greedy-Algorithmus eindeutig charakterisiert sind. Polymatroide sind eine Verallgemeinerung von Matroiden in Hinblick auf deren polyedrische Beschreibung.

Theresa Thunig: Steuerung von Verkehrsflüssen in Mehrgüternetzwerken mit heterogenen Nutzern durch Mautgebühren

In Netzwerken ohne Maut minimiert jeder Nutzer seine Reisezeit. Dabei entsteht das sogenannte Nash-Gleichgewicht, bei dem sich kein Nutzer durch alleinigen Routenwechsel verbessern kann. Es ist bekannt, dass sich dieses stark vom Systemoptimum, der Minimierung der Gesamtreisezeit, unterscheiden kann. Die Frage ist, ob man durch die Einführung von Mautgebühren auf den Kanten erreichen kann, dass sich das Systemoptimum als Nash-Gleichgewicht im Netzwerk einstellt.

Für Mehrgüternetzwerke mit heterogenen Nutzern, das heißt, Nutzern, die unterschiedlich auf Maut reagieren, haben Fleischer, Jain und Mahdian 2004 die Exisitenz solcher Maut, die das Systemoptimum erzwingt, bewiesen. Ihr Beweis ist konstruktiv, sodass sich die entsprechende Maut mithilfe eines linearen Programms berechnen lässt. Fleischer, Jain und Mahdian zeigten außerdem, dass höchstens eine Maut nötig ist, die linear von der maximalen Latenzsensitivität der Nutzer und der maximalen Latenz einer Kante und exponentiell von der Anzahl der Kanten des Netzwerkes abhängt.

In meiner Bachelorarbeit habe ich mich genauer mit dieser oberen Schranke an die Mauthöhe in Mehrgüternetzwerken beschäftigt.Neben einem Beispiel, welches die Abhängigkeit der Maut von der maximalen Latenz einer Kante und der maximalen Latenzsensitivität der Nutzer zeigt, habe ich spezielle Mehrgüternetzwerke betrachtet, in denen die maximale Länge eines Weges beschränkt ist. Für diese Spezialfälle konnte die obere Schranke an die Mauthöhe verbessert werden. In diesem Vortrag möchte ich genauer auf diese Untersuchungen der oberen Schranke an die Mauthöhe eingehen.

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe

Diese Seite verwendet Matomo für anonymisierte Webanalysen. Mehr Informationen und Opt-Out-Möglichkeiten unter Datenschutz.