TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)Abstracts Dr.-Dipl.-Seminar

COGA 5-Wheel

Page Content

to Navigation

There is no English translation for this web page.

Julia Kitzmann: "Scheduling mit evolutionären Algorithmen im Luftverkehrsmanagement"

Julia Kitzmann
"Scheduling mit evolutionären Algorithmen im Luftverkehrsmanagement"

In dieser Bachelorarbeit werden bestimmte Scheduling Probleme, welche im Luftverkehrsmanagement auftreten, untersucht. Hierfür werden diese Scheduling Probleme als ein 1|r_j|\gamma Scheduling Problem (mit unterschiedlichen
Ausprägungen für \gamma ) klassiziert. Dabei wird die Komplexität verschiedener 1|r_j|\gamma Scheduling Probleme untersucht und die betrachteten Probleme als NP-vollständig identiziert.
Die Reihenfolgeplanung im Luftverkehrsmanagement erfolgt bereits mit Hilfe von verschiedenen Heuristiken, wie Take-Select und A*-Algorithmen. Auÿerdem wurden bereits Greedy, Tabu-Search und Branch & Bound implementiert und untersucht.

Eine weitere Möglichkeit, um NP-vollständige Probleme zu lösen, ist die Anwendung Evolutionärer Algorithmen. Das Hauptinteresse dieser Arbeit ist diesen gewidmet. Sie werden in allgemeiner Form eingeführt und ein für die Reihenfolgeplanung spezischer Evolutionärer Algorithmus vorgestellt. Die Implementation dieses Algorithmus wird mit unterschiedlichen Parametern und verschiedenen Instanzen von Scheduling Problemen des Air Trac Management Umfelds getestet. Diese werden sowohl untereinander als auch mit den bisher implementierten Algorithmen bezüglich Laufzeit und Güte verglichen. Durch die Auswertung dieser Ergebnisse wird der Einsatz von Evolutionären Algorithmen in der Reihenfolgeplanung des Luftverkehrsmanagement beurteilt und festgestellt, inwiefern Evolutionäre Algorithmen hierfür geeignet sind.

Kai-Simon Goetzmann: "Compromise Solutions in Multicriteria Optimization"

A popular concept in Multicriteria Optimization is that of Pareto optimality. Unfortunately, the number of Pareto optimal solutions is often exponential. To identify a single Pareto optimal solution, one often considers the weighted sum of all objectives to get a single-objective problem. This can lead to highly unbalanced solutions, though, even if perfectly balanced solutions exist. To overcome this problem, in the 70s Yu et al. proposed Compromise Solutions as an alternative.
Here, the ideal point is defined as an imaginary solution that takes the optimal value in each objective. A Compromise Solution is a feasible solution that minimizes the distance to this ideal point with respect to some norm. We consider the standard vector norms as well as a parametrized combination of the Manhattan and the maximum norm.
Compromise Solutions have the advantage that typically there is only one of them, and they are always Pareto optimal (except for the maximum norm).
We show that for a fixed, polynomially sized norm parameter any Pareto optimal solution also is a Compromise Solution. Furthermore, an approximation scheme for Compromise Solutions enables us to approximate the Pareto
set, by choosing different weights for the objectives. Compromise Solutions thus neatly fit into the popular concept of Pareto optimality.
Moreover, if good balanced solutions exist, they can be obtained by computing a Compromise Solution. The degree of balancing can be influenced by the choice of the norm parameter.

Kai-Simon Goetzmann: "Optimization over Integers with Robustness in Cost and Few Constraints"

We consider robust counterparts of integer programs and combinatorial optimization problems (summarized as integer problems in the following), i.e., seek solutions that stay feasible if at most Gamma-many parameters change within a given range.
While there is an elaborate machinery for continuous robust optimization problems, results on robust integer problems are still rare and hardly general.
We show that one can optimize or rho-approximate the robust (with respect to cost, or few constraints) counterpart of an integer problem if one can optimize or rho-approximate the original integer problem with respect to a piecewise linear objective (respectively piecewise linear constraints).
We demonstrate the applicability of our approach on two classes of integer programs, namely, totally unimodular integer programs and integer programs with two variables per inequality. Further, for combinatorial optimization problems our method yields polynomial time approximations and pseudopolynomial, exact algorithms for robust Unbounded Knapsack Problems.

Benjamin Labonté: "Effiziente Algorithmen zur Lösung von Min-Cost-Flow Problemen: Ein empirischer Vergleich verschiedener Techniken"

Im Rahmen dieser Bachelorarbeit wurden der Successive Approximation Push-Relabel Algorithmus und der Netzwerk Simplex Algorithmus zur Lösung von Min-Cost-Flow Problemen anhand von aktuellen Implementierungen von Andrew V. Goldberg (CS2) und Andreas Löbel (MCF) betrachtet.
Auf 2.300 eigenen Testinstanzen mit bis zu 47 Millionen Kanten wurden 14.000 Laufzeitmessungen durchgeführt, um das empirische Laufzeitverhalten der Algorithmen zu untersuchen. Die Ergebnisse wurden jeweils mit einer Regressionsanalyse ausgewertet. Durch die gefundenen Regressionsformeln kann die Laufzeit der Algorithmen auf dem Testrechner über ein Reihe von Instanzparametern geschätzt werden. Darüber hinaus wurden die Algorithmen auf bestimmten Graphenklassen
direkt verglichen, auf der Suche nach einem einfachen Instanzparameter mit dem entschieden werden kann, welcher Algorithmus zur Lösung besser geeignet ist.
Im Vortrag werden das Verfahren und die Ergebnisse des empirischen Vergleichs präsentiert und bestimmte Details der genannten Implementierungen vorgestellt, die sie zu den aktuell schnellsten Programmen zur Lösung von Min-Cost-Flow Problemen machen.

Ebrahim Nasrabadi: "Robust and Adjustable Robust Network Flows"

We study network flow problems in an uncertain environment from the viewpoint of robust optimization. In contrast to previous work, we consider the case that the network parameters (e.g., capacities) are known and deterministic, but the network structure (e.g., nodes and arcs) is subject to uncertainty. In this talk, we present the notion of robust and adjustable robust maximum flows in networks with node and arc failures. The adjustable robust model is a two-stage optimization approach as one performs a post-processing optimization step to adjust the solution after the realization of the failure in the network. This leads to a more flexible model and yields less conservative solutions compared to the robust model. While the robust maximum flow problem can be solved in polynomial time, the adjustable robust problem is NP-hard. We give a full characterization of the adjustable robust model and present the notation of adjustable robust minimum cuts. We show how to characterize the adjustable robust model as a two-player zero sum game. We prove the existence of a pure equilibrium in such games and extend the MaxFlow-MinCut Theorem to our setting. Moreover, we consider a path-based formulation of flows in contrast to the more commonly used arc-based version of flows. This would lead to a slightly different model of robustness for maximum flows. We analysis this problem as well and develop a simple linear program to obtain approximate solutions. Furthermore, we introduce the concept of adjustable robust maximum flows over time in networks with transit times on the arcs. Unlike the deterministic case, this problem is NP-hard on series-parallel graph even for the case that only one arc is allowed to fail. Joint work with Dimitris Bertsimas and Sebastian Stiller.

Martin Groß: "Generalized Maximum Flows over Time"

Andreas Schutt: Solving Resource-Constrained Project Scheduling Problems with Lazy Clause Generation

Resource-constrained project scheduling problems (RCPSP) are NP-hard problems which arise in many real-world problems as extensions, specialisations, or variations. They consist of activities consuming resources for their executions which are subjected to limited resource availability and precedence relations between pairs of activities. The goal is to find an optimal schedule that obeys the resource and precedence constraints. Lazy clause generation (LCG) is a constraint-based approach to solve combinatorial problems. At the moment, LCG is the best-performing exact method on RCPSPs and RCPSPs with minimal and maximal time lags from the standard benchmark library PSPLib for which it could close numerous open instances. Its strength comes from its nogood learning facility which allows the solver to fathom huge parts of the search space. In this talk, we introduce LCG in general and present our LCG method for minimising the project duration of RCPSPs and RCPSPs with minimal and maximal time lags.

Muhammed Alat: "Praktische Lösung von Minimum Cost Flow Problemen: Ein Vergleich verschiedener Algorithmen"

Um das Minimum Cost Flow Problem zu modellieren werden wir einige Beispiele betrachten. In den Beispielen werden unterschiedliche Problemstellungen aufgezeigt. Mit einigen interessanten Beobachtungen und Annahmen wird anschaulich illustriert, unter welchen Bedingungen das Minimum Cost Flow Problem optimal lösbar ist. Zum Lösen des Problems stellen wir zwei Algorithmen, den Netzwerk-Simplex-Algorithmus und Cost Scaling Algorithmus, vor. Dabei untersuchen wir, welche Techniken zum Einsatz kommen und welche Bedingungen zum Finden einer optimalen Lösung in Anspruch genommen werden. Schließlich werden mit vier bekannten Programmen 65 Probleme verschiedener Problemklassen gelöst. Die Ergebnisse mit Laufzeiten von weniger als einer Sekunde bis zu fast drei Tagen werden uns Aufschluss darüber geben, welches Programm für den praktischen Einsatz am besten geeignet ist und wo die Vor- und Nachteile der einzelnen Programme liegen.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe