direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

There is no English translation for this web page.

Wiebke Höhn: Single machine scheduling with weighted non-linear cost

We consider the problem of scheduling jobs on a single machine. Given a non-linear cost function, we aim to compute a schedule minimizing the weighted total cost, where the cost of each job is defined as the cost function value at the job's completion time. We address exact solution methods as well as approximation algorithms. Concerning the former, great effort has been made to develop fast algorithms for the case of quadratic costs. The efficiency of these methods heavily depends on the utilization of structural properties of optimal schedules such as order constraints, i.e., sufficient conditions for pairs of jobs to appear in a certain order. We enhance the map of known order constraints, and evaluate the performance of the different constraints in an experimental study. On the approximation side, we analyze well-known Smith's rule for convex or concave cost functions by reducing  the task of determining a worst case problem instance to a continuous optimization problem, which can be solved by standard algebraic or numerical methods. For polynomial cost functions with positive coefficients it turns out that the tight approximation ratio can be calculated as the root of a univariate polynomial. This is joint work with Tobias Jacobs from NII Tokyo, Japan.

Martin Trapp: Slope Scaling for Multicommodity Multicapacitated Fixed-Charge Network Flow Problems

As a special form of the Capacitated Network Design Problem, the Fixed Charge Network Flow Problem is NP hard and cannot be approximated within certain bounds. Therefore, we require appropriate heuristics to solve it in practice. In this talk, an adapted Slope-Scaling procedure for the given problem will be discussed. While in the single-commodity case this procedure is very intuitive and powerful, it requires several modifications for the multicommodity case with multiple capacities.

Philipp von Falkenhausen: Optimal Cost Sharing Protocols for Scheduling Games

We consider the problem of designing cost sharing protocols to minimize the price of anarchy and stability for a class of scheduling games. Here, we are given a set of players, each associated with a job of certain non-negative weight. Any job fits on any machine, and the cost of a machine is a non-decreasing function of the total load on the machine. We assume that the private cost of a player is determined by a cost sharing protocol. We consider four natural design restrictions for feasible protocols: stability, budget balance, separability, and uniformity. While budget balance is self-explanatory, the stability requirement asks for the existence of pure-strategy Nash equilibria. Separability requires that the resulting cost shares only depend on the set of players on a machine. Uniformity additionally requires that the cost shares on a machine are instance-independent, that is, they remain the same even if new machines are added to or removed from the instance. We call a cost sharing protocol basic, if it satisfies only stability and budget balance. Separable and uniform cost sharing protocols additionally satisfy separability and uniformity, respectively. For n-player games we show that among all basic and separable cost sharing protocols, there is an optimal protocol with price of anarchy and stability of precisely the n-th harmonic number. For uniform protocols we present a strong lower bound showing that the price of anarchy is unbounded. Moreover, we obtain several results for special cases in which either the cost functions are restricted, or the job sizes are restricted. As a byproduct of our analysis, we obtain a complete characterization of outcomes that can be enforced as a pure-strategy Nash equilibrium by basic and separable cost sharing protocols.

Yann Disser: Mapping polygons with simple agents

We consider the exploration of a simple polygon P by an agent that moves from vertex to vertex along edges of the visibility graph. The visibility graph has a node for every vertex of P and an edge between two vertices, if they see each other, i.e., if the line segment connecting them lies in P entirely. While located at a vertex, the agent is capable of ordering the vertices it sees in counter-clockwise order as they appear along the boundary. Other than that, distant vertices are indistinguishable to the agent. We consider various extensions to the agent model, with the goal of finding minimal models that empower the agent to infer the visibility graph of its environment. We investigate one such model in detail. This model assumes that an upper bound on the number of vertices is known to the agent a priori and allows to distinguish whether the angle between two lines of sight is convex (<=PI) or reflex (>PI). We show that such an agent is always capable of reconstructing the visibility graph of P. We also show that multiple identical, indistinguishable and deterministic such agents can position themselves such that they mutually see each other, i.e., such that their positions induce a clique in the visibility graph.

Daniel Schmand: Ein Algorithmus für das verallgemeinerte Zuordnungsproblem und dessen Performance

Beim verallgemeinerten Zuordnungsproblem werden verschiedene Prozesse Maschinen zugeordnet, wobei jede Zuordnung unterschiedliche Kosten verursacht und verschieden große Kapazitäten der Maschine in Anspruch nimmt. Das Ziel ist es, die Kosten der Zuordnung zu minimieren, wobei die Kapazitätsgrenzen der Maschinen eingehalten werden müssen.
Man kann zeigen, dass allein das Finden einer zulässigen Lösung NP-schwer ist. Es wird daher hier ein sehr schneller Approximationsalgorithmus von Shmoys und Tardos dargestellt, der die Kapazitätsgrenze der Maschinen um bis zu 100% überschreitet, aber dessen Lösungswert mindestens so gut wie der einer Optimallösung ist. Wir betrachten die Laufzeit des Algorithmus und die Güte der Lösung anhand von Testinstanzen aus der OR-Library.

Veronika Günther: Flussalgorithmen zur Optimierung der Grünflächenversorgung in Großstädten

Die Qualität einer Großstadt lässt sich mit Hilfe vieler verschiedener Kriterien beschreiben. Eines ist die Versorgung der Einwohner mit Grünflächen im Naherholungsbereich, oder anders: Wie viel Quadratmeter Grünfläche stehen einem Einwohner im Umkreis von höchstens 1500 Metern zur Verfügung?

Meine Diplomarbeit beinhaltet unter Anderem eine Analyse des Ist-Zustandes unter verschieden Aspekten, wie z. B. die Entfernung oder die Auslastung der Grünflächen und soll nach Möglichkeit auch zukunftsweisende Planungen liefern.

Dieses Problem lässt sich in die Gruppe der Network Flow Problems eingliedern. In meinem Einstiegsvortrag möchte ich erklären wie ich dieses Problem in die Flusstheorie eingebettet habe und erste Lösungen präsentieren.

Michael Bastubbe: Algorithmen zum Erkennen von Blockstrukturen in Matrizen

Matrizen sind ein wichtiges Hilfsmittel zum Darstellen von Instanzen zahlreicher mathematischer Probleme. Zu vielen dieser Problemen (z.B. dem Lösen von linearen Gleichungssystemen und dem Lösen von MIPs) gibt es algorithmische Ansätze, die ausnutzen, dass die Nichtnulleinträge der instanzbeschreibenden Matrix in einer speziellen Blockstruktur angeordnet sind. Wir werden zwei  Blockstruckturen betrachten, die sogenannte k-Arrowhead Form (k-Arh) und die Bordered k-Block Diagonal Form (k-Bbd). Die Nichtnulleinträge sind jeweils in k Blöcken entlang der Diagonalen angeordnet. Davon ausgenommen sind die Nichtnulleinträge der untersten Zeilen bei der k-Bbd bzw. bei der k-Arh die untersten Zeilen und die rechtesten Spalten. Dieser Ausnahmebereich wird Border genannt.

In diesem Vortrag betrachten wir die zwei folgenden Optimierungsprobleme: Gegeben sind eine Matrix A, eine natürliche Zahl k und Blockgrößenschranken. Wir suchen nach einer Permutation der Zeilen und Spalten von A, so dass die permutierte Matrix in k-Arh bzw. in k-Bbd ist und den Blockgrößenschranken genügt. Dabei soll die Gesamtanzahl der Zeilen und Spalten in der Border minimal sein.

Wir werden sehen, dass beide Probleme NP-schwer sind. Für jedes Problem werden wir zwei Heuristiken vorstellen. Jede dieser Heuristiken löst ein Graph- bzw. Hypergraphpartitionierungsproblem auf einem speziellen Graph. Anschließend werden zwei IP-Modelle vorgstellt, mit denen beide Probleme exakt gelöst werden können. Schließlich werden die Rechenergebnisse, der implementierten Algorithmen vorgstellt.

Marlen Schwengfelder: Reduktion komplexer Graphen bei der Simulation von Evakuierungsszenarien

Bei der Simulation von Evakuierungen werden im Evakuierungstool ZET Graphen aufgebaut, die durch eine Vielzahl von Knoten und Kanten gekennzeichnet sind. Dadurch ist unter anderem die Laufzeit der darauf angewandten dynamischen Flussalgorithmen sehr hoch. Ziel meiner Masterarbeit ist es, Konzepte zur Reduktion der entstehenden Graphen zu entwickeln. Dabei soll das Originalnetzwerk hinsichtlich kürzester Wege sowie der sich ergebenden Flusswerte möglichst gut approximiert werden. Im dazugehörigen Einstiegsvortrag werden die Problemstellung sowie erste Lösungsansätze dargestellt.

Michael Müller: MinCostFlow-Algorithmen in zeitexpandierten Netzwerken

Das allgemeine dynamische kosten-minimale s-t-Flussproblem ist schwach NP-schwer. Man kann das Problem aber in pseudopolynomialer Zeit lösen, mit dem Konzept vom zeitexpandierten Netzwerk. Auf dieses spezielle Netzwerk lassen sich dann alle bekannten statischen Netzwerkalgorithmen für kosten-minimale Flüsse anwenden (wie z.B. Successive Shortest Path, Cycle Canceling etc.). Ein großer Nachteil dabei ist, dass die Instanzen sehr groß werden und die Algorithmen u.U. sehr viele Iterationen benötigen um das Problem zu lösen.

Dieses Verfahren wird im Rahmen des ZET-Evakuierungstools bereits so eingesetzt.

Meine Diplomarbeit befasst sich damit, zu untersuchen, ob sich ausgewählte statische MinCostFlow-Algorithmen verbessern lassen, wenn man sie an die spezielle Struktur der zeitexpandierten Netzwerke anpasst. Ziel wäre es, neben den Erkenntnissen, einen ggf. verbesserten Algorithmus in ZET einzubetten.
Ich werde im Vortrag auf die Problemstellung eingehen und einen ersten verbesserten Algorithmus vorstellen.

Ágnes Cseh: Stable flows over time

The well-known notion of stable matchings can be extended in several interesting ways, one of them operates with network flows. Some features of stable matchings are inherited by stable flows, but not all of them, for example the Gale-Shapely algorithm does not run in polynomial time on the second problem. 

Introducing time to the model brings up several questions regarding existence, algorithms to find stable flows over time, flow decompositions, waiting at nodes, etc. Apart from the static stable flow problem these topics will be sketched briefly in the talk and studied in my Masters' Thesis. 

Applications can be found to the subject: stable flows naturally model real-life market situations, adding time to the framework makes it even more realistic.

Alexander Richter: Multicommodity Multidimensional Covering Problems with Applications To Transportation

In this talk we look at a  Multicommodity Multidimensional Covering problem that arises as a subproblem in a model for transportation problems in logistics. In a first part we explore  similarities to the well known SetCover problem and present theoretical implications.
In a second part present a family of greedy algorithms that aim at producing approximate solutions in very fast running times. To further reduce the running times, we also provide methods that only estimate the cost of an optimal solution and do not give a solution explicitly. Finally, we present test results
on real world instances and outline a trade-off between running times and solution quality.

Wolfgang Welz: Howto: Parallel Programming for GPUs

There is a trend in high-performance computing to use special-purpose hardware originally designed for 3D graphics for solving general-purpose computing problems.
The advantage of such graphics processing units (GPUs), which can be found in any modern personal computer, is that they offer enormous peak performance at relatively low costs.

In this talk, we will give a short introduction on how the Open Computing Language (OpenCL) is used to write and execute C-functions on graphics card. These cards provide a high degree of parallelism by being able to perform over 1000 operations simultaneously.
This talk is focusing on the fundamental differences between GPUs and conventional microprocessors and their influence on the theoretical and practical development of scalable parallel programs, especially in combinatorial optimization.

In this context, we will also introduce a new approach that allows transparent and automatic scaling of existing OpenCL programs so that they can benefit from the additional computational power of multiple graphics cards in one computer. This approach uses an additional layer above the existing OpenCL implementation to assign and schedule the commands and functions on all available graphics cards.

Michael Lüttge: Ein Dekompositions-Ansatz zur Kostenoptimierung von ausfallsicheren längenbeschränkten Mehrgüterfluss-Netzen

Thema meiner Diplomarbeit war, den Dekompositionansatz von Benders zur Kostenoptimierung von ausfallsicheren, längenbeschränkten Mehrgüterflussnetzen unter Verwendung der Software SCIP zu implementieren. Zusätzlich sollte durch Modifikation des zugrundeliegenden Modells sowie durch Erweiterung der Lösungssoftware die Laufzeit zur Berechnung der Lösung mit der implementierten Anwendung beschleunigt werden.

Um das Problem als ganzzahliges Optimierungsproblem zu modellieren, stelle ich zunächst die Graphenerweiterung von Gouveia vor. Anschließend gehe ich auf den auf diesem Modell basierenden Ansatz zur Benders Dekomposition ein. Ich stelle eine Modellerweiterung vor, welche aus dem ursprünglichen Problem ohne die Längenbeschränkung hergeleitet wurde. Zusätzlich beschreibe ich eine eigens entwickelte Heuristik. Beide Ansätze hatten das Ziel, den implementierten Solver zu beschleunigen. Zum Schluss präsentiere ich einige Ergebnisse meiner Testreihen um zu zeigen, ob und inwieweit diese Ziele erfüllt wurden.

Robert Zimmermann: Rekonstruktion cross-cut und längs-cut geschredderter Dokumente mit Multicommodity Flows auf Basis paarweiser Scores

Abhängig von der Bauweise eines Schredders werden Dokumente entweder in schmale Streifen (längs-cut) oder durch zusätzliche horizontale Schnitte in kleinere Streifen zerschnitten (cross-cut). Um den Inhalt dieser geschredderten Dokumente wieder lesbar zu machen, müssen diese rekonstruiert werden. Die Entwicklung von Algorithmen zur Rekonstrukton dieser Dokumente ist das Hauptziel der Arbeit. Grundlegend dafür werden die Schredderstreifen nach Breite und Höhe je Schnitt in mehrere Kategorien klassifiziert, wodurch die Ableitung von Position und Lage der Schredderstreifen innerhalb des zu rekonstruierenden Dokuments ermöglicht wird. Es wird eine Analyse der Komplexität der Rekonstruktion von Dokumenten durchgeführt. Dazu wird die mögliche Anzahl aller Rekonstruktionen betrachtet und die Komplexität der Probleme bewiesen. Auf Grundlage dessen werden Verfahren entwickelt, die auf Basis gegebener paarweiser Scores Dokumente so zusammensetzen, dass die Summe der verwendeten Scores zwischen den Schredderstreifen im rekonstruierten Dokument maximal oder eine Annäherung daran ist. Im Anschluss daran wird die Implementierung der Algorithmen beschrieben und anhand geschredderter Dokumente zur Anwendung gebracht. Zudem wird die Qualität der von den unterschiedlichen Algorithmen erzeugten Ergebnisse miteinander verglichen. In meinem Abschlussvortrag werde ich den Inhalt meiner Diplomarbeit kurz vorstellen.

Christoph Stettin: Eine Greedy Heuristik für das rooted Incremental Connected Facility Location Problem

In meinem Vortrag werde ich das rooted Incremenental Facility Location Problem (rooted IConFl) und eine Greedy Heuristik für dieses Problem vorstellen. Das rooted IConFl weist Ähnlichkeiten zum Connected Facility Location Problem (ConFl) auf, es ist aber nicht nur eine Periode gegeben, sondern es sind im rooted IConFl mehrere Perioden gegeben. Für das ConFl liefert die GRASP Heuristik Ergebnisse, die für die getesteten Instanzen weniger als 10 % von einer Optimallösung entfernt sind. Die GRASP Heuristik verfolgt einen „greedy“ Ansatz: es werden nacheinander „günstige“ Facilities ausgewählt und geöffnet. Meine Greedy Heuristik für das rooted IConFl verfolgt den selben Ansatz: Es werden „günstige“ Facilities ausgewählt und geöffnet. In meinem Vortrag werde ich darauf eingehen, welche Facilities ausgewählt werden sollten, wie gut die Ergebnisse der Greedy Heuristik sind und welche lokalen Verbesserungsverfahren angewandt werden können.

Roman Rischke: "Ein neues Konzept für die zweistufige robuste kombinatorische Optimierung"

In der klassischen Optimierung wird eine Probleminstanz üblicherweise durch einen Satz von (nominalen) Daten eindeutig beschrieben. In der Praxis jedoch ist die exakte Bestimmung der (nominalen) Eingabe-Daten meist unmöglich oder nur unter sehr hohem Aufwand realisierbar. Beispielhafte Gründe dafür sind Messfehler, die nicht restlos ausgeschlossen werden können und die Unfähigkeit, zukünftige Ereignisse mit Bestimmtheit vorherzusagen. Entscheidungen müssen also sehr häufig auf der Grundlage eines Raums an möglichen Szenarien getroffen werden. Ein etablierter Ansatz, mit dieser Datenunsicherheit umzugehen, ist die robuste Optimierung.

 

Im Vortrag wird zunächst am Beispiel der robusten linearen Optimierung und anhand eines konkreten zweistufigen robusten kombinatorischen Optimierungsproblems die Grundidee der robusten Optimierung verdeutlicht. Dabei soll insbesondere deutlich werden, dass in der robusten Optimierung der Szenarioraum recht willkürlich beschränkt wird. Ein alternativer Ansatz hierzu stellt die Bepreisung der Szenarien dar. Dieser Ansatz und das inbegriffene Problem des Gegenspielers werden im Vortrag für die zweistufige robuste kombinatorische Optimierung anhand konkreter Beispiele vorgestellt.

Nicole Megow: Scheduling to meet deadlines: online algorithms and feasibility tests


In this talk I will present recent results and open questions in the context of scheduling real-time jobs with hard deadlines on m parallel machines. Each job has a processing time and a deadline, and the objective is to schedule jobs so that they complete before their deadline. It is known that even when the instance is feasible it may not be possible to meet all deadlines when jobs arrive online over time. Therefore, we consider settings in which the online algorithm has additional resources, such as higher speed or more machines, than the optimal offline algorithm that knows all jobs in advance.

Inken Olthoff: Primal Heuristics for the Welding Cell Problem

In the metalworking industry, automation plays a major role. One of the automated processes is the welding of points on components with the aid of robots. The Welding Cell Problen (WCP) is to find a shortest tour for each of these robots such that every weld point is handled exactly once. Additionally, the robots have special properties that allow a particular robot to weld specific points only. Furthermore, collisions between robots are forbidden. The WCP is NP-hard. In the presented thesis, we extended an existing WCP-solver by adding primal heuristics. Their goal is to find early feasible solutions and to improve suboptimal ones. We present ideas for different primal heuristics and several variants of these. Afterwards, we discuss computational results and compare variants of the heuristics, the impact of single heuristics and some combinations of them.

Daniela Luft: Single Machine Scheduling mit monomischer Zielfunktion in den Fertigstellungszeiten

Beim Single Machine Scheduling Problem soll für eine Maschine und eine
gegebene Menge von Jobs ein optimaler Zeitplan aufgestellt werden. Im
betrachteten Problem besitzt jeder Job eine gegebene Bearbeitungszeit und
ein gegebenes Gewicht. Ziel ist es, die gewichtete Summe der
Fertigstellungszeiten der Jobs zu minimieren, wobei die
Fertigstellungszeiten monomisch (z.B. alle quadratisch) in die Zielfunktion
eingehen. Hinreichende Bedingungen dafür, dass zwei Jobs in einer bestimmten Reihenfolge in einem optimalen Schedule auftreten, nennt man Order Constraints. Für quadratische Kosten existieren bereits eine Reihe von Order Constraints, jedoch sind für den allgemeinen monomischen Fall kaum Resultate bekannt. Daher soll Ziel meiner Arbeit sein, die bereits bekannten
Constraints (für den quadratischen Fall) auf den allgemeinen monomischen
Fall zu übertragen. Zudem sollen unterschiedliche Formulierungen für das
Single Machine Scheduling Problem aufgestellt werden und unter Hinzunahme
der Order Constraints exakt gelöst werden.
Im Vortrag werden unterschiedliche globale Order Constraints vorgestellt
sowie zwei gemischt-ganzzahlige Formulierungen.  Zudem sollen erste
Resultate der experimentellen Untersuchung der in SCIP implementierten MIPs vorgestellt werden.

Seminar on Routing Aspects: Felix König, Thomas Pajor and Tobias Pröger

This week's seminar hosts three short talks on routing brought to you by the eCOMPASS project (http://www.ecompass-project.eu/), which will be introduced briefly by Christos Zaroliagis, CTI Patras. The aim is to encourage interested researchers to contribute in the algorithmic quest towards tomorrow's advanced car navigation engine.

Felix König, TomTom:
"Future Directions in Car Navigation"

In recent years, TomTom's car navigation algorithms have progressed significantly. Key features now include dynamic routing with time-dependent travel times based on historical traffic data, advanced preprocessing techniques for extremely fast route queries, and reactivity to real-time online traffic updates. However, many algorithmic challenges remain. This talk gives a brief introduction to the state-of-the-art at TomTom before pointing out interesting directions for future research and exciting possibilities for cooperations with academic researchers.

 

Thomas Pajor, KIT:
"Customizable Route Planning"

We present an algorithm to compute shortest paths on continental road
networks with arbitrary metrics (cost functions). The approach supports
turn costs, enables real-time queries, and can incorporate a new metric
in a few seconds; fast enough to support real-time traffic updates and
personalized optimization functions. The amount of metric-specific data
is a small fraction of the graph itself, which allows us to maintain
several metrics in memory simultaneously.

Joint work mit Daniel Delling, Andrew Goldberg, Ilya Razenshteyn und
Renato Werneck.

Tobias Pröger, ETH Zürich:
"A Novel Technique to Handle Uncertainty in Optimization Problems"

Suppose that we want to travel from A to B, and we are given a graph where
expected travel times are assigned to the edges. However, in reality, these
times might be different due to traffic congestion or road work. Thus, the
result that "classical" algorithms return for such optimization problems with
"uncertainty" should no longer be accepted as the obvious ultimate solution.
Instead, we assume that we have two possible problem instances that share the topology (e.g. the edges of the underlying graph), but differ due to noise
(e.g. the edge weights are slightly different). We can also assume that we
have no further information about the noise. A new approximation set based
approach is presented, which uses sets of solutions that approximate the
optimum within some factor. We also show some settings where the new approach can be applied.

Sandro Bosio: A temporal extension of combinatorial problems

Dynamic optimization problems are widely studied in many areas of mathematics and control theory. However, relatively little is known about dynamic counterparts of purely combinatorial problems, except for specific structures such as network flows and scheduling problems. In this talk, we introduce a general setting for the temporal extension of combinatorial optimization problems, and mention some applications and special cases. We also provide a complexity study that includes a 1.691030-\beta-approximation algorithm for the temporal extension of any combinatorial problem whose set system is an independence system and that admits a beta-approximation algorithm for linear optimization. This algorithm considerably generalizes the alpha-approximation total-value heuristic by Kohli and Krishnamurti (1992) for integer knapsack, which turns out to be a special case of dynamic optimization problem.

Joint work with David Adjiashvili and Robert Weismantel.

Britta Peis: Resource buying games

In resource buying games, the players jointly buy a subset of a given resource set (e.g., machines, edges, etc.). Just like in classical congestion games, each player has a predefined family of subsets of the resources
from which she needs at least one to be available (e.g., the machines on which the player's job can be processed, or the paths connecting two player-specific terminals in a  graph). However, a resource is only available if the sum of payments of all players cover the (load-dependent) cost of that resource. Thus, in these games a strategy of a player is a tuple consisting of one of her
resource sets together with a payment vector indicating how much she is willing to contribute towards the purchase of each resource.
During the talk, we study the existence and computability of pure Nash equilibria (PNEs) in resource buying games.
While there exist very simple connection games (e.g. those where each player wants to connect two terminals) without PNE, we will see that almost everything is fine as soon as we consider games in which each players strategy set is the base set of a matroid.

Martin Niemeier: Scheduling with an orthogonal resource constraint

We address a scheduling problem that arises in  highly parallelized environments like modern multi-core CPU/GPU computer architectures. Here simultaneously active jobs share a common limited resource, e.g. a memory cache. The scheduler must ensure that the demand for the common resource never exceeds the available capacity. This introduces an orthogonal  constraint to classical minimum makespan scheduling problems.


After giving a brief overview over the complexity landscape of this problem class,
we present a (2+eps)-approximation algorithm to compute non-preemptive schedules on identical machines which relies on the interplay of several classical and modern techniques in scheduling.

This is joint work with Andreas Wiese.

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Auxiliary Functions

This site uses Matomo for anonymized webanalysis. Visit Data Privacy for more information and opt-out options.