Archiv

From PubADS

Jump to: navigation, search

Dies sind Themen für Praktika und Diplomarbeiten, die vergeben wurden bzw. aus anderen Gründen (derzeit) nicht zur Wahl stehen.

Contents

A Hybrid Metaheuristic for Bi-Level Transport Optimization
(funded with €1000,-)

Oct 3, 2013
Topic for
Master/Diploma thesis
Contact
Günther Raidl, Bin Hu

We are considering a bi-level transportation optimization problem in which a produced good is distributed from a set of factories (depots) via trucks to re-distribution centers and from there via vans to customer drop-off points. Time windows need to be respected for the pickup of goods and their delivery as well as capacities of vehicles

The goal is to develop a meaningful hybrid metaheuristic approach that finds a feasible solution minimizing operation costs. A starting point might e.g. be a variable neighborhood search considering suitable neighborhood structures which might later be extended by Large Neighborhood Search techniques. For improving the scalability of an approach to very large instances, multilevel refinement strategies might become useful.

This work is funded by Salzburg Research with €1000.


Searching for New Snarks

May 3, 2013
Topic for
Master Thesis
Contact
Bin Hu, Arthur Hoffmann-Ostenhof

Snarks are non 3-edge colorable 3-regular graphs with a certain additional connectivity property. The Petersen graph is the smallest snark. Many central open conjectures in graph theory (as for instance the Cycle Double Cover Conjecture and the Nowhere Zero 5-Flow Conjecture) can be reduced to the case of snarks. Note that the famous 4-Color Theorem is equivalent to the statement that there exists no planar snark.

So far, all snarks with less than 38 vertices are known since they have been generated by computer. The aim of this thesis is to develop efficient algorithms for generating larger snarks with certain graph theoretical properties. The first two tasks are as follows:

  • generate all snarks with 46 vertices which have certain spanning subgraphs.
  • check these obtained snarks for certain properties (e.g. length of the shortest cycle and connectivity properties).

The search for new snarks offers a lot of possibilities for computer work. Modifications and own ideas concerning this topic are welcome.

Bi- and Multi-objective Optimization in Network Design

March 5, 2012
Topic for
Master Thesis
Contact
Markus Leitner, Günther Raidl

When considering realistic scenarios occurring in the extension of networks one often faces conflicting goals such as

  • achieved coverage vs. total costs
  • achieved quality-of-service vs. total costs

One possibility to deal with conflicting objectives is the use of multi-objective optimization models. Based on the concept of Pareto-optimality such approaches deliver a whole set of potential solutions among which a decision maker can choose its preferred one.

Within a master thesis students may choose

  • a concrete network design problem among a list of potential problem variants provided by us and
  • develop metaheuristic approaches for a bi- and / or multi-objective variant of the chosen problem.

Table Creator

March 1, 2012
Topic for
Project
Contact
Johannes Inführ

The Table Creator is the result of a previous project. Its main feature is the creation of publishable latex tables from raw data. It also offers limited support for data analysis, like calculating mean, max or min values and marking lowest or highest values in a set of table cells. Graphs can also be created from the output of the Table Creator. However, there are some nuisances and limitations, especially with regards to the structure of the created tables. Your task when working on this project will be to remove those limitations and improve the Table Creator. It was written in C++, so you should be familiar with this language. It also utilizes components of the boost library, so some familiarity with this library would be an advantage.

Instance Generator for Variants of the Connected Facility Location Problem

March 5, 2012
Topic for
Project
Contact
Markus Leitner

The Connected Facility Location Problem is a network design problem suitable to model certain scenarios in the extension of real-world networks. The goal of this project is to develop an instance generator that allows to

  • generate challenging benchmark instances

for variants of this problem based on

  • existing (real-world) data for similar problems.


Graph Partitioning Under Uncertainty

September 27, 2011
Topic for
Project, Bachelor or Master Thesis
Contact
Markus Leitner (and Ivana Ljubic)

Variant of the graph partitioning problem are well studied combinatorial optimization problems. Less approaches have been proposed, however, for more realistic settings when input data is only partly known in advance, i.e. is subject to uncertainty. One possibility to address uncertainty is robust optimization.

Within projects, bachelor or master theses, students may develop

  • meta-heuristic approaches
  • MIP formulations and corresponding solution approaches

for robust variants of graph partitioning problems.

Mirror Server Location Problem

August 9, 2011
Topic for
Project, Bachelor or Master Thesis
Contact
Günther Raidl

Given a communication network, the aim is to identify suitable positions for locating mirror servers in order to alleviate the loads on servers and links.

More formally, we consider the following strongly simplified model, called Server Location Problem with Restricted Loads on Servers and Links: Given a graph G = (V,E) representing the communication network, find a subset S=\{s1,\ldots,s_k\}\subset V of k nodes for locating mirror servers such that

  • each s_i\in S has a neighbor set Vi of no more than r nodes, with r being a given constant; the neighbor set of a server si is the set of all nodes V\setminus S to which si is the closest server w.r.t. the number of hops (links);
  • and the load m(e) on each link e\in E does not exceed a given limit c; a link's load is the total number of shortest paths between servers and the nodes in their respective neighbor sets.

This problem formulation is rather new and consequently, not much work exists yet. In one or more student projects, bachelor, and/or master theses, it is possible to develop and study diverse either heuristic or exact problem solving methods. Promising techniques include constructive heuristics, local search, metaheuristics, constraint programming, and mathematical programming techniques.

Network Design Under Uncertainty

Umfang
Praktikum oder Diplomarbeit
Auskunft
Ivana Ljubic

Deterministic network design problems like Steiner trees, survivable network design, degree-, hop- or cardinality-constrained tree problems are some of the well studied combinatorial optimization problems. In these classical settings we assume that the input parameters (e.g., communication patterns, customer demands and/or installation costs) are known and fixed values. However, in many relevant applications, e.g. in the design of telecommunication networks, those parameters are hard to predict and they may even change over time. Therefore, network planners are often faced with uncertainty with respect to the input data. The actual demand patterns become known only after the network has been built. In that case, networks found by solving an instance in which it is assumed that the complete knowledge of the input is known upfront, might not provide appropriate solutions if deviations from the assumed scenario are encountered.

Stochastic and robust optimization are two promising ways to take uncertainties into account.

Within the framework of this project/master thesis, students may choose to develop some of the following approaches to solve network design problems under uncertainty:

  • development of specific MIP formulations and their polyhedral comparison,
  • branch-and-cut algorithms,
  • Lagrangian relaxation approaches,
  • meta-heuristic approaches, or
  • matheuristics

We will consider:

  • single and two-stage robust optimization
  • two-stage stochastic optimization

HAIS: Hierarchical Abstraction and Intelligent Subproblem Composition

Umfang
Praktikum oder Diplomarbeit
Auskunft
Günther Raidl

Trotz der vielen existierenden Optimierungsverfahren ist die Auswahl äußerst beschränkt, wenn es um das Lösen sehr großer Probleminstanzen geht. Meist werden deshalb in der Praxis einfachste Konstruktionsheuristiken oder lokale Verbesserungsmethoden angewandt bzw. alternativ die sehr großen Instanzen manuell oder mit einfachen Strategien in kleinere Probleme zerteilt, die dann gut gelöst werden können. Leider liefern diese Ansätze i.A. keine zufriedenstellenden Resultate.

Im Zuge dieser Arbeit soll ein Framework (bzw. Teile davon) entwickelt werden, welches wir Hierarchical Abstraction and Intelligent Subproblem Composition (HAIS) nennen. Dieses soll im Speziellen besonders gut mit der Größe eines Problems skalieren und bestehende führende Heuristiken oder exakte Algorithmen für kleinere Instanzen des betreffenden oder eines verwandten Problems effizient nutzen um eine Ausgangslösung iterativ zu verbessern.

Dazu konstruiert HAIS zunächst eine hierarchische Problem-Repräsentation (HPR), siehe Bild rechts, welche im Wesentlichen ein Baum ist, der das Ausgangsproblem auf unterschiedlichen Abstraktionsebenen darstellt. Im Gegensatz zu bisherigen Methoden konstruiert HAIS nun iterativ kleinere Unterprobleme in einer flexiblen Weise bei der verschiedene Teile des Problems auf unterschiedlichen Abstraktionsniveaus betrachtet werden. Dieser Konstruktionsmechanismus basiert weniger auf einfachen Zufallsentscheidungen wie im Fall der klassischen Very Large Neighborhood Search Methoden, sondern nutzt verschiedenste Arten von Informationen und Strategien zur intelligenten Auswahl jener Teile, die auf einem niedrigen Abstraktionsgrad betrachtet werden und am vielversprechendsten sind um insgesamt Verbesserungen zu erzielen. Die so erzeugten Unterprobleme werden dann mit den für kleinere Instanzen am besten geeigneten heuristischen, exakten oder hybriden Algorithmen gelöst. Verschiedenste neue Strategien sollen für die Verbreitung von Lösungsinformationen innerhalb der HPR sowie für die kontinuierliche Anpassung dieser zentralen Struktur untersucht werden.

Aufgrund bestehenden Codes sollte C++ verwendet werden.

Multilevel Ansätze im Netzwerkdesign

Umfang
Praktikum oder Diplomarbeit
Auskunft
Günther Raidl

Reale Instanzen im Bereich des Netzwerkdesigns sind häufig sehr groß. Die entsprechenden Optimierungsprobleme können auf den resultierenden Graphen dann nur mit sehr einfachen Methoden gelöst werden. Aus diesem Grund werden häufig Clustering – Verfahren eingesetzt und die resultierenden einzelnen Teile unabhängig voneinander gelöst. In dieser Arbeit sollen Instanzen mittels sukzessivem Clustering bzw. durch sukzessiver Vereinfachung einer Instanz (etwa durch Entfernen von Knoten / Kanten) auf mehreren Ebenen betrachtet und gelöst werden. Durch Transformationen von Lösungen zwischen diesen Ebenen sollen bessere Lösungen erzielt werden. Zusätzlich soll untersucht werden, inwieweit diese Lösungen dazu benutzt werden können das bestehende Clustering und damit die resultierende Lösung weiter zu verbessern.

Hop Constrained Survivable Network Design Problem

Umfang
Diplomarbeit oder Praktikum
Auskunft
Markus Leitner

Das Hop Constrained Survivable Network Design Problem tritt beim Design von ausfallsicheren Netzwerken auf. Gegeben ist ein Graph mit nicht-negativen Kantenkosten, sowie Redundanzanforderungen zwischen Knotenpaaren (= Anzahl der geforderten paarweise disjunkten Verbindungen zwischen den jeweiligen Knoten). Die Aufgabe, besteht nun darin, den kostengünstigsten Teilgraphen zu identifizieren, sodass alle Redundanzanforderungen erfüllt sind. Weiters muss eine obere Schranke bezüglich der maximalen Anzahl an Kanten einer Verbindung zwischen zwei Knoten berücksichtigt werden (Hoplimit).

Themen:

  • MIP Formulierungen und entsprechende Lösungsverfahren (Branch&Cut, Branch&Price)
  • Lagrange Relaxierung
  • Metaheuristiken
  • Konstruktionsheuristiken


Quota Constrained Steiner Tree Problem

Umfang
Diplomarbeit (ev. auch Praktikum)
Auskunft
Markus Leitner

Das Quota Constrained Steiner Tree Problem tritt beim Design bzw. Ausbau von Netzwerken auf. Gegeben ist ein Graph mit positiven Kantenkosten (Ausbaukosten) und eine Menge von Kundenknoten mit Erlösen, die beim Anschluss des jeweiligen Kundenknoten erzielt werden. Beim klassischen Prize Collecting Steiner Tree Problems (PCSTP) soll nun jene Teilmenge an Kunden identifiziert und an das Netzwerk angeschlossen werden, welche den resultierenden Profit maximiert. Im Gegensatz dazu, ist in der Quota Constrained Variante zusätzlich eine untere Schranke für die Summe der zu erzielenden Erlöse gegeben. Ziel ist es das kostengünstigste Netzwerk zu finden, sodass die Summe der Erlöse mindestens dem geforderten Wert entspricht.

Themen:

  • MIP Formulierungen und entsprechende Lösungsverfahren (Branch&Cut&Price)
  • Metaheuristiken



Computing Safe Cycling Tours

June 25, 2013
Topic for
Project, Bachelor or Master Thesis
Contact
Günther Raidl, Matthias Prandtstetter
Special feature
This work will be co-supervised by members of the AIT Austrian Institute of Technology; a "Werkvertrag" at the AIT can be offered.

We want to compute safe cycling tours for persons with special (mobility) needs (e.g. rehabilitation patients, people with multiple sclerosis, elderly, etc.). Although parallels to the well-known traveling salesperson problem can be identified, we are neither given a set of locations to be visited nor a (classical) objective function to be optimized. Therefore, novel methods need to be developed, which can provide the user (cyclist) round trips satisfying additional constraint like

  • the tour should be a round trip as much as possible (the number of street segments to be traversed more than once should be minimized),
  • the length of the tour should be no longer and no shorter than given values, and
  • it should be possible to return at each time while cycling along the tour to the departure location within a given time limit (e.g. 10 minutes) - obviously not necessarily along the pre-computed round trip.

Goal of this project is to implement novel algorithms for providing us with safe cycling tours. Implementation should be realized in Java using a framework providing functionality for reading maps and processing location based data. Own ideas and inputs are warmly welcomed.

Stamina-Aware Sightseeing Tour Problem

October 10, 2012
Topic for
Project, Bachelor or Master Thesis
Contact
Bin Hu

The Stamina-Aware Sightseeing Tour Problem is a variation of the well-known Traveling Salesman Problem (TSP). Given a tourist and a set of sightseeing spots, we seek a tailored sightseeing tour with sightseeing methods for each spot that satisfies the tourist most. The tourist's preferences, stamina, and available time are considered.

Within projects, bachelor or master theses, students may develop

  • MIP formulations and corresponding solution approaches
  • meta-heuristic approaches
  • visualizations with human interaction
  • Hybrid metaheuristic with MIP formulation

Partition Graph Coloring Problem

February 18, 2013
Topic for
Master Thesis
Contact
Bin Hu

Given a graph G = (V, E) where V is partitioned into disjoint clusters, the problem consists of finding a subset V' that contains one node in every cluster and the induced subgraph G' has the minimal chromatic number.

Content:

  • Metaheuristic approach with different solution representations

Integer Linear Programming Ansätze für das Generalisierte Vertex Biconnected Network Problem

Umfang
Diplomarbeit oder Praktikum
Auskunft
Bin Hu

Für das generalisierte Vertex Biconnected Network Problem ist ein Graph gegeben, dessen Knoten in Clustern partitioniert sind. Das Ziel besteht darin, einen möglichst kostengünstigen Subgraphen zu finden, der genau einen Knoten aus jedem Cluster enthält und kanten-zweizusammenhängend ist.

Ausgehend von einer bestehenden Multicommodity Flow ILP Formulierung besteht die Arbeit darin, neue Modelle zu entwickeln und zu testen, bzw. Verfahren wie Lagrangean Relaxation/Decomposition anzuwenden.

Rekonstruktion von zerstörten Dokumenten

Umfang
Praktikum oder Diplomarabeit
Auskunft
Christian Schauer

In Folge einer Arbeit soll eine Datenstruktur entwickelt werden, die die Verwaltung von händisch zerrissenen Dokumente erlaubt. Während maschinell geschredderte Dokumente in ein rechtwinkeliges Raster passen, können händisch zerrissene Schnipsel in kein systematisches Raster eingefügt werden und müssen daher auf komplexere Art verwaltet werden. Ziel des Praktikums wäre eine entsprechende Datenstruktur zu entwickeln und implementieren.

Wir arbeiten in diesem Forschungsgebiet eng mit dem Computer Vision Lab zusammen, daher ist auch eine fachübergreifene Arbeit möglich.

Weitere Themen sind nach Absprache möglich!

AI Challenge

March 1, 2012
Topic for
Project
Contact
Johannes Inführ

The general theme of the AI Challenges is to program artificial intelligence which is capable of playing a game. When working on this project, the task will be to apply a metaheuristic (e.g. Genetic Programming) to create valid game playing strategies (in contrast to programming an AI by hand). The actual game to play depends on the current iteration of the AI challenge. Previous topics were PlanetWars (building up a space empire) and Ants (controlling an ant colony). In times when no contest is being run, you can work on Robocode instead.

The p-Cable-Trench Problem

September 27, 2011
Topic for
Project, Bachelor or Master Thesis
Contact
Markus Leitner

The recently proposed p-cable-trench problem is an NP-hard combinatorial optimization problem in the context of network design. In this problem, p facilities shall be determined which then supply all other customer nodes. In the p-cable-trench problem edge costs (digging costs) as well as cable costs for connecting customer nodes are considered. The goal is to identify a solution yielding minimum total costs.

Within projects, bachelor or master theses, students may develop

  • meta-heuristic approaches
  • MIP formulations and corresponding solution approaches

for this problem.

Regenerator Location Problem

August 9, 2011
Topic for
Project, Bachelor or Master Thesis
Contact
Günther Raidl

In optical telecommunication networks, fiber optic links are nowadays state-of-the-art. Such links have certain limits with respect to the maximum distance before the signal quality deteriorates too much. For longer connections, regenerators must be introduced for refreshing the signals. As these regenerators are expensive, one wants to deploy as few regenerators as possible in a given network.

More formally, the goal in the Regenerator Location Problem (RLP) is to find within a given graph representing a communication network a minimum cardinality subset of nodes such that for every pair of nodes there exists a path with the property that it has no subpath longer than a limit dmax without an intermediate regenerator.

Existing work primarily includes exact mathematical programming techniques, a few construction heuristics and a GRASP. In a student project, bachelor, or master thesis, further metaheuristic approaches, primarily based on extensions of local search, shall be investigated.

Erstellung eines universellen Längsdynamik-Simulationsmodells für Hybridfahrzeuge

September 12, 2011
Umfang
Diplomarbeit
Auskunft
Günther Raidl, gemeinsame Betreuung mit dem Institut für Elektrische Antriebe und Maschinen und dem Institut für Fahrzeugantriebe und Automobiltechnik

Hybridfahrzeuge können durch die Aufteilung der Antriebsleistung zwischen Verbrennungskraftmotor und Elektromotor mit höherem Gesamtwirkungsgrad betrieben werden als konventionelle Fahrzeuge. Diese Vorteile können jedoch nur bei richtiger Auslegung der einzelnen Komponenten (Verbrennungskraftmotor, Elektromotor, Batterie, Getriebe,... ) genutzt werden.

Mithilfe einer Längsdynamiksimulation soll der Einfluss dieser Komponenten auf Reichweite, Verbrauch, Beschleunigung, etc. untersucht werden.

Es ist ein universelles Längsdynamik Simulationsmodell für Hybrid-antriebsstränge in Matlab / Simulink oder LabView zu programmieren, mit dem die Energieflüsse im Fahrzeug berechnet werden können. Das fertige Modell wird in der Lehre eingesetzt und soll dem Anwender die Erarbeitung eines Grundverständnisses für die Hybridtechnologie ermöglichen. Neben einer bedienerfreundlichen Oberfläche soll das Werkzeug folgende Features aufweisen:

  • Einfache Erstellung verschiedener Hybridantriebsstränge (parallel, seriell,..)
  • Einfache Austauschbarkeit und Parametrierung der Komponentenmodelle
  • Berechnung verschiedener Fahrzyklen

Voraussetzungen:

  • Grundkenntnisse/Interesse im Bereich Hybridfahrzeuge
  • Kenntnisse mit Simulationsprogrammen

Metaheuristiken für das Quadratische Rucksackproblem

October 3, 2011
Topic for
Project, Bachelor or Master Thesis
Contact
Ulrich Pferschy (Uni Graz), Günther Raidl

Beim klassischen Rucksackproblem wird eine Menge von items betrachtet, von denen jedes einen Profit und ein Gewicht besitzt. Als Lösung ist eine Teilmenge von items auszuwählen, sodass ihr Gesamtprofit maximal wird und ihr Gesamtgewicht eine gegebene Kapazitätsschranke nicht überschreitet.

Im quadratischen Rucksackproblem (QKP) stehen die items zuätzlich in einer Wechselwirkung zueinander, sodass jedes Paar (i,j) von items neben den beiden Profiten p_i und p_j auch einen Synergiewert q_ij generiert, der ebenfalls zum Gesamtprofit beiträgt. Natürlich entsteht dieser Synergiewert nur, wenn beide items in der Lösung ausgewählt werden.

Für dieses schwierige kombinatorische Optimierungsproblem gibt es eine Reihe von exakten Lösungsalgorithmen, die aber schon bei Problemen mittlerer Größe sehr lange Laufzeiten benötigen. Erstaunlicherweise sind aber noch kaum ausgereifte (Meta)-Heuristiken für dieses Problem bekannt.

In Zusammenhang mit einem Industrieprojekt, bei dem eine optimale Mischung von Werbemitteln für eine Marketingkampagne bestimmt werden soll, werden nun Metaheuristiken gesucht, die rasch Lösungen mit geringer Abweichung vom Optimum finden. Mögliche Ansätze sind Genetische Algorithmen, Tabu-Search, Variable Neighbourhood Search.

Die Betreuung erfolgt in Zusammenarbeit mit Prof. Ulrich Pferschy von der Universität Graz.

Optimierung von Kraftfahrzeugen

Umfang
Praktikum und/oder Diplomarbeit
Auskunft
Günther Raidl, Thorsten Krenek

Für ein Hybridfahrzeug, das durch numerische Verfahren vollständig simuliert wird, soll eine optimale Betriebsstrategie gefunden werden, sodass dieses möglichst effizient in einem definierten Fahrzyklus betrieben werden kann. Dazu wurde bereits eine Diplomarbeit verfasst und eine Optimierungssoftware in C++ mit grafischer Benutzeroberfläche entwickelt (http://www.ub.tuwien.ac.at/dipl/2011/AC07811094.pdf, Kapitel 4.3, S.36ff). Im Rahmen eines Praktikums soll diese Software für den Einsatz weiterer Optimierungsaufgaben im KFZ Bereich erweitert, in die bestehende Infrastruktur (Linux-Cluster) eingegliedert und Multiuser-fähig gemacht werden. Alternativ können im Zuge einer Diplomarbeit die bereits vorhandenen Optimierungsalgorithmen verbessert und neue Methoden entwickelt werden. Diese Arbeiten werden in Zusammenarbeit mit dem Institut für Fahrzeugantriebe und Automobiltechnik an der TU-Wien durchgeführt.

Themen (u.a):

  • Optimierung von kontinuierlichen Parametern
  • Particle-Swarm-Optimization
  • Genetische Algorithmen
  • Neuronale Netze

Three-Dimensional Loading Capacitated Vehicle Routing Problem (3L-CVRP)

Umfang
Praktikum oder Diplomarbeit
Auskunft
Sandro Pirkwieser

Das Three-Dimensional Loading Capacitated Vehicle Routing Problem (3L-CVRP) ist eine sehr praxisrelevante Kombination zweier in der Vergangenheit meist getrennt voneinander betrachteter Probleme. Wie bei anderen ähnlich gelagerten Problemen ist jedoch der integrative Ansatz vorzuziehen. Ziel beim 3L-CVRP ist es kostengünstige Touren für die Auslieferung von Waren (in Form rechteckiger Boxen) zu finden, welche die Beschränkungen hinsichtlich der dreidimensionalen Beladung der Frachträume einhalten. Folgende Bedingungen sind dabei zu berücksichtigen: Gewichts- und Volumenbeschränkung, Berücksichtigen von eventuellen fragilen Waren, der (un-)erlaubten Rotation der Waren, und jene betreffend des Stapelns der Waren, d.h. die Waren des nächsten Kunden sollen jeweils ohne Umschichten entnommen werden können (rear loading bzw. sequential loading) und die Waren müssen stabil gestapelt werden. Als Erweiterung wäre eine Berücksichtigung der Achslasten denkbar.

In der Literatur sind bisher nur sehr wenige metaheuristische Ansätze zu finden, was aufgrund der Komplexität (vor allem) der Beladung nicht verwunderlich ist. Mögliche Themen wären daher zum Beispiel eine entsprechende Variable Nachbarschaftssuche zu implementieren und/oder sich mit einem neuen Packverfahren zu beschäftigen.

Truck and Trailer Routing Problem (TTRP)

Umfang
Praktikum oder Diplomarbeit
Auskunft
Sandro Pirkwieser

Das Truck and Trailer Routing Problem (TTRP) ist eine bisher eher wenig untersuchte Variante eines speziellen Tourenplanungsproblems. Dabei liegt die Schwierigkeit darin, dass prinzipiell eine Flotte an Fahrzeugen mit Anhänger (bzw. Auflieger) zur Verfügung steht um allen Kundenwünschen mit entsprechender Effizienz gerecht werden zu können. Einige dieser Kunden können jedoch nur von dem Truck alleine besucht werden, welches sowohl für dicht besiedelte Gebiete wie in Innenstädten als auch für ländliche und unwegsame Gebiete gilt. Ziel ist es daher eine global gesehen kostengünstige Auslieferung zu realisieren bei der die Kunden entweder nur vom Truck, vom Truck plus Trailer oder einer Mischung aus beiden (d.h. mit zwischenzeitlichem Abstellen des Trailers) besucht werden.

Mögliche sinnvolle Themen für eine Diplomarbeit sind eine hybride Metaheuristik bei der Teile des Problems exakt gelöst werden, als auch ein exaktes Verfahren an sich. Als Praktikum würde sich das Nachimplementieren eines bestehenden Verfahrens oder auch die Untersuchung von Konstruktionsheuristiken anbieten.

Two-Echelon Location Routing Problem (2E-LRP)

Umfang
Praktikum oder Diplomarbeit
Auskunft
Sandro Pirkwieser

Das Two-Echelon Location Routing Problem (2E-LRP) kombiniert die strategische Planung von Standorten (in weiterer Folge als Depots bezeichnet) und die operative Planung von zweierlei Fahrzeugtouren. Gegeben ist ein zentrales Depot (in der Grafik rot markiert), potenzielle weitere (kleinere) Depots und eine Menge von zu beliefernden Kunden (z.B. Filialen, grün markiert). Teil des Problems ist die Auswahl von zu eröffnenden Depots (blau markiert, restliche potenzielle Depots sind grau) sowie die Planung von Touren vom Zentraldepot zu den offenen Depots und von letzteren schließlich zu den Kunden. Für die Auslieferung werden zwei unterschiedliche Typen von Fahrzeugen angenommen, die jedoch als fixiert zu betrachten sind. In der Literatur sind bisher relativ wenig Arbeiten darüber zu finden.

Ein mögliches Praktikumsthema ist die Erweiterung eines bestehenden hybriden Verfahrens für das LRP (d.h. ohne dem Zentraldepot und den ausgehenden Touren) auf das 2E-LRP. Als Diplomarbeitsthema wird ein exaktes Verfahren basierend auf Spaltengenerierung angeboten.

Pre-marshalling Problem

Umfang
Praktikum oder Diplomarbeit
Auskunft
Sandro Pirkwieser, Markus Leitner

Das Pre-marshalling Problem tritt in der maritimen Logistik auf, konkret in einem Hafenterminal in dem Container umgeschlagen werden. Letztere erreichen über die Straße oder Schiene den Hafen und werden dort auf zugeteilten Flächen, denen jeweils ein normalerweise fix montierter Lastenkran zugeordnet ist, in Form von Stapeln zwischengelagert um später auf ein Schiff geladen zu werden. Das Problem ist, dass die eintreffenden Container nicht jener Reihenfolge entsprechen in der sie den Hafen verlassen sollen bzw. dies auch oft beim Eintreffen noch nicht klar ist. Um die Beladungszeit des später eintreffenden Schiffes möglichst kurz zu halten und dadurch den Warenumschlag zu maximieren werden die gestapelten Container so umgeordnet, dass die oben liegenden vor den unteren Containern beladen werden und keine weiteren Verschiebungen nötig sind. Diese Umordnung soll in möglichst wenig Schritten realisiert werden.

Mögliche Themen sind die Entwicklung von Metaheuristiken (z.B. interessant: Nachbarschaften, Repräsentation) als auch eines entsprechenden exakten Verfahrens basierend auf mathematischer Programmierung.

Optimierung informeller Kommunikation in Bürogebäuden

Umfang
Diplomarbeit
Auskunft Günther Raidl

Die geometrische Form der gebauten Umwelt hat einen wesentlichen Einfluß auf das menschliche Verhalten. Im urbanen Maßstab wurden erfolgreich Modelle entwickelt, die die Planung von Städten, Stadtteilen, Gebäuden,... als Analysewerkzeug unterstützen. Der Stadtraum wird dabei durch einen Graphen abstrahiert. Die unterschiedlichen Eigenschaften des Graphen wie z.B.: die Zentralität geben Auskunft über Bewegungsmuster in einer Stadt. Für Unternehmen (z.B.: Google) wird der Wissensaustausch zwischen Mitarbeitern abseits täglicher Büroabläufe immer wichtiger. Diese informelle Kommunikation ist planbar. In Bürobauten ist dies ungleich komplexer. Sie werden von vergleichsweise wenigen Menschen, mit einer genauen Kenntnis des Bürogebäudes und bestimmten Tagesabläufen genutzt. Jedoch gibt es auch bei Bürobauten die Möglichkeit, das Potential abzubilden, von Menschen genutzt zu werden:

  • Wie oft ist ein Bereich Teil des Weges zwischen zwei Punkten (Arbeitsplätze, Anziehungspunkten);
  • Wie sichtbar ist ein Bereich von anderen Bereichen aus (Anordnung von Barrieren wie z.B. Wände,...);
  • Wie weit entfernt befindet sich ein Bereich zu den Arbeitsplätzen, Anziehungspunkten.

Mit diesen Informationen ist es möglich, Abläufe in Bürogebäuden zu visualisieren und zu verstehen. Es kann gezeigt werden, dass ein Büro mit den kürzesten Wegen zwischen Mitarbeitern einer Organisationseinheit nicht das optimale Büro im Hinblick auf informelle Kommunikation ist.

Das Simulationsmodell soll erweitert werden, so dass es nicht nur die Analyse bestehender Situationen als Planungshilfe erlaubt, sondern durch die Platzierung von Arbeitsplätzen und Anziehungspunkten bzw. durch die Veränderung der Barrieren mehrere "optimale" möglichst unterschiedliche Lösungen vorschlägt. Eine „optimale“ Lösung ist abhängig von mehreren Kriterien:

  • Verteilung des Nutzungspotentials
Möglichst großes Nutzungspotential an einem beliebigen Punkt;
Möglichst gleichmäßig verteiltes Nutzungspotential;
Möglichst großes Nutzungspotential in einem oder mehreren Bereichen;
  • Platzierung von Arbeitsplätzen
Nahe an bzw. weit von Bereichen mit großem Nutzungspotential
Viel bzw. wenig Übersicht über den Raum und andere Arbeitsplätze bzw. Anziehungspunkte
Nahe bzw. weit entfernt von anderen Arbeitsplätzen der zugehörigen Organisationseinheit
  • Platzierung von Anziehungspunkten
Nahe an bzw. weit von Bereichen mit großem Nutzungspotential
Viel bzw. wenig Übersicht über den Raum und andere Arbeitsplätze bzw. Anziehungspunkte
  • Platzierung von Nebenräumen
  • Anordnung und Höhen von Barrieren

Die Analyse ist momentan als C++ Plug In für die Software UCL Depthmap realisiert. Als Alternative dazu würde sich die in Java geschriebene Open Source Software „Syntax2D“ anbieten.

Die Betreuung erfolgt in Zusammenarbeit mit Kollegen Schaffranek von der Fakultät für Architektur und Raumplanung.

Optimierung der Produktionsplanung unter volatilen Bedingungen

Umfang
bezahlte Diplomarbeit (oder Berufspraktikum) in Zusammenarbeit mit der Firma nemak, Dauer ca. 6 Monate
Auskunft und Betreuung seitens der TU
Günther Raidl

Am Standort Linz des internationalen Nemak-Konzerns (Weltmarktführer für Aluminiumguss von Zylinderköpfen und Motorblöcken; www.nemak.com) wurde das vollautomatische Informationssystem NORIS (NemakOperationsRealtimeInformationSystem) entwickelt und bereits auf mehrere Standorte ausgebreitet. Die Funktionalität von NORIS beinhaltet derzeit die vollautomatische Echtzeitübertragung von Maschinendaten (Stück produziert, Störungen, Produktionsparameter,…), sowie die manuelle, dezentrale Datenerfassung von Ausschussteilen via Touchscreens. Die Applikation ist in C# programmiert, die Datenhaltung ist in MS-SQL 2008, als Auswertewerkzeug ist MS Reporting Service 2008 im Einsatz. Die Funktionalität von NORIS wird nun um die Möglichkeit erweitert, die optimale Produktionsplanung für sehr volatile (stark schwankende, instabile Prozesszeiten) Produktionsprozesse durchzuführen.

Aufgabenstellung

  • Erhebung des Standes der Technik der Produktionsplanung von volatilen Produktionsprozessen
  • Entwicklung der Planungsstrategie, des Planungsablaufes und des User-Interfaces in enger Zusammenarbeit mit dem Werkzeugbau
  • Entwicklung der automatischen Planungslösung für den ausgewählten Bereich des Werkzeugbaus basierend auf Metaheuristiken (Genetische Algorithmen, Simulated Annealing,..) oder mittels einer Kombination von Dispatch-Regeln

Gewünschte Qualifikationen: C#, SQL, Grundkenntnisse Metaheuristiken, MS Reporting Service

Neben Bezahlung bei Bedarf Dienstwohnung am Firmengelände in Linz, teilweises Teleworking möglich

Optimierung in der Produktionsplanung von Zylinderköpfen und Motorblöcken

Umfang
bezahlte Diplomarbeit (oder Berufspraktikum) in Zusammenarbeit mit der Firma nemak, Dauer ca. 6 Monate
Auskunft und Betreuung seitens der TU
Günther Raidl

Am Standort Linz des internationalen Nemak-Konzerns (Weltmarktführer für Aluminiumguss von Zylinderköpfen und Motorblöcken; www.nemak.com) wurde das vollautomatische Informationssystem NORIS (NemakOperationsRealtimeInformationSystem) entwickelt und bereits auf mehrere Standorte ausgebreitet. Die Funktionalität von NORIS beinhaltet derzeit die vollautomatische Echtzeitübertragung von Maschinendaten (Stück produziert, Störungen, Produktionsparameter,…), sowie die manuelle, dezentrale Datenerfassung von Ausschussteilen via Touchscreens. Die Applikation ist in C# programmiert, die Datenhaltung ist in MS-SQL 2008, als Auswertewerkzeug ist MS Reporting Service 2008 im Einsatz. Die Funktionalität von NORIS wird nun um die Möglichkeit erweitert, bereits abgearbeitete Aufträge an Maschinen via Gantt-Chart darzustellen sowie im zweiten Schritt auf heuristischen Algorithmen basierende optimale Planung vorzuschlagen. Im Rahmen dieser Diplomarbeit steht die Entwicklung der automatischen Planungslösung für den ausgewählten Bereich der Wärmebehandlung basierend auf Metaheuristiken (Genetische Algorithmen, Simulated Annealing, etc.) im Vordergrund.

Neben Bezahlung bei Bedarf Dienstwohnung am Firmengelände in Linz, teilweises Teleworking möglich, Mitarbeit in einem kleinen, motivierten Team bei einem Weltmarktführer, keine „Papier-Arbeit“ für die Ablage sondern direkte Umsetzung im Konzern.

Vehicle Routing Problem with Compartments (VRPC)

Umfang
Praktikum oder Diplomarbeit
Auskunft
Sandro Pirkwieser, Günther Raidl

Das VRPC ist eine Generalisierung des klassischen Tourenplanungsproblems dahingehend, dass die betrachteten Fahrzeuge der gegebenen Flotte mehrere Ladeabteile (Compartments) haben, in denen die zu liefernden Waren untergebracht werden sollen. Dabei ist es oft weder erlaubt alle Waren in allen Ladeabteilen zu transportieren noch bestimmte Waren gemeinsam in ein Abteil zu geben. Ebenfalls sind die Kapazitäten der einzelnen Abteile sowie des Fahrzeuges an sich zu berücksichtigen. Dadurch ist das Problem i.A. zwar schwieriger zu lösen, befasst sich aber mit einem praktisch sehr relevanten Aspekt.

Für folgende Waren müssen zum Beispiel solche Bedingungen berücksichtigt werden:

  • Milch (von Kuh, Schaf, Ziege)
  • Erdölprodukte (Benzin, Diesel)
  • Lebensmittel (trocken, gekühlt, gefroren)
  • chemische Produkte

Diese spezielle Problemstellung wurde bisher recht selten und auch erst kürzlich in der Literatur behandelt. Es ist daher durchaus mit einem Optimierungspotenzial hinsichtlich der Methodiken zu rechnen. Letztere können sowohl im metaheuristischen als auch exaktem Bereich liegen. Eventuell bietet sich auch eine geeignete Kombination zu leistungsfähigen Hybridverfahren an.

Genetic Programming mit D

Umfang
Praktikum
Auskunft
Johannes Inführ

Die Programmiersprache D ist eine Systemprogrammiersprache und vereinigt Eigenschaften von C++, Java und funktionalen Programmiersprachen. Von C++ kommen beispielsweise die Systemprogrammierfähigkeiten (zB Inline-Assembler) und Template-Metaprogrammierung, von Java Garbage Collection und for-Schleifen über Collections und von funktionalen Sprachen Lamda-Ausdrücke und Closures. D bietet auch Features die in diesen Quellsprachen nicht zu finden sind, wie zum Beispiel Contract Programming, Unit-Testing (als Sprachfeature) und Funktionsevaluierung während der Kompilierung.

Ziel der Arbeit sind Implementierung und Test verschiedener Genetic Programming Ansätze in D sowie eine Evaluierung, ob und wie spezielle Eigenschaften von D dabei nützlich sind. Ein einfaches Beispiel für ein nützliches Sprachelement ist die final switch Anweisung, die wie eine normale switch-Anweisung funktioniert, aber eine Enumeration als Argument verwendet. Der D-Compiler warnt wenn nicht jedes Element der Enumeration im switch-Block behandelt wird, was im Hinblick auf Genetic Programming nützlich ist, wenn man eine Enumeration mit den möglichen arithmetischen Operationen verwendet. So hat man die Garantie, dass man bei Änderungen der möglichen Operationen deren Implementierung nicht vergisst. Ein etwas komplexeres Beispiel ist der typsichere Ellipsis-Operator, der Funktionen mit einer beliebigen Anzahl (und beliebigen Typen) von Argumenten ermöglicht. Damit lässt sich eine Stack-Maschine implementieren, die besonders einfach zu testen ist, z.B. stack_machine(1,1,'+') sollte 2 ergeben, stack_machine(2,2,1,'*','+') 4. Es ist kein Umweg über eine spezielle Programmrepäsentation erforderlich. Wenn man auch Funktionen als Argumente zulässt erhält man eine Stack-Maschine deren Befehlssatz je nach Anwendung verändert werden kann, z.B. stack_machine(2,3,(x,y){return x^^y;}) ergibt 8.


Genetic Algorithms for Model Selection in QTL Analysis (Bioinformatik)

Umfang
Praktikum oder Diplomarbeit
Auskunft
Ivana Ljubic (University of Vienna), Florian Frommlet (University of Vienna)

Many quantitative traits in plants, animals, and humans are to a certain extent determined genetically. Regions of the genome that influence such traits are called quantitative trait loci (QTL), and typically molecular markers are employed to detect and locate QTL using statistical models. A simple but successful approach is to apply multiple regression or ANOVA models including interactions. The most difficult part in fitting such models lies in the identification of the nonzero coefficients. This problem of model selection could be addressed by employing any information criterion. In cooperation with Prof. Bogdan from TU Wroclaw the performance of a modified BIC criterion has been analysed extensively. Theoretical considerations, as well as simulation studies, have shown that mBIC performs excellently as a model selection criterion when detecting QTL. However, for large n it is completely impossible to compute mBIC for all 2n - 1 possible models, and some search strategy within the space of all models is needed to find the (sub)optimal one. So far only fairly simple search strategies like forward selection or stepwise selection have been implemented. These strategies result in one set of QTL which is not necessarily the optimal solution. Genetic algorithms will be used to develop a much more sophisticated search strategy, which is not only likely to find ‘the best’ model, but which also gives an idea of the distribution of a whole set of potentially interesting models.

Connected Facility Location with Piecewise Linear Costs

Umfang
Praktikum oder Diplomarbeit
Auskunft
Ivana Ljubic (University of Vienna)

In order to provide high-quality broadband connections to its end-customers, a telecommunication company is interested in replacing parts of the existing copper-network with high-capacity fiber optic connections. Edge and node-installation costs obey economies of scale in the sense that the cost per unit of capacity installed decreases with the maximum capacity provided by equipment. To capture this aspect, we use discrete, step increasing, non-convex cost functions on nodes and edges.

This practical problem represents a generalization of some well-studied NP-hard network design problems: (connected) facility location, (generalized) Steiner tree and minimum cost multi-commodity flow. Within the framework of this project/master thesis, students may choose to develop specific ILP formulations for the problem, or (for more advanced work) to consider hybridizations of the ILP approach with local-search based meta-heuristics.

ROADEF/EURO Challenge 2010: A large-scale energy management problem with varied constraints

Umfang
Praktikum
Auskunft
Sandro Pirkwieser

Dieser Wettbewerb wird gemeinsam von der French Operational Research and Decision Support Society (ROADEF) und der European Operational Research Society (EURO) organisiert. Die Aufgabenstellung besteht darin eine gegebene Menge an (Wärme-)Kraftwerken möglichst kostenminimal zu betreiben. Dazu gehört sowohl die Planung der produzierten Menge an Strom pro Zeiteinheit und Kraftwerk, welche den Kundenbendarf decken muss, als auch die genauen Zeitpunkte der Abschaltung einiger dieser Kraftwerke zur Betankung und Wartung. Eine gültige Lösung muss außerdem noch für diesen Anwendungsfall definierte Bedingungen erfüllen (z.B. dürfen nur eine bestimmte Menge an Kraftwerken innerhalb eines Zeitfensters abgeschalten werden).

Wir haben uns bereits erfolgreich für die Endphase qualifiziert. Die finale Version des Programmes muss bis zum 5.Juni 2010 eingereicht werden. Daher sollte das Praktikum auch in dieser Zeit abgeschlossen werden.

Für mehr Details siehe entsprechende Webseite.

Multilevel Ansatz für das Consensus Tree Problem

Umfang
Praktikum (ev. auch Diplomarbeit)
Auskunft
Sandro Pirkwieser

Beim Consensus Tree Problem geht es darum anhand von mehreren Eingabebäumen (z.B. phylogenetischen Bäumen) einen repräsentativen Baum abzuleiten, der allen Eingabebäumen möglichst ähnlich ist. Es gibt viele Ansätze, die jedoch unterschiedliche Schwächen aufweisen. Wir beschäftigen uns zur Zeit mit binären Bäumen gleicher Größe und modellieren das Problem als Optimierungsproblem, d.h. der Lösungsbaum (=Konsensbaum) soll möglichst gleich den Eingabebäumen sein. Dafür wird vorwiegend die sogenannte TreeRank-Measure verwendet.

Ein vielversprechender Ansatz für schwierige und vor allem große Probleme besteht darin, das Problem in unterschiedlichen Detailstufen zu betrachten. Ausgehend vom Originalproblem werden sukzessive einzelne Problemkomponenten zuammengefasst bis man auf der höchsten (gröbsten) Stufe ist. Danach wird iterativ das Problem in der jeweiligen Detailstufe lokal optimiert und anschließend wieder um eine Stufe verfeinert. Dadurch ist es möglich mit den gleichen Nachbarschaften unterschiedliche Bereiche des Gesamt-Suchraumes abzudecken. Für das Consensus Tree Problem bietet es sich an einzelne Taxa zu Sub-Bäumen und letztere mit anderen Sub-Bäumen zu vereinigen um unterschiedliche Detailstufen zu erhalten. Ein bestehendes Programm in C++ kann als Ausgangsbasis dienen.

Golomb-Ruler Problem

Umfang
Praktikum
Auskunft
Andreas Chwatal

Anschaulich, kann man sich einen Golomb-Ruler als ein Lineal vorstellen, dessen Skala bestimmte Eigenschaften hat. Zunächst soll die Skala nur aus Markierungen an Stellen von ganzen Zahlen bestehen. Darüber hinaus wird gefordert, dass die paarweisen Abstände dieser Markierungen jeweils unterschiedlich sein sollen. Ein Lineal mit derartigen Eigenschaften nennt man Golomb-Ruler, hat es zusätzlich minimale Länge, so nennt man es Optimal Golomb-Ruler (OGR).

Die Berechnung beweisbar optimaler GR ist bis heute nur bis zu einer Länge von n=24 möglich! Und das trotz massivstem Einsatz von Parallelität. Interessanterweise ist bis heute nicht klar, ob das OGR Problem NP-vollständig ist.

Basierend auf zahlreichen metaheuristischen Ansätzen in der Literatur, sollen weitere, verbesserte Metaheuristiken zur Lösung des OGR Problems implementiert werden.

Steiner Ring Star Problem

Umfang
Diplomarbeit (ev. auch Praktikum)
Auskunft
Markus Leitner

Das Steiner Ring Star Problem (SRS) tritt beim Design von Netzwerken mit Anforderungen hinsichtlich Ausfallsicherheit auf. Gegeben ist ein Graph mit positiven Kantenkosten, die analog zum Steiner Tree Problem den Ausbaukosten entsprechen. Analog zum STP besteht die Knotenmenge aus den Kundenknoten und sogenannten Steinerknoten, welche hier zusätzlich als Hubs verwendet werden können. Weiters sind Zuweisungkosten zwischen diesen potentiellen Hubs und den Kundenknoten, sowie Aktivierungskosten für die Hubs gegeben. Eine Lösung des SRS besteht aus einer Menge von aktiven Hubs, welche redundant mittels einer Ringtopologie verbunden werden müssen. Weiters muss jeder Kunde genau einem Hub zugewiesen werden. Gesucht ist hier eine Lösung, welche die Summe der Ausbaukosten aufgrund des Ringes zwischen den Hubs, plus die Summe der Aktivierungskosten für aktivierte Hubs und die Summe der Zuweisungskosten zwischen Kunden und aktiven Hubs minimiert.

Konkrete Themen sind je nach Interesse sowohl im Bereich der Metaheuristiken als auch exakter Verfahren möglich.

Disjoint Pair of directed Paths Problem

Umfang
Praktikum
Auskunft
Markus Leitner

Als Subproblem in einem existierenden Spaltengenerierungsansatz für ein Problem aus dem Bereich Survivable Network Design muss eine spezielle Variante des Disjoint Pair of Paths Problems gelöst werden, bei dem das Summe kostengünstigste, entgegengesetzt gerichtete, disjunkte Paar von Pfaden zwischen zwei Knoten berechnet werden muss. Im Rahmen dieses Praktikums sollen Algorithmen zur Lösung dieses Problems implementiert und verglichen werden.


Critical Links Detection to Maintain Small Diameter against Link Failures

Umfang
Praktikum oder Diplomarbeit
Auskunft
Bin Hu

Bei diesem Problem ist eine Netzwerk-Infrastruktur als Graph vorgegeben. Die Qualität des Netzwerks ist durch dessen Durchmesser (der längste Weg bezüglich der Anzahl der Kanten von einem Knoten zu einem anderen) bestimmt. Da Kanten im Netzwerk ausfallen und damit den Durchmesser erhöhen können, müssen bestimmte Kanten geschützt werden. Es gilt, eine möglichst kleine Menge von Kanten zu schützen, um einen gewissen Durchmesser zu garantieren, falls eine bestimmte Anzahl ungeschützter Kanten ausfallen.

(Beispiel: Wenn die Kante (v7,v8) geschützt ist, kann eine beliebige andere Kante ausfallen und ein Durchmesser von 4 kann garantiert werden. Falls diese Kante ungeschützt ist und sie fällt aus, entsteht ein Netzwerk mit Durchmesser 5.)

Mögliche Themen:

  • Massive Parallel Computing, GPU Programming


Negative Cost Subset Disjoint Cycle Problem

Umfang
Praktikum
Auskunft
Markus Leitner

Als Subproblem eines existierenden Very Large Scale Neighborhood Search Ansatzes, tritt das Negative Cost Subset Disjoint Cycle Problem auf, bei dem bestimmte Kreise mit negativen Kosten in einem Graph gefunden werden müssen. Hier wird bisher eine einfache, aber durchaus effektive Heuristik eingesetzt. In einer aktuellen Publikation wurden neue (u.a. auch exakte) Algorithmen zur Lösung dieses Problems vorgestellt, welche im Rahmen dieses Praktikums implementiert und mit der existierenden Lösung verglichen werden sollen.


Unterschiedliche Themen im Bereich der Rekonstruktion von zerstörten Papierseiten

Umfang
Praktikum oder Diplomarbeit
Auskunft
Matthias Prandtstetter

Gegeben ist eine Menge von Papierschnipsel. Gesucht ist das originale Dokument, das unter Umständen aus mehr als einer Seite bestand.

Es existiert bereits ein relativ umfangreiches Framework zum Finden von Lösungen für das oben genannte Problem, das in Java implementiert wurde. Es gilt nun, Erweiterungen für dieses Framework zu implementieren, die die Lösungsfindung verbessern. Ein Großteil der von Ihnen zu entwickelnden Ansätze wird mittels Java zu implementieren sein. Dennoch ist eine Anbindung von C/C++-Bibliotheken über JNI möglich und stellt kein Problem dar.

Die Aufgabenstellungen, die noch bearbeitet werden können, reichen von kurzen Praktikumsarbeiten, die sich hauptsächlichen mit der Implementierung von kleinen Verebsserungen oder Reimplementierung von bereits existierenden Ansätzen beschäftigen bis zu Diplomarbeitsthemen, bei denen unter anderem eine Entwicklung von informationsaustauschenden Metaheuristiken zu machen wäre.

Heuristiken für einen Lagrange Relaxierungsansatz

Umfang
Praktikum
Auskunft
Matthias Prandtstetter

Viele exakte und heuristische Verfahren beruhen darauf, gute Schranken, die den Lösungsraum einschränken, zu berechnen. Ein solches Standardverfahren ist die Lagrange Relaxierung, bei der schwer zu erfüllende Nebenbedingungen aus der originalen Problemformulierung entfernt werden und dafür in die Zielfunktion eingearbeitet werden. Das dadurch entstehende (im Normalfall) leichtere Problem muss nun in einem iterativen Prozess mehrfach exakt gelöst werden, um gute Schranken zu berechnen.

Im Rahmen dieses Praktikums soll ein Verfahren entwickelt werden, mit dessen Hilfe es möglich wird, das wiederholte exakte Lösen des Subproblems durch heuristische Verfahren zu approximieren und so eine entscheidende Performancesteigerung im Laufzeitverhalten des Verfahrens zu erlangen. Entscheidend für die erstrebte Verbesserung sind effiziente Heuristiken, die für das Car Sequencing Problem bzw. für das Puzzle Problem entwickelt und implementiert werden sollen.

Da schon große Teile eines Frameworks existieren, muss diese Arbeit in C++ implementiert werden. Grundlegende Kenntnisse dieser Programmiersprache sollten vorhanden sein.

Verbesserung einer Konstruktionsheuristik / eines EAs für das BDMST Problem

Umfang
Praktika
Auskunft
Martin Gruber

Das Bounded Diameter Minimum Spanning Tree (BDMST) Problem kommt aus dem Bereich des Netzwerkdesigns, hat aber durchaus auch noch weitere Anwendungsgebiete, z.B. bei der Datenkomprimierung oder bei Distributed Mutual Exclusion Algorithmen.

Ziel ist es, einen minimalen Spannbaum in einem Graphen zu finden, wobei der Durchmesser, d.h. die maximale Anzahl an Kanten zwischen je zwei beliebigen Knoten, nach oben hin beschränkt ist. Obwohl man einen MST sehr einfach mit Hilfe der Algorithmen von Kruskal oder Prim bestimmen kann, macht das Hinzufügen der Durchmesserbeschränkung das Problem NP-schwer (ab einem Durchmesser von 4).

Für dieses Problem haben wir unterschiedliche Ansätze entwickelt, unter anderem eine Konstruktionsheuristik basierend auf Clustering und einen einen evolutionären Algorithmus (EA), der eine spezielle Kodierung von Lösungen einsetzt. Beide Verfahren liefern bereits sehr gute Ergebnisse, bieten aber durchaus noch Potential für Verbesserungen.

Die Details der einzelnen Aufgaben können nur schwer in wenigen Sätzen zusammengefasst werden. Bei der Clustering-Heuristik steht die Arbeit mit dynamischen Datenstrukturen im Vordergrund (Manipulationen an binäre Bäumen), wohingegen beim EA das Verhalten der aktuellen Implementation (der EA liefert sehr gute Ergebnisse, konvergiert aber zu rasch) genau analysiert werden muss, um entsprechende Gegenmaßnahmen treffen zu können. Alle Programme liegen in C++ vor.

Implementation von Modellen aus der Literatur

Umfang
Praktikum
Auskunft
Martin Gruber

Das Bounded Diameter Minimum Spanning Tree (BDMST) Problem kommt aus dem Bereich des Netzwerkdesigns, hat aber durchaus auch noch weitere Anwendungsgebiete, z.B. bei der Datenkomprimierung oder bei Distributed Mutual Exclusion Algorithmen.

Ziel ist es, einen minimalen Spannbaum in einem Graphen zu finden, wobei der Durchmesser, d.h. die maximale Anzahl an Kanten zwischen je zwei beliebigen Knoten, nach oben hin beschränkt ist. Obwohl man einen MST sehr einfach mit Hilfe der Algorithmen von Kruskal oder Prim bestimmen kann, macht das Hinzufügen der Durchmesserbeschränkung das Problem NP-schwer (ab einem Durchmesser von 4).

Wir haben für dieses Problem einen exakten Lösungsansatz entwickelt. Ein direkter Laufzeitvergleich mit in der wissenschaftlichen Literatur veröffentlichten Verfahren gestaltet sich aber ohne deren Reimplementation schwierig, da veröffentlichte Ergebnisse zum Teil auf stark veralteter Hardware generiert wurden.

Im Zuge des Praktikums sollen nun – dem jeweiligen Aufwand endsprechend – eine oder mehrere Algorithmen aus der Literatur implementiert werden. Dabei handelt es sich in erster Linie um Inter Linear Programs, die mit Hilfe eines sogenannten LP-Solvers gelöst werden müssen, in unserem Fall CPLEX. Als Programmiersprache soll C++ zum Einsatz kommen.

Neue Nachbarschaftssuchen für das durchmesserbeschränkte Spannbaumproblem

Umfang
Praktikum
Auskunft
Martin Gruber

Das Bounded Diameter Minimum Spanning Tree (BDMST) Problem kommt aus dem Bereich des Netzwerkdesigns, hat aber durchaus auch noch weitere Anwendungsgebiete, z.B. bei der Datenkomprimierung oder bei Distributed Mutual Exclusion Algorithmen.

Ziel ist es, einen minimalen Spannbaum in einem Graphen zu finden, wobei der Durchmesser, d.h. die maximale Anzahl an Kanten zwischen je zwei beliebigen Knoten, nach oben hin beschränkt ist. Obwohl man einen MST sehr einfach mit Hilfe der Algorithmen von Kruskal oder Prim bestimmen kann, macht das Hinzufügen der Durchmesserbeschränkung das Problem NP-schwer (ab einem Durchmesser von 4).

Wir haben in den letzten Jahren unerschiedliche Verfahren zur Lösung dieses Problems entwickelt, darunter einige Metaheuristiken (Variable Neighborhood Search [VNS], Ant Colony Optimization [ACO], Evolutionary Algorithm [EA]). Zur lokalen Verbesserung werden aktuell vier unterschiedlichen Nachbarschaftssuchen eingesetzt.

Ziel dieses Praktikums wäre es nun, neue Nachbarschaften für dieses Problem zu definieren und entsprechende Suchoperatoren effizient in C++ zu implementieren. Ein in diesem Zusammenhang besonders interessanter Aspekt ist, dass in jüngerer Zeit große Fortschritte bei der exakten Lösung von BDMST Problemen mit bis zu 40 Knoten erzielt wurden. Damit ist es nun erstmals möglich, kleinere Subprobleme sinnvoller Größe exakt zu lösen; dies kann für die Definition neuer Nachbarschaften verwendet werden.

Suche nach Transits von Exoplaneten

Umfang
Praktikum
Auskunft
Andreas Chwatal

Eine Methode Planeten bei anderen Sternen nachzuweisen basiert auf sogenannten Transits. Unter einem Transit versteht man das Ereignis, wenn der Planet direkt vor dem Stern vorbeiläuft, und somit einen geringen Anteil seines Lichtes abschattet.

Ein Detektionsalgorithmus versucht nun ein möglichst gutes Modell an die Daten zu fitten. Im Falle von Mehrplanetensystemen stellt dies jedoch eine schwierige Aufgabe dar und metaheuristische Ansätze sind hierbei eine interessante Alternative zu exakten Methoden.

Im Zuge dieses Praktikums soll eine Particle Swarm Optimization (PSO) implementiert und getestet werden. PSO ist ein populationsbasierendes stochastisches Optimierungsverfahren, inspiriert vom Verhalten von Vogel- oder Fischschwärmen. Der Algorithmus soll in ein bestehendes Java-Framework integriert werden, welches bereits Klassen zur Modellierung, I/O, lokalen Methoden und anderen Metaheuristiken beinhaltet.

Distributed information sharing hybrid (meta)heuristics

Umfang
Praktikum oder Diplomarbeit
Auskunft
Matthias Prandtstetter

Im Rahmen dieser Arbeit soll ein Framework entwickelt werden, mit dessen Hilfe es möglich wird, Metaheuristiken (oder auch exakte Algorithmen) parallel auszuführen. Dabei soll das Framework den Informationsaustausch zwischen den einzelnen, parallel ablaufenden Instanzen der Metaheuristiken unterstützen.

Neben dem Design und der Implementierung der Netzwerkkommunikation soll im Rahmen des Arbeit dieses Framework getestet werden. Als Anwendungsgebiet dient die Rekonstruktion von in Streifen geschnittenen Papierdokumenten. Für diese Aufgabenstellung existieren bereits einzelne Algorithmen, die unter geringen Änderungen in das Framework als Beispielapplikation integriert werden sollen. Da diese bereits existierenden Algorithmen in Java implementiert sind, soll auch das übrige Framework in Java geschrieben werden.

Branch-and-Bound-ACO

Umfang
Praktikum, evtl. Diplomarbeit
Auskunft
Andreas Chwatal, Günther Raidl

Für viele kombinatorische Optimierungsprobleme erweisen sich hybride Algorithmen als günstig. So lieferte beispielsweise die Kombination von Ant Colony Optimization (ACO) mit Beam-Search (BS) vielversprechende Ergebnisse bei einigen Problemen. ACO ist ein modellbasierendes Optimierungsverfahren, dessen Mechanismen an die Funktionsweise einer Ameisenkolonie (z.B. bei der Futtersuche) angelehnt sind. BS ist vereinfacht gesagt eine beschränkte Breitensuche.

Verbesserungen des Beam-ACO Ansatzes könnten etwa sein, BS durch einen etwas ausgefeilteren Branch-and-Bound Ansatz zu ersetzen. Diese Idee soll im Zuge eines Praktikum, angewandt auf ein konkretes Problem, umgesetzt werden (proof of concept). Bei Erfolg, ist eine anschliessende Diplomarbeit möglich.

Multi-Gravity-Assist Optimization

Umfang
Praktikum
Auskunft
Andreas Chwatal

Raumsonden die in weit entfernt gelegene Regionen des Sonnensystems vordringen sollen, erreichen ihr Ziel üblicherweise nur unter Zuhilfenahme sogenannter Gravity-Assists bei Planeten. Hierbei fliegt die Raumsonde nahe an einem Planeten vorbei, und wird durch dessen Schwerkraft abgelenkt. Neben der Richtungsänderung erfährt die Raumsonde jedoch auch eine Beschleunigung, da ein minimaler Anteil des Bahndrehimpulses des Planeten auf die Raumsonde übertragen wird. Missionen zu weit entfernten Zielen werden erst dadurch ermöglicht indem bei mehreren Planeten derart beschleunigt wird (Multi-Gravity-Assist, MGA). Eine optimal gewählte Flugbahn bietet darüber hinaus ein erhebliches Potential die notwendige Antriebsenergie der Sonde zu minimieren.

Die Berechnung von MGAs ist ein kontinuierliches Parameteroptimierungsproblem. Von der esa (european space agency) wird ein Framework zur Verfügung gestellt, dass es ermöglicht das Problem als Black-Box zu behandeln. D.h. ein vorhandenes C++ Framework retourniert zu konkreten Anfangsbedingungen der Flugbahn (=Optimierungsparameter) einen Zielfunktionswert (der im wesentlichen dem Energiebedarf der resultierenden Flugbahn entspricht).

Im Zuge dieses Praktikums sollen Metaheuristiken aus dem Bereich der kontinuierlichen Parameteroptimierung (z.B. Evolution Strategies, Particle Swarm Optimization, Differential Evolution) auf das Problem angewandt werden.


Implementierung eines Branch-and-Cut-and-Price Verfahrens für eine Variante des Minimum Label Spanning Tree Problems

Umfang
Praktikum
Auskunft
Andreas Chwatal

Im Zuge unserer Forschungstätigkeiten bezüglich eines Datenkompressionsverfahrens (Anwendungshintergrund: Biometric Template Compression) betrachten wir verschiedene Varianten des Minimum Label Spanning Tree Problems (MLST). Bei diesem Problem werden den Kanten eines Graphen verschiedene Labels zugewiesen und eine optimale Lösung besteht aus einem Spannbaum in diesem Graphen der möglichst wenige Kantenlabels benötigt.

Branch-and-Cut-and-Price vereint im Wesentlichen die Ideen der Spaltengenerierung und Branch-and-Cut. In den Knoten des Branch-and-Bound Baumes werden sowohl verletzte Ungleichungen als auch neue Variablen dem Modell dynamisch hinzugefügt. Ziel dieser Arbeit ist die Implementierung eines Branch-and-Cut-and-Price Algorithmus mittels COIN-OR.


Erweiterung einer bestehenden Library für Metaheuristiken

Umfang
Praktikum
Auskunft
Andreas Chwatal

Im Zuge unserer Forschungstätigkeit, Diplomarbeiten und Praktika kommt oftmals eine am Institut entwickelte C++ Library für Evolutionäre Algorithmen und Metaheuristiken namens ealib zum Einsatz. Im Zuge eines Praktikums soll diese Library um weitere Metaheuristiken erweitert werden. Ein mögliches Beispiel wäre Ant Colony Optimization (ACO), eine auf dem Prinzip der Selbstorganisation (angelehnt an die Mechanismen in einer Ameisenkolonie) basierende Metaheuristik.

Vorraussetzungen sind gute C++ Kenntnisse, und die Bereitschaft sich in das bestehende Framework einzuarbeiten. Im Zuge des Praktikums soll eine Metaheuristik implementiert, getestet und dokumentiert werden.


Periodische Transportprobleme

Umfang
mehrere Praktika bzw. Diplomarbeiten möglich
Auskunft
Sandro Pirkwieser

Transportprobleme treten in vielen Bereichen des täglichen Lebens auf. Dabei geht es generell um die Zustellung von produzierten Gütern an Kunden und um die Entscheidung wann und von wem diese Güter den Kunden zugestellt werden. Eine Verbesserung der Lösung spiegelt sich direkt in den daraus resultierenden Kosten wider und beeinflusst auch andere wichtige Faktoren wie zum Beispiel die Kundenzufriedenheit. Aufgrund der Mannigfaltigkeit der zu treffenden Entscheidungen handelt es sich bei Transportproblemen um äußerst komplexe Kombinationen von Zuordnungsproblemen und Aufgabenstellungen aus dem Bereich der Reihenfolge- und Tourenplanung. Wir konzentrieren uns auf spezielle Transportprobleme: Aufgabenstellungen, bei denen mehrfache Belieferungen der Kunden erforderlich sind. Mittels verschiedener hybrider Ansätze von Metaheuristiken und ganzzahliger linearer Programmierung sollen bessere Lösungen als mit herkömmlichen Methoden erzielt werden.

Variable Neighborhood Search für das PVRPTW
Beim Periodic Vehicle Routing Problem with Time Windows (PVRPTW) müssen Kunden mehrmals während eines definierten Planungshorizontes beliefert werden. Dabei geben die einzelnen Kunden eine Lieferhäufigkeit sowie eine Menge an möglichen Kombinationen von Liefertagen vor (z.B. zwei Zustellungen pro Woche, möglich am Montag und Donnerstag oder Dienstag und Freitag). Zusätzlich muss für jeden Kunden ein Zeitintervall beachtet werden, welches die mögliche Zustellzeit angibt. Die Aufgabe besteht darin sowohl eine Kombination von Liefertagen pro Kunde auszuwählen als auch für jeden Tag das daraus resultierende Tourenplanungsproblem zu lösen. Im Zuge dieser Arbeit soll eine entsprechende Variable Neighborhood Search (VNS) Metaheuristik (Artikel von Hansen und Mladenović) entwickelt und implementiert werden. Abschließend soll die VNS mit einer existierenden Tabu Search verglichen werden. Die Implementierung sollte aufgrund der von uns geplanten Kombination mit den exakten Verfahren in C++ erfolgen.
Lösen des Pricing-Subproblems während der Spaltengenerierung mittels exaktem Verfahren und heuristischen Methoden
Implementieren eines randomisierten Algorithmus (Monte Carlo Methode) zum Finden des minimalen Schnittes (minimum cut) (Praktikum)
Der Algorithmus von Karger findet mit einer gewissen Wahrscheinlichkeit (steigt mit der Anzahl der Aufrufe) den minimalen Schnitt in einem Graphen, bzw. je nach Einstellung auch "fast minimale" Schnitte. Letztere werden von uns dazu benötigt um verletzte Ungleichungen eines bestimmten Typs zu finden die dem ILP Modell hinzugefügt werden um dieses zu stärken. Da der Algorithmus in das bestehende Framework eingebettet werden soll, ist eine Implementierung in C++ erwünscht.
Bidirektionaler Algorithmus zum Finden des kürzesten Pfades (Praktikum)
Das Finden des kürzesten Pfades mit zusätzlichen Beschränkungen hinsichtlich der Kapazität, des Zeitlimits und der Zeitfenster kommt als Subproblem beim Lösen der Spaltengenerierung vor. Ein exakter Ansatz basiert auf dynamischer Programmierung, bei dem die Pfade sukzessive vom Depot ausgehend erweitert werden. In der Literatur finden sich einige Ergebnisse die zeigen, dass es von Vorteil sein kann die Pfade gleichzeitig von vorne nach hinten und umgekehrt zu expandieren. Dadurch wird die Laufzeit im Allgemeinen oftmals drastisch reduziert. Deshalb sollen zwei bestehende Algorithmen, ein vorwärts und ein rückwärts Expandierender, zu einem Algorithmus kombiniert werden.
Entwicklung von (Meta-)Heuristiken für das PVRPTW (Praktikum oder Diplomarbeit)
Zusätzlich zu einer von uns entwickelten variablen Nachbarschaftssuche (VNS) und einer Tabu Suche von Cordeau et al. wäre es auch interessant andere (Meta-)Heuristiken auf dieses Problem anzuwenden. Denkbar wäre z.B. ein evolutionärer Algorithmus, eine Ant Colony Optimization (ACO) Metaheuristik (Artikel M. Dorigo), als auch eine Scatter Search die jeweils durch eine entsprechende lokale Suche gestärkt werden könnten. Natürlich ist auch ein geeignetes hybrides Verfahren realisierbar.
Verbessern eines dynamischen Programmes zum Finden des kürzesten Weges (Praktikum)
Bei diesem Praktikum soll ein bestehender dynamischer Programmieralgorithmus hinsichtlich des Laufzeitverhaltens verbessert werden. Eine Möglichkeit besteht darin die Lösungen sowohl in normaler als auch umgekehrter Reihenfolge aufzubauen. Dabei kann man bestehende Algorithmen verwenden. Desweiteren existieren andere Ansätze in der Literatur die man implementieren bzw. in das bestehende Programm einbauen kann.
Erzeugen gültiger Lösungen während eines Spaltengenerierungsprozesses
Um für das genannte Problem untere Schranken, d.h. Zielfunktionswerte die von gültigen Lösungen nicht unterschritten werden können, zu finden, wird die Linear Programming (LP) Relaxierung mittels Spaltengenerierung gelöst. Abgesehen von einer optional verwendeten gültigen Startlösung erhält man keine zusätzlichen gültigen Lösungen. Ziel dieses Praktikums ist es daher eine bzw. mehrere Methoden zu entwickeln die bereits während des Spaltengenerierungsprozesses gültige Lösungen generieren. Ein erster Ansatz wäre gültige Lösungen durch einfaches Runden der LP Lösung und anschließendem Reparieren zu erhalten.
Evolutionärer Algorithmus für das Subproblem bei der Spaltengenerierung
Für das wiederholt auftretende kürzeste-Wege Subproblem bei der Spaltengenerierung ist ein geeigneter Evolutionärer Algorithmus (EA) zu entwickeln, zu implementieren, und anschließend zu testen. Dabei ist von Vorteil, dass der EA bei der nächsten Ausführung das Wissen (Lösungen) der vorigen Anwendung direkt ausnützen kann. Der Algorithmus ist dahingehend zu untersuchen wie schnell die Spaltengenerierung terminiert und welche Qualität die heuristisch generierten Spalten hinsichtlich der Verwendung in einer gültigen Lösung haben.

Consensus Tree Problem

Umfang
mehrere Praktika bzw. Diplomarbeiten möglich
Auskunft
Sandro Pirkwieser

Beim Consensus Tree Problem geht es darum anhand von mehreren Eingabebäumen (z.B. phylogenetischen Bäumen) einen repräsentativen Baum abzuleiten, der allen Eingabebäumen möglichst ähnlich ist. Es gibt viele Ansätze, die jedoch unterschiedliche Schwächen aufweisen. Wir beschäftigen uns zur Zeit mit binären Bäumen gleicher Größe und modellieren das Problem als Optimierungsproblem, d.h. der Lösungsbaum (=Konsensbaum) soll möglichst gleich den Eingabebäumen sein. Dafür wird vorwiegend die sogenannte TreeRank-Measure verwendet.

Folgende Teilaspekte können in Praktika bzw. Diplomarbeiten bearbeitet werden:

Rekombinationsoperatoren

Der Rekombinationsoperator sorgt in Evolutionären Algorithmen dafür, dass aus üblicherweise zwei Elternchromosomen (mindestens) ein Nachkomme erzeugt wird. Dabei soll möglichst viel Information der Elternteile übertragen werden und durch die Mischung ein neues, besser angepasstes Chromosom (=bessere Lösung) generiert werden. Am vielversprechendsten sind spezielle problemspezifische Rekombinationsoperatoren.

Eine oft angewandte Rekombination für Bäume geht so vor, dass aus einem Elternteil ein Subbaum selektiert wird und entsprechend im zweiten Elternteil "eingepflanzt" wird.

In diesem Praktikum ist eine analytische Untersuchung bereits bestehender Operatoren durchzuführen (z.B. wie verschieden sind die erzeugten Nachkommen von den Eltern), als auch neue zu entwickeln, zu implementieren und mit den anderen zu vergleichen. Es existiert ein Framework in C++ das verwendet werden soll.

Scatter Search mit Path Relinking

Scatter Search (Artikel M. Laguna, Artikel R. Marti) gehört wie der bekanntere Genetische Algorithmus zu den Evolutionären Algorithmen, jedoch mit einem wesentlichen Unterschied: anstatt wie der GA in vielen Bereichen das Element des Zufalls auszunützen wird systematischer vorgegangen. Man hat zum Beispiel eine kleinere aber qualitativ hochwertigere Population, probiert unter Umständen alle möglichen Kombinationen aus um neue Lösungen zu erzeugen, und letztere werden in Anlehnung an eine lineare Kombination zweier bestehender Lösungen generiert (siehe Grafik rechts). Dazu kann Path Relinking angewandt werden: ausgehend von einer Startlösung bewegt man sich im Lösungsraum schrittweise in Richtung einer Ziellösung um auf dem Weg bessere Lösungen zu finden.

Es soll für das Consensus Tree Problem die Scatter Search Metaheuristik mit Path Relinking implementiert und getestet werden, wobei man anfänglich nach einer bereits publizierten Variante für phylogenetische Bäume vorgehen kann. Mann sollte im eigenen Interesse ein bestehendes Framework in C++ verwenden.

Ant Colony Optimization (Diplomarbeit, evtl. auch Praktikum)

Die Ant Colony Optimization (ACO) Metaheuristik (Artikel M. Dorigo) nimmt Anlehnung an die Fähigkeit von Ameisen die kürzesten (=besten) Wege zu ihren Futterquellen zu finden. Dabei wird anfänglich zufällig nach Lösungen gesucht - welche immer inkrementell gebildet werden - und durch individuelle Verstärkung des zurückgelegten "Weges", abhängig von der Lösungsgüte, kristallisiert sich mit der Zeit eine (nahezu) optimale Tour welcher der am besten gefundenen Lösung entspricht. Man spricht hierbei von emergentem Verhalten.

Die Aufgabe dieses Praktikums ist nun eine entsprechende ACO Metaheuristik für das Consensus Tree Problem zu entwickeln und zu implementieren. Generierte Lösungen können dann bei Bedarf mit bereits bestehenden anderen (Meta-)Heuristiken weiter verbessert werden. Es gibt bereits ACO Algorithmen die für die Optimierung auf Bäumen angewandt wurden, jedoch bei einem anderen Problem, nach denen man sich richten kann. Zwecks Kombination mit den anderen Algorithmen wird C++ empfohlen.

Knapsack Constrained Maximum Spanning Tree Problem

Umfang
mehrere Praktika bzw. Diplomarbeiten möglich
Auskunft
Sandro Pirkwieser

Das Knapsack Constrained Maximum Spanning Tree Problem (KCMST Problem) besteht darin für einen gegebenen Graphen mit Kantenprofiten und -gewichten einen profitmaximalen Spannbaum zu finden welcher eine ebenfalls gegebene Gewichtsbeschränkung einhält. Man kann sich vorstellen für ein Netzwerk mit Kantenkosten einen Spannbaum finden zu müssen während das festgelegte Gesamtbudget nicht überschritten wird.

Folgende Praktika bzw. Diplomarbeiten sind aktuell möglich:

Kombination eines Evolutionären Algorithmus mit Branch-and-Cut

Ein generell sehr vielversprechender Ansatz ist die Hybridisierung von exakten und heuristischen Verfahren. Es existiert bereits ein Evolutionärer Algorithmus mit problemspezifischen Operatoren als auch ein Branch-and-Cut (B&C). Letzteres ist prinzipiell ein Branch-and-Bound bei dem zusätzlich in den Knoten des Enumerationsbaums Cuts generiert werden um die Formulierung zu stärken. Die beiden komplementären Methoden sollen nun in unterschiedlicher Weise kombiniert werden. Beide Praktika sind für C++ vorgesehen. </dd>

Verschachtelte Ausführung beider Algorithmen

Bei dieser Variante sind beide Algorithmen als gleichwertig anzusehen. Es soll ein größtmöglicher Informationsaustausch zwischen ihnen stattfinden. Eine einfache Form ist das gegenseitige Übergeben von besseren Lösungen. Auch andere Formen dieser kollaborativen Kooperation sind zu entwickeln bzw. zu implementieren. </dd>

Einsatz von B&C im EA

Das Thema dieses Praktikums ist es das exakte Verfahren sinnvoll innerhalb der Metaheuristik einzusetzen. Bei dieser integrativen Kombination ist das B&C ein untergeordneter Algorithmus des EA's. Zwei zu untersuchende Einsatzmöglichkeiten sind:

  1. einen exakten Rekombinationsoperator (exact merging) zu realisieren, d.h. man sucht innerhalb des Lösungsraumes beider Elternteile die beste Lösung und macht diese zum Nachkommen
  2. man definiert (große) Nachbarschaften und durchsucht diese vollständig, man spricht dabei von einer Very Large Scale Neighborhood Search


Effiziente Implementierung eines Dynamischen Programms zum Berechnen von optimalen Touren unter Ausnutzung spezieller Graphenstrukturen

Umfang
Praktikum
Auskunft
Matthias Prandtstetter

Im Rahmen dieser Arbeit soll ein bereits existierender Ansatz basierend auf dynamischer Programmierung neu implementiert werden. Dabei soll das Hauptaugenmerk auf eine effiziente Implementierung gelegt werden, da das bereits existierende Codestück als Teil eines größeren Frameworks sich als Flaschenhals im Laufzeitverhalten herausgestellt hat. Vor allem eine inkrementelle Berechnung von Lösungen anhand bereits absolvierter Lösungsdurchläufe soll realisiert werden. Eigene Ideen zur (Code-)Optimierung können und sollen bei diesem Praktikum einfließen, sodass letztendlich ein zuverlässiger und schneller Lösungsansatz zum Berechnen von Touren in einem Graphen mit speziellen Eigenschaften entstehen wird.

Da dieser Ansatz Teil eines größeren Frameworks ist, muss eine Implementierung in Java vorgenommen werden.

Lösungsansätze für eine Lagerverwaltung

Umfang
Diplomarbeit
Auskunft
Matthias Prandtstetter, Günther Raidl, Andreas Chwatal

Folgende aus dem industriellen Alltag entnommene Aufgabenstellung ist gegeben: Das Lager eines Ersatzteillieferanten soll umgestaltet werden, wobei ein Hauptaugenmerk auf die Verwaltungssoftware gelegt wird. Diese Software soll es ermöglichen, die Arbeitsabläufe innerhalb des Lagers zu optimieren. Derzeit wird wie folgt verfahren:

  1. Die Bestellung wird von einem Mitarbeiter entgegengenommen und an den Lagerleiter weitergeleitet.
  2. Der Lagerleiter gibt einem seiner Mitarbeiter den Auftrag, die einzelnen in dieser Bestellung verlangten Artikel aus dem Lager auszufassen und zur Verpackungszone zu bringen.
  3. Ein Mitarbeiter in der Verpackungszone schachtelt die einzelnen Teile ein, versieht das bzw. die Pakete mit Adresspickerl und leitet die Postsendung an einen Lieferanten weiter.

Kommen mehrere Bestellungen gleichzeitig herein, so kann es durchaus sein, dass der Lagerleiter im Schritt 2 einen Mitarbeiter beauftragt, gleich mehrere Bestellungen gleichzeitig zu bearbeiten. Auf alle Fälle kommt es aber häufig dazu, dass ein Mitarbeiter lange Wege innerhalb des Lagers zurücklegen muss, um die einzelnen Artikel einzusammeln. Daher soll folgende neue Methodik angewandt werden:

  1. Die Bestellung wird von einem Mitarbeiter entgegengenommen und an den Lagerleiter weitergeleitet.
  2. Der Lagerleiter teilt diese Bestellung in Teilbestellungen auf, und übergibt diese Teilbestellungen an mehrere Mitarbeiter.
  3. Die Mitarbeiter machen sich auf den Weg durch das Lager und fassen die auf ihnen zugeteilten Teilbestellung aufgelisteten Artikel aus.
  4. Alle Mitarbeiter bringen die von ihnen ausgefassten Artikel in die Verpackungszone, wo wiederum ein Mitarbeiter damit beauftragt wird, die originalen Bestellungen zusammenzustellen, zu verpacken und an den Kunden zu versenden.

Auch bei diesem Ansatz kann es dazu kommen, dass mehrere Bestellungen gleichzeitig an mehrere Mitarbeiter aufgeteilt werden. Die Anzahl der zu holenden Artikel hängt dabei von der Kapazität der von den Mitarbeitern verwendeten Transportwägen ab. Man erhofft sich durch diese Änderung allerdings, dass die Touren der Mitarbeiter kürzer werden. Letztendlich versucht man möglichst kurze Touren für alle Mitarbeiter zu finden, sodass alle Bestellungen abgearbeitet werden und sämtliche (noch nicht erwähnten) Nebenbedingungen erfüllt werden.

Im Rahmen dieser Diplomarbeit gilt es einen Optimierer zu entwerfen, der möglichst kurze Touren unter Berücksichtigung aller Nebenbedingungen berechnet. Es ist aber nicht nötig Userinterface etc. zu programmieren. Bei Interesse kontaktieren Sie bitte eine der oben angegebenen Ansprechpersonen. Durch die Sommerferien und den gedrängten Zeitplan bedingt, empfehlen wir Ihnen sich gleich an alle drei Kontaktpersonen zu wenden.

What to do, after a shredder destroyed your only copy of your diploma thesis?

Umfang
Praktikum oder Diplomarbeit
Auskunft
Matthias Prandtstetter, Günther Raidl

Was soll man machen, wenn ein Aktenvernichter, die einzige existierende Kopie Ihrer Diplomarbeit vernichtet hat? Natürlich könnten Sie die Arbeit einfach nochmals verfassen, allerdings ist das Original für immer verloren. Sie könnten aber auch anfangen die einzelnen Papierschnipsel wieder zusammenzusetzen. Um diesen Prozess zu erleichtern, entscheiden Sie sich als kompetenter Informatiker dazu, Software zu entwickeln, die Ihnen diese Tätigkeit abnimmt.

Im Rahmen eines Praktikums oder auch einer Diplomarbeit gilt es eine oder mehrere (Meta-)Heuristiken zu entwickeln, die zerissene Papierseiten wieder zusammensetzen. Prinzipiell muss zuerst eine Zuordnung gefunden werden, welches Schnipsel zu welcher Seite gehört. In einem zweiten Schritt muss jede einzelne Seite wieder hergestellt werden. Im Optimalfall kann man die originalen Seiten zusammenfügen und so die scheinbar vernichteten Dokumente wieder herstellen. Im Normalfall kann man allerdings davon ausgehen, dass dies nicht ohne weiteres möglich sein wird. Daher wäre es - je nach Umfang der Arbeit - auch interessant, die neu entwickelten Methoden mit schon existierenden Verfahren zu kombinieren und so von beiden Ansätzen zu profitieren.

Metaheuristiken für das Car Sequencing Problem

Umfang
Praktikum (oder Diplomarbeit)
Auskunft
Matthias Prandtstetter

Beim Car Sequencing geht es darum, für eine Menge bestellter Fahrzeuge eine optimale Reihung für die sogenannte Bandauflage zu finden. Dabei sind einge Constraints, die von den einzelnen bei der Produktion zu durchlaufenden Arbeitsstationen definiert werden, zu beachten. Beispiele für diese Constraints wären, dass nur eine vorgegebene Anzahl von Fahrzeugen in einer Teilsequenz fixer Länge eine bestimmte Komponente wie zum Beispiel eine Klimaanlange erhalten dürfen, da die Einbauzeit für diese Komponente größer als die Taktzeit des Fließbandes ist. Weiters muss darauf geachtet werden, dass nur eine bestimmte Anzahl von aufeinander folgenden Fahrzeugen mit der selben Farbe gespritzt werden dürfen. Danach muss ein Farbwechsel auftreten. Allerdings versucht man die Anzahl der Farbwechsel zu minimieren.

Im Rahmen dieser Arbeit gilt es neue (Meta-)Heuristiken zu entwickeln bzw. bekannte Verfahren auf dieses Problem anzuwenden. Auch eine Verbindung heuristischer mit exakten Ansätzen wäre von Interesse. Neben der Entwicklung und Implementierung sollen diese Ansätze auch mit entsprechenden Benchmarkinstanzen getestet und mit anderen Verfahren verglichen werden.

Visualisierungen von Lösungen für das Puzzle-Problem

Umfang
Praktikum
Auskunft
Matthias Prandtstetter

Im Bereich der Restaurierung zerstörten Papiers (kurz auch Puzzle-Problem genannt) entwickelten wir schon einige unterschiedliche Ansätze zum Lösen des Problem, wobei in nächster Zeit die effiziente Implementierung und das Testen und Vergleichen der unterschiedlichen Methoden ansteht. Um die QUalität der Lösungen allerdings nicht nur als Zahlen (hauptsächlich Matrizen aus Nullen und Einsen) vor uns zu haben, benötigen wir leistungsfähige Visualisierungstools, denen es möglich ist unterschiedliche Lösungsfiles einzulesen und graphisch darzustellen. Damit die entwickelten Tools auch wirklich Verwendung finden, ist vorallem die plastische, d.h. gut vorstellbar und übersichtliche, Darstellung der Ergebnisse von essentieller Wichtigkeit.

Primär sollte man in C++ und Java Kenntnisse besitzen, um dieses Praktikum anzutreten, allerdings können auch andere Programmiersprachen zur Erstellung der Tools verwendet werden, wenn entscheidende Gründe für diese sprechen.

Solutionvalidator für das Puzzle-Problem

Umfang
Praktikum
Auskunft
Matthias Prandtstetter

Im Bereich der Restaurierung zerstörten Papiers (kurz auch Puzzle-Problem genannt) benötigen wir schnelle und effiziente Methoden, um die Qualität der von uns gefundenen Lösungen zu bewerten. Im Konkreten geht es darum, den aktuell verwendeten Solutionvalidator entsprechend zu verbessern, da dieser noch einige Tücken hat und bei gewissen Sonderfällen, die zwar selten aber dennoch auftreten, Probleme hat. Außerdem ist die derzeit existierende Bewertungsfunktion noch nicht ganz ausgereift und muss noch feinjustiert werden. Es wurde auch schon eine graphische Oberfläche zum Anzeigen der endgültigen Ausgabe implementiert, die nach Belieben angepasst und erweitert werden kann. Je nach Umfang kann das Praktikum auf weitere Solutionvalidatoren für andere Lösungsansätze, die leider auch andere Ausgabefiles erzeugen, ausgeweitet werden.

Grundsätzliche Kenntnis der Programmiersprache C++ wäre wünschenswert, da die Aufgaben in C++ zu erledigen sind (das bereits vorhandene Framework wurde ebenfalls in C++entwickelt).

Zuweisung von Funkfrequenzen für kabellose Mikrofone

Umfang
Bezahlte Diplomarbeit (EUR 2350,- Honorar bei erfolgreichem Abschluss)
Auskunft
Günther Raidl, Andreas Chwatal
Besonderheiten
Forschungsprojekt in Zusammenarbeit mit AKG Acoustics für reale Anwendung

Bei vielen Konzerten oder Live-Veranstaltungen kommen heute kabellose Mikrofone zum Einsatz. Bei der gleichzeitigen Verwendung mehrerer Funkmikrofone können jedoch gegenseitige Störsignale auftreten.

Der Hauptmechanismus gegenseitiger Störung ist dabei die so genannte Intermodulation, bei der z.B. bei zwei Übertragungsfrequenzen mehrere neue Störfrequenzen entstehen. Ziel ist es nun, für jedes Mikrofon eine bestimmte Sendefrequenz zu bestimmen, sodass diese nicht mit irgend einer daraus resultierenden Intermodulationsfrequenz zusammenfällt. Vorhandene Ansätze/Programme sind entweder hinsichtlich der Laufzeit oder der Lösungsqualität nicht zufriedenstellend.

Ziel der Diplomarbeit ist die Entwicklung und Implementierung vielversprechender heuristischer (und möglicherweise auch exakter) Algorithmen zur Lösung des Problems in C++. Spezielle Kenntnisse in der Elektronik bzw. Hochfrequenztechnik sind nicht erforderlich, Verständnis im Bereich der diskreten Optimierung von Vorteil. Bei erfolgreichem Abschluss wird ein Honorar von EUR 2350,- ausbezahlt. Die Betreuung der Diplomarbeit erfolgt gemeinsam mit der Forschungs u. Entwicklungsabteilung der Firma AKG Acoustics in Wien.

Interface für eine Push-Relabel Maximum Flow Implementierung

Umfang
Praktikum
Auskunft
Martin Gruber

Im Bereich der Netzwerkoptimierung haben sich Branch&Cut Algorithmen als exakte Lösungsverfahren bewährt und werden in unserer Forschungstätigkeit auch entsprechend eingesetzt. Als Subproblem muss in diesem Zusammenhang ein gerichteter maximaler Fluss (Directed Maximum Flow) in einem Graphen berechnet werden.

Für den Push-Relabel Maximum Flow Algorithmus existiert eine äußerst effiziente Implementierung von Cherkassky und Goldberg [PDF], die auch online verfügbar ist. Allerdings ist das Interface für unsere Bedürfnisse unzureichend: Zwar bleiben bei uns die Knoten des zugrundeliegenden Graphens konstant, aber die gerichteten Kanten können sich zwischen den zahlreichen Berechnungen, die innerhalb des Branch&Cut Algorithmus notwendig sind, immer wieder verändern, d.h. müssen zum Teil entfernt und später wieder neu aufgenommen werden. Diese notwendigen Manipulationen des Graphens werden aber von der Implementierung von Cherkassky und Goldberg zur Zeit nicht unterstützt.

Aufgabe in diesem Praktikum wäre es nun, ein entsprechendes, möglichst effizientes Interface in C++ zur bereits vorhandenen Push-Relabel Maximum Flow Implementierung zu erstellen, das das Löschen und Hinzufügen von gerichteten Kanten zur Verfügung stellt.

Nachrichtenübertragung in einem (Daten-)Netzwerk

Umfang
mehrere Diplomarbeiten (bzw. Praktika) möglich
Auskunft
Andreas Chwatal
Besonderheiten
Dieses Thema entstammt dem fakultätsinternen Forschungsschwerpunkt "Komplexe Systeme" und wird gemeinsam mit Mitarbeitern des Instituts für Softwaretechnik und interaktive Systeme betreut.

Das Senden einer Nachrichten zwischen Sender und Empfänger in einem kapazitätsbeschränkten Netzwerk kann mittels effizienter Algorithmen gelöst werden. Möchten allerdings mehrere Sender gleichzeitig an unterschiedliche Empfänger Nachrichten übermitteln, kann es zu Engpässen und ungewünschten Verzögerungen kommen. In diesem Fall ist eine Lösung gewünscht, die verschiedene Kriterien gleichzeitig (möglichst gut) erfüllt: Die maximale Übermittlungszeit sollte so wie die durch die Nachrichtenübertragung entstehenden Kosten möglichst gering gehalten werden. Gleichzeitig müssen die Bandbreitenbeschränkungen berücksichtigt werden.

Die konkrete Aufgabenstellung Ihrer Diplomarbeit würde darin bestehen neben einer genauen Literaturrecherche zu diesem und verwandten Problemstellungen Algorithmen zu entwickeln, die je nach gewählten Algorithmen kleinere, mittelgroße beziehungsweise größere Instanzen dieses Problem lösen. Prinzipiell gibt es zwei von einander unabhängige Arbeiten zur Auswahl, wobei sich die eine mehr auf exakte Verfahren und die andere eher auf heuristische Verfahren konzentrieren wird.

Exakte Verfahren </dt>
Es wäre interessant heurauszufinden, wie groß die Instanzen sein können, sodass diese noch exakt gelöst werden können. Hierfür benötigt man allerdings auch entsprechende leistungsfähige Verfahren, um eine aussagekräftige Feststellung tätigen zu können. Unter anderem klingen folgende Ansätze vielversprechend:

Ganzzahlige Lineare Programmierung
Hierbei geht es das Problem als ganzzahliges lineares Programm (ILP) zu formulieren und mit einem zur Verfügung stehenden ILP-Solver (CPLEX) zu lösen. Zusätzlich sollten je nach Formulierung Verfahren wie Cutgenerierung oder Spaltengenerierung angedacht werden.
Flussalgorithmen
Diese Art von Algorithmen haben sich bei vielen Netzwerkproblemen als effizient erwiesen. Es sollte daher eine auf die konkrete Problemstellung angepasste Flussformulierung entwickelt werden. Zur Lösung kann wiederum CPLEX herangezogen werden.

</dd>

Heuristische Methoden </dt>
Je nach Größe der Eingabeinstanzen kann es vorkommen, dass exakte Verfahren nur bedingt brauchbare Ergebnisse liefern. Vorallem wenn Rechenzeit kritisch ist, kann es hilfreich sein, auf heuristische Verfahren zurückzugreifen:

Konstruktionsheuristken
Mittels schnellen Greedy-Vorgangsweisen soll eine Lösung generiert werden, die als Startösung für weitere Verbesserungsheuristiken benutzt wird.
Lokale Suchmethoden
Um eine gegebene Ausgangslösung effizient zu verbessern, ist zunächst eine kluges Auswahl von Nachbarschaftsstrukturen erforderlich. Neben Standardnachbarschaften wie 2-opt sollen hier spezielle, auf das Problem zugeschnittene Nachbarschaftsstrukturen entwickelt werden. Um diese effizient zu durchsuchen, sind dann in weiterer Folge spezielle Algorithmen zu entwickeln.
Metaheuristiken
In den meisten Fällen ist die Lösungsqualität, die mittels einfacher Konstruktions- und Verbesserungsheuristiken erreicht wird, für den konkreten Anwendungsfall nicht ausreichend. Daher greift man oft auf Metaheuristiken zurück, mit deren Hilfe eine weitere Verbesserung der Ergebnisse erzielt werden kann. Neben Verfahren wie Variabler Nachbarschaftsuche und Tabusuche, die auf lokaler Suche basieren, können auch evolutionäre Algorithmen und andere „nature inspired algorithms“ wie Ameisensysteme vielversprechend sein.

</dd>

Knapsack Constrained Maximum Spanning Tree Problem

Umfang
mehrere Praktika bzw. Diplomarbeiten möglich
Auskunft
Sandro Pirkwieser

Das Knapsack Constrained Maximum Spanning Tree Problem (KCMST Problem) besteht darin für einen gegebenen Graphen mit Kantenprofiten und -gewichten einen profitmaximalen Spannbaum zu finden welcher eine ebenfalls gegebene Gewichtsbeschränkung einhält. Man kann sich vorstellen für ein Netzwerk mit Kantenkosten einen Spannbaum finden zu müssen während das festgelegte Gesamtbudget nicht überschritten wird.

Folgende Praktika bzw. Diplomarbeiten sind vergeben:

Einbettung von Lagrangescher Dekomposition in Branch-and-Bound</dt>

Bei der Lagrangeschen Dekomposition (LD) wird versucht das Problem in mehrere voneinander unabhängige Teilprobleme aufzusplitten die verlinkt werden, in diesem Fall das Spannbaum- und Rucksackproblem, um anschließend diesen Link zu relaxieren, also "aufzulockern". Eine bereits entwickelte LD ist in der Lage sehr gute, in vielen Fällen sogar optimale obere Schranken zu erlangen. Des Weiteren werden durch eine Heuristik zusätzlich im Zuge des Verfahrens auch untere Schranken, also gültige Lösungen erzeugt, wodurch oftmals bereits die beweisbar optimale Lösung gefunden werden kann. Das Praktikum setzt nun genau in den anderen Fällen an, wo keine Optimalität bewiesen werden kann. Die Idee ist nun die LD in einen Branch-and-Bound (B&B) Algorithmus einzubetten. Sie ersetzt damit die sonst übliche Linear Programming (LP) Relaxation um die benötigten Schranken zu generieren. Durch die sehr guten Schranken wird ein B&B Baum moderater Größe erwartet.

Im Zuge des Praktikums soll ein geeigneter B&B Algorithmus implementiert werden (es kann auf ILP Solver wie COIN BCP oder ILOG CPLEX zurückgegriffen werden) und die bestehende LD muss auf diesen Einsatz hin angepasst werden. Abschließend sind Vergleichstests zu machen. Das Praktikum ist in C++ zu absolvieren. </dd>

Optimierung einer Papierrollen-Lagerung

Umfang
Diplomarbeit oder Praktikum
Auskunft
Günther Raidl, Matthias Prandtstetter
Besonderheiten
Projekt für reale Anwendung, Erfolgshonorar
Fertigstellung
bis Ende Jänner

In einer Papier-Fabrik soll die Einlagerungsstrategie für produzierte Papierrollen optimiert werden. Die Papierrollen werden auf 105 Streifen verteilt gelagert, wobei bei jedem Streifen immer nur auf die vorderste Rolle, die zuletzt hinzugefügt wurde, direkt zugegriffen werden kann. Um eine weiter hinten gelagerte Rolle zu entnehmen sind die auf diesem Streifen davor stehenden Rollen zuvor auf andere Streifen umzulagern. D.h., ein Streifen ist mit einem Stapel (LIFO) vergleichbar.

Für jede Papierrolle ist ein voraussichtlicher Abholzeitpunkt bekannt, zu dem die Rolle ausgelagert wird. Ziel ist es, die einzulagernden Papierrollen so auf die Streifen aufzuteilen, sodass der voraussichtliche Arbeitsaufwand für notwendige Umlagerungen minimiert wird.

Für diese Aufgabenstellung ist ein heuristisches Lösungsverfahren zu entwerfen, in Java zu implementiert und mit realen Daten zu testen. Bei erfolgreichem Abschluss bis Jänner wird ein Erfolgshonorar ausbezahlt.

Complete Archive Genetic Algorithm: Ein genetischer Algorithmus wird um ein Lösungsarchiv erweitert

Umfang
Praktikum oder Diplomarbeit
Auskunft
Günther Raidl

Klassische genetische Algorithmen erzeugen und bewerten ein und dieselbe Kandidatenlösung im gesamten Optimierungsverlauf häufig mehrfach. Für Probleme, bei denen die Bewertung von Kandidatenlösungen aufwendig ist, ist das ein erheblicher Nachteil. Im Rahmen dieser Arbeit soll ein klassischer genetischer Algorithmus um eine auf einen Trie basierende Datenstruktur erweitert werden, in der besuchte Lösungen kompakt gemerkt werden. Wird dieselbe Kandidatenlösung im weiteren Verlauf nochmals erzeugt, so wird dies über den Trie erkannt und die Lösung soll in eine möglichst ähnliche, aber noch nicht bewertete Nachbarlösung modifiziert werden. Über den Trie ist es weiters möglich, bereits vollständig untersuchte Teilräume des gesamten Suchraums effizient zu erkennen und diese in Zukunft auszuschließen. Wir erwarten uns durch diese neue Idee erhebliche Performancesteigerungen für genetische Algorithmen zu unterschiedlichen Problemstellungen.

Das Verfahren soll im Rahmen eines Praktikums oder einer Diplomarbeit in C++ auf Basis einer existierenden Bibliothek für Metaheuristike (EALib) implementiert und auf zwei bis drei Benchmarkproblemen getestet werden.

Visualisierung verschiedener Algorithmen und Datenstrukturen

Umfang
Praktikum
Auskunft
Martin Gruber

In unseren Lehrveranstaltungen Ausgewählte Kapitel der Algorithmik 5 oder Effiziente Algorithmen präsentieren wir Algorithmen und Datenstrukturen aus den unterschiedlichsten Gebieten der Informatik, z.B. aus dem Bereich der Bioinformatk oder der effizienten Textsuche. Viele davon sind aufgrund ihrer Komplexität (z.B. Zusammenspiel mehrerer Indizes) mitunter schwer verständlich. Eine grafische Veranschaulichung der Abläufe bzw. des schrittweisen Aufbaus von komplexen Datenstrukturen wäre sowohl in den Vorlesungen als auch später für die Studenten bei der Vorbereitung auf die Prüfung hilfreich.

Aufgabe wäre es nun, eine oder mehrere Visualisierungen (abhängig vom Umfang) von Algorithmen und/oder Datenstrukturen - vorzugsweise in Java - zu implementieren, um diese dann bei der Lehre einsetzen zu können. Dabei kann - basierend auf den eigenen Vorlieben - aus einem relativ großen Fundus an Aufgabenstellungen gewählt werden.

Approximation von Papierschnippseln durch Polygone

Umfang
Praktikum
Auskunft
Matthias Prandtstetter

Im Bereich der Restauration zerstörten Papiers (kurz auch Puzzle-Problem genannt) werden Testdaten dadurch erzeugt, dass Papier (händisch) zerrissen wird und die entstehenden Schnippsel eingescannt werden. Unsere derzeitigen Ansätze beruhen allerdings darauf, dass die Schnippsel durch Polygone angenähert werden. Es existiert auch schon eine Implementierung eines solchen Polygon erzeugenden Algorithmus. Dieser bedarf jedoch einiger Verbesserungen - so werden spezielle Sonderfälle derzeit nicht abgefangen. Weiters sollte ein zweiter ähnlicher Ansatz implementiert werden, um dessen Performance mit dem aktuellen Algorithmus zu vergleichen. Auch die Auswirkungen auf die bereits existenten Verfahren sind dabei von großem Interesse.

Parallele Nachbarschaftsuche für das Car Sequencing Problem

Umfang
Praktikum oder Diplomarbeit
Auskunft
Matthias Prandtstetter

Beim Car Sequencing geht es darum, für eine Menge bestellter Fahrzeuge eine optimale Reihung für die sogenannte Bandauflage zu finden. Dabei sind einge Constraints, die von den einzelnen bei der Produktion zu durchlaufenden Arbeitsstationen definiert werden, zu beachten. Beispiele für diese Constraints wären, dass nur eine vorgegebene Anzahl von Fahrzeugen in einer Teilsequenz fixer Länge eine bestimmte Komponente wie zum Beispiel eine Klimaanlange erhalten dürfen, da die Einbauzeit für diese Komponente größer als die Taktzeit des Fließbandes ist. Weiters muss darauf geachtet werden, dass nur eine bestimmte Anzahl von aufeinander folgenden Fahrzeugen mit der selben Farbe gespritzt werden dürfen. Danach muss ein Farbwechsel auftreten. Allerdings versucht man die Anzahl der Farbwechsel zu minimieren.

Bei diesem Praktikum (bzw. Diplomarbeit) würde es darum gehen, ein schon existierendes Framework zum Lösen des Problem mittels Variabler Nachbarschaftssuche (VNS) derart zu erweitern, sodass die lokale Nachbarschaftsuche (auf mehreren Prozessoren) parallel ausgeführt werden kann. Neben dem Design und der Implemtierung der dafür benötigten Architektur besteht auch die Möglichkeit je nach Umfang der Arbeit zusätzliche Nachbarschaften zu entwickeln und zu implementieren.

Kombination von Metaheuristiken und einer Lagrange-Relaxierung für das durchmesserbeschränkte Spannbaumproblem

Umfang
Praktikum oder Diplomarbeit
Auskunft
Martin Gruber

Das Bounded Diameter Minimum Spanning Tree (BDMST) Problem kommt aus dem Bereich des Netzwerkdesigns, hat aber durchaus auch noch weitere Anwendungsgebiete, z.B. bei der Datenkomprimierung oder bei Distributed Mutual Exclusion Algorithmen.

Ziel ist es, einen minimalen Spannbaum in einem Graphen zu finden, wobei der Durchmesser, d.h. die maximale Anzahl an Kanten zwischen je zwei beliebigen Knoten, nach oben hin beschränkt ist. Obwohl man einen MST sehr einfach mit Hilfe der Algorithmen von Kruskal oder Prim bestimmen kann, macht das Hinzufügen der Durchmesserbeschränkung das Problem NP-schwer (ab einem Durchmesser von 4).

Wir haben in letzter Zeit unerschiedliche Verfahren zur Lösung dieses Problems entwickelt, darunter einige Metaheuristiken (Variable Neighborhood Search [VNS], Ant Colony Optimization [ACO], Evolutionary Algorithm [EA]) und im Zuge einer Diplomarbeit eine Lagrange-Relaxierung. Bei der Lagrange-Relaxierung werden schwer zu erfüllende Nebenbedingungen (in diesem Fall die Durchmesserbeschränkung) zunächst aus dem Modell entfernt, Verletzungen dieser Nebenbedingungen werden in der Folge aber durch entsprechende Terme in der Zielfunktion bestraft. Durch iterative Adaptierungen des Modells wird versucht, diese Strafterme möglichst auf Null zu bringen.

Ziel dieses Praktikums bzw. dieser Diplomarbeit wäre es nun, Kombinationen dieser Lagrange-Relaxierung mit den vorhandenen Metaheuristiken zu implementieren und zu testen, z.B. die Einbringung einer neuen Lösung aus der Lagrange-Relaxierung in die Population des EAs. Auch die Entwicklung einer Heuristik zur Reparatur ungültiger Lösungen, wie sie während der Lagrange-Relaxierung entstehen (Spannbäume, die die Durchmesserbeschränkung nicht vollständig einhalten), ist für eine Kombination der unterschiedlichen Algorithmen ein interessantes Thema.

Interessant ist in diesem Zusammenhang auch, dass es mit Hilfe der Lagrange-Relaxierung, die eine untere Schranke für das BDMST Problem berechnet, möglich ist, für die von den Metaheuristiken erzeugten Lösungen Aussagen über deren Güte zu machen bzw. vielleicht sogar – in einem optimistischen Szenario – die Optimalität einzelner Lösungen zu beweisen.

DNA-Methylierung: Erweiterung für Doppelstranganalyse

Umfang
Praktikum
Auskunft
Jennifer Hetzl

In der DNA ist nicht nur primäre Sequenzinformation, d.h. um welches Nukleotid ("A", "C", "G", oder "T") es sich handelt gespeichert, sondern es können auch übergeordnete Informationen im Molekül selbst codiert sein. Eines dieser Meta-tags ist DNA Methylierung, d.h. eine an "C"-Bausteine angehängte Methylgruppe (mC). CyMATE ist eine via ein Webinterface verfügbare Applikation zur quantitativen und qualitativen Analyse des Methylierungszustands molekularer Daten nach chemischer Umwandlung nicht-methylierter "C"s in "T"s.

Bisher ist es jedoch nur möglich, Einzelstränge zu vergleichen, d.h. entweder jeweils Daten des Vorwärts- ('F' im Bild) oder des Rückwärtsstrangs ('R') zu verarbeiten. Durch eine Erweiterung der Applikation sollen nun auch Doppelstranginformationen evaluiert werden. Vorwärts- und Rückwärtsstrang sollen verifiziert werden, und danach die für den Vorwärtsstrang bereits bestehende Analysemethode auf den Rückwärtsstrang angewendet werden. Die Auswertung der Korrelation von mC-tags aus beiden Strängen soll sowohl textuell als auch grafisch dargestellt werden.

Im Rahmen dieser Arbeit sollen die zur Lösung der Aufgabe notwendigen Anpassungen und Erweiterungen des CyMATE-Moduls vorgenommen werden. CyMATE ist in der Sprache Python implementiert und verwendet die Cairo Graphics Library zur Erzeugung von PDF-Dateien. Als Werkzeuge stehen SVN bzw. Trac zur Verfügung. Vorkenntnisse aus der Biologie/Bioinformatik sind nicht erforderlich, Interesse fuer bioinformatische Fragestellungen ist jedoch hilfreich.

Input-Datei für CyMATE - Beispiel

Unterstützende Tools zum Visualieren selbstentwickelter Algorithmen und Datenstrukturen

Umfang
Praktikum
Auskunft
Matthias Prandtstetter
Besonderheiten
Abschluss möglichst rasch geplant

Im Rahmen dieses Praktikums sollen Sie mit Rücksprache der Verantwortlichen der Lehrveranstaltung Algorithmen und Datenstrukturen 1 unterstützende Tools für ihre sich im zweiten Semester befindenden Kollegen entwickeln. Dabei handelt es sich primär um Visulaisierungen, sodass das Debuggen und Nachvollziehen der im Rahmen des Laborübungsteils selbstentwickelten Algorithmen vereinfacht wird. Mitunter sollen Sie aber auch das Format der Ausgabe dieser Algorithmen, die von Ihrem Visualisierungstool eingelesen werden muss, mitbestimmen.

Da diese LVA bereits Anfang März startet, ist ein möglichst schneller Abschluss dieses Praktikums wünschenswert, sodass die von Ihnen entwickelten Tools bereits dieses Semester ihren Einsatz finden könnnen.

Dynamische Programmierung mit "Optimal Policy Iteration" für Allokationsprobleme

Umfang
Praktikum oder Diplomarbeit
Auskunft
Günther Raidl, Betreuung gemeinsam mit Alfred Kalliauer, Verbund AG

In dieser Arbeit werden mehrdimensionale Allokationsprobleme (Zuweisungsaufgaben) betrachtet, wie sie beispielsweise in der Produktionsplanung oder Finanzwirtschaft auftreten. Dabei geht es darum, Güter vorgegebener Menge auf eine diskrete Anzahl von Zeitschritten in Bezug auf eine Zielfunktion bestmöglich aufzuteilen. "Güter" können beispielsweise in der Energiewirtschaft bei hydraulischen Speicherkraftwerken die gespeicherten Wassermengen sein, in der Finanzwirtschaft Optionen etc.

Derartige Problemstellungen können oft mit dynamischer Programmierung effizient gelöst werden. Werden etliche Güter gleichzeitig betrachtet (mehrdimensionales Problem), so steigt der Lösungsaufwand normalerweise dennoch dramatisch, da die Anzahl der für die dynamische Programmierung relevanten Zustände exponentiell mit der Anzahl der Güter wächst ("curse of dimensionality").

In dieser Arbeit soll eine durch "optimal policy iteration" erweiterte dynamische Programmierung implementiert und getestet werden. Hierbei wird von einem kleinen Zustandsraum ausgegangen und dieser dann sukzessive erweitert. In jedem Schritt wird die jeweils optimale Lösung effizient aus der Lösung des vorangegangenen, kleineren Problems berechnet.

Implementierung des Volume Algorithmus für eine Lagrangian Relaxation des Car Sequencing Problems

Umfang
Praktikum
Auskunft
Matthias Prandtstetter

Beim Car Sequencing geht es darum, für eine Menge bestellter Fahrzeuge eine optimale Reihung für die sogenannte Bandauflage zu finden. Dabei sind einge Constraints, die von den einzelnen bei der Produktion zu durchlaufenden Arbeitsstationen definiert werden, zu beachten. Beispiele für diese Constraints wären, dass nur eine vorgegebene Anzahl von Fahrzeugen in einer Teilsequenz fixer Länge eine bestimmte Komponente wie zum Beispiel eine Klimaanlange erhalten dürfen, da die Einbauzeit für diese Komponente größer als die Taktzeit des Fließbandes ist. Weiters muss darauf geachtet werden, dass nur eine bestimmte Anzahl von aufeinander folgenden Fahrzeugen mit der selben Farbe gespritzt werden dürfen. Danach muss ein Farbwechsel auftreten. Allerdings versucht man die Anzahl der Farbwechsel zu minimieren.

Da exakte Verfahren zum Lösen des CarSP in der Praxis nicht einsetzbar sind, versucht man mittels Metaheuristiken gute Lösungen in kurzer Rechenzeit zu erzeugen. Für Instanzen, von denen optimale Lösungen nicht bekannt sind, wäre es daher gut, wenn man zumindest gute Schranken, in denen sich die Optimallösung aufhält, kennt. Um diese Schranken zu berechnen wird oft ein Lagrangian Relaxierungsansatz gewählt.

Bei diesem Praktikum würde es darum gehen den Volume Algorithmus, der zum Berechnen von Lagrangian Relaxierungen verwendet wird, zu implementieren. Es kann teilweise auf ein schon fertiges Framework zum Lösen des Car Sequencing Problems zurück gegriffen werden und das letztendlich resultierende Programm sollte in dieses Framework eingebunden werden können.


Implementierung und Visualisierung eines Sweep Line Algorithmus für das Line Segment Intersection Problem

Umfang
Praktikum
Auskunft
Daniel Wagner

In einem aktuellen Forschungsprojekt ist es nötig, für eine gegebene Menge an Linien all jene Paare von Linien zu bestimmen, die sich im geometrischen Sinne schneiden. Ein naiver Ansatz, der allerdings sehr ineffizient ist, testet alle möglichen Paare darauf ob sich sich schneiden. Es gibt allerdings auch effizientere Algorithmen die sich des Sweep Line Prinzips bedienen, welche wesentlich schneller sind.

Ziel des Praktikums ist es, einen solchen Sweep Line Ansatz für das beschriebene Problem zu implementieren. Weiters soll für den Einsatz in der Lehre auch eine Visualisierung des Algorithmus umgesetzt werden. Diese soll auf graphisch anschauliche Weise das Funktionsprinzip des Algorithmus darstellen.

Algorithm Deception in Image Processing

Umfang
Diplomarbeit
Auskunft
Prof. Raidl
Besonderheit
Dieses Projekt wird gemeinsam mit dem Berliner Fraunhofer Institut für Produktionsanlagen und Konstruktionstechnik (IPK) durchgeführt bzw. betreut.

The famous No-Free-Lunch theorems for search and optimization state the impossibility to prefer one algorithm for the other in case there is no other knowledge about the optimization problem. It has not much been considered so far that there is another implication of these theorems: the existence of universal algorithm deception. For any algorithm and performance measure, there can be a problem specified where the algorithm produces the worst performance that is possible.

The goal of the thesis is to study such a deception of algorithms in the context of image processing algorithms. Instead of new algorithms, procedures should be developped that are able to deceive common pattern recognition procedures by appropriate image manipulations. To name two such scenarios: given two images A and B, and a histogram (grayvalue frequencies, co-occurrence matrix) of A, modify B in a manner that it remains percetually similar to B, but has the same histogram as A. Or: given an image A and an image operator O, devise an image B that is completely different from A but has similar result to operation O than A. Relaxation procedures are one candidate for such deceptive operations.

The achievements from such a study can be seen in two regards: the higher effort needed to deceive an image processing feature also demonstrates its better suitability for processing images. But it is also of interest for devlopping new techniques for information hiding and digital watermarking.


Lagrange Dekomposition für das durchmesserbeschränkte Spannbaum Problem

Umfang
Praktikum oder Diplomarbeit
Auskunft
Martin Gruber oder Prof. Raidl

Zum oben genannten durchmesserbeschränkten Spannbaum Problem soll weiters ein Ansatz über Lagrange Dekomposition entwickelt und implementiert werden. Diese Methode unterteilt das Problem in zwei leichtere, aber von einander abhängige Probleme und löst diese iterativ. Diese Subprobleme sind hier im Wesentlichen die Berechnung eines unbeschränkten, gerichteten minimalen Spannbaums und ein spezielles Zuweisungsproblem.

Die Lagrange Dekomposition liefert einerseits eine untere Schranke für die optimale Lösung, andererseits durch entsprechende Erweiterung mit Rundungsmethoden oder greedy Algorithmen konkrete Näherungslösungen. Somit sollten insgesamt gute heuristische Lösungen inklusive Gütegarantien gefunden werden.

Konstruktionsheuristik für das durchmesserbeschränkte Spannbaum Problem

Umfang
Praktikum oder Diplomarbeit
Auskunft
Martin Gruber

Das Bounded Diameter Minimum Spanning Tree (BDMST) Problem kommt aus dem Bereich des Netzwerkdesigns, hat aber durchaus auch noch weitere Anwendungsgebiete, z.B. bei der Datenkomprimierung oder bei Distributed Mutual Exclusion Algorithmen.

Ziel ist es, einen minimalen Spannbaum in einem Graphen zu finden, wobei der Durchmesser, d.h. die maximale Anzahl an Kanten zwischen je zwei beliebigen Knoten, nach oben hin beschränkt ist. Obwohl man einen MST sehr einfach mit Hilfe der Algorithmen von Kruskal oder Prim bestimmen kann, macht das Hinzufügen der Durchmesserbeschränkung das Problem NP-schwer (ab einem Durchmesser von 4).

Wir haben in letzter Zeit unerschiedliche Verfahren zur Lösung dieses Problems entwickelt, darunter - neben einigen Metaheuristiken - einen Integer Linear Programming (ILP) Ansatz, um das BDMST-Problem beweisbar optimal zu lösen. Das Problem ist allerdings so schwer, dass exakte Algorithmen nur auf relativ kleine Graphen angewendet werden können: bei einem Zeitlimit von wenigen Minuten nur auf vollständige Graphen mit rund 25-30 Knoten.

Wir haben nun folgende Idee für eine Konstruktionsheuristik, um einen BDMST auf Graphen mit bis zu 1000 Knoten zu erzeugen: Man fasst einzelne Knoten solange zu Clustern zusammen, bis das BDMST-Problem auf den Clustern (jeder Cluster wird durch einen einzelnen Knoten repräsentiert) mit einem exakten Algorithmus (relativ) einfach zu lösen ist. Danach wird jeder einzelne CLuster selbst als Subproblem betrachtet, in dem wieder die einzelnen Knoten solange zu Clustern zusammengefasst werden, bis das Problem einfach exakt lösbar ist. Dieses Verfahren wird rekursiv solange fortgesetzt, bis wirklich jeder Knoten des Originalgraphen in den BDMST eingebunden ist. Natürlich ist darauf zu achten, dass das Endergebnis die Durchmesserbeschränkung nicht verletzt.

Aufgabe in diesem Praktikum wäre es nun, verschiedene Cluster-Algorithmen zu recherchieren und davon einen oder mehrere geeignete (je nach Aufwand) zu implementieren, um sie mit dem von uns bereits entwickelten ILP zur exakten Lösung des BDMST-Problems zu einer Konstruktionsheuristik zu kombinieren.

Evolutionary Optimization for Super-Resolution Algorithms

Umfang
Diplomarbeit
Auskunft
Prof. Raidl
Besonderheit
Dieses Projekt wird gemeinsam mit dem Berliner Fraunhofer Institut für Produktionsanlagen und Konstruktionstechnik (IPK) durchgeführt bzw. betreut.

Super-Resolution algorithms are a rather new family of approaches to increase image resolution of low-resolution image acquisition devices (like cameras in mobiles) by processing a set of images taken by the low-resolution device in a sequence. As in case of a mobile phones, the small tremor of the hand result in slight shifts of the camera perspective that can be used to estimate intensities in the sub-pixel range (as the camera is moved in a continuous domain, but the image is acquired in the grid of the CCD chip). Present realizations of super-resolution algorithms make heavy use of image modelling aspects, as the underlying optimization problem, to find the best fitting transformation from one image to the next, is highly variate and complex.

The goal of the thesis is to employ evolutionary computation to achieve the best matching transformations between the images and thus allowing for the derivation of an image in higher resolution (double resolution). Evolutionary computation is suggested as it is working on a heuristic basis, thus not explicitely needing image generation models, the value of which in practice is questionable anyway.

The achievements is to support the development of mobile security applications, where the low resolution of devices often is a strong restriction.


Wegsuche in einem geografischen Informationssystem

Umfang
Diplomarbeit
Auskunft
Prof. Raidl
Besonderheit
Dies ist ein Anwendungsprojekt der Firma SynerGIS mit internationaler Bedeutung. Für die Durchführung ist eine Anstellung vorgesehen. Der Arbeitsbereich Algorithmen und Datenstrukturen der TU Wien wird die wissenschaftliche Betreuung übernehmen.
Beginn
ehestmöglich!
Projektendtermin
voraussichtlich Ende 2006; Option der Verlängerung des Dienstverhältnisses

Gegeben sind eine Liste von fehlerbehafteten Punktkoordinaten (GPS Messungen) und deren Zeitpunkte der Aufnahme. Die Aufgabe besteht darin, diese Positionen auf ein Referenzliniennetz zu korrigieren. Zwischen den auf das Liniennetz korrigierten Punkten ist zuerst die kürzeste Verbindung zu ermitteln, die alle Punkte in der korrekten Reihenfolge enthält. Im zweiten Schritt ist eine Liste aller Liniensegmente zu finden, die die kürzeste Verbindung darstellt. Durch die fehlerbehafteten GPS Messungen kann es sein, dass die korrigierten Positionen der Punkte nicht eindeutig sind (z.B. wenn sich zwei Linien kreuzen kann der Punkt entweder auf einer oder auf der anderen Linie sein). Die Auflösung dieser Mehrdeutigkeiten ist ebenfalls durchzuführen.

Die zu lösenden Probleminstanzen besitzen teilweise bis zu 1.000.000 Liniensegmente. Die Implementierung muss höchste Performance aufweisen, weshalb eine Parallelisierung des Berechnungsprozesses auf einer Blade-Farm erfolgen soll. Die Anzahl der Punkte die einen einzelnen Pfad definieren ist unterschiedlich (50 - 1000 Punkte sollen möglich sein). Wir gehen von einer Prototypsystemgröße von 5 CPUs aus. Der Endausbau kann dann bis zu 500 CPUs beinhalten.

Die Anwendung wird für ein internationales Pilotprojekt verwendet, welches bei Erfolg in den kommenden Jahren international eingesetzt werden soll. Aus diesem Grunde ist SynerGIS daran interessiert den/die DiplomandIn zumindest für die Zeit der Diplomarbeit fix anzustellen (Vollzeit). Bei Erfolg des Projektes besteht die Option der Verlängerung des Dienstverhältnis um einerseits diese Applikation weiter zu betreuen bzw. weiter zu optimieren oder in anderen Entwicklungsprojekten mitzuarbeiten.

Der Algorithmus wird höchstwahrscheinlich mit Hilfe von Microsoft .NET zu implementieren sein. Eine entsprechende Erfahrung hiermit wäre daher erwünscht, ist jedoch keine unbedingte Voraussetzung.

Die Aufgabe der/des Diplomand/in/en besteht darin in Zusammenarbeit mit den GIS Entwicklern der Firma SynerGIS und unter Betreuung von Prof. Raidl der Technischen Universität Wien die räumlichen Analysen in Richtung Parallelisierung und Performance zu optimieren. SynerGIS bringt das KnowHow bei den räumlichen Analysen und benötigt das KnowHow der Optimierung des Prozesses in Bezug auf Geschwindigkeit und Systemressourcen.

Unterstützung in der Einarbeitungsphase in den Bereich der geopraphischen Informationssysteme und den benötigten Werkzeugen wird von der Firma SynerGIS selbstverständlich im größtmöglichen Ausmaß gewährt.


Combinatorial Optimization for the Compression of Biometric Templates

Umfang
Diplomarbeit
Auskunft
Prof. Raidl
Besonderheit
Dieses Projekt wird gemeinsam mit dem Berliner Fraunhofer Institut für Produktionsanlagen und Konstruktionstechnik (IPK) durchgeführt bzw. betreut.

Biometric templates are representing a biometric pattern for the purpose of verification. In a biometric application, the template of a biometric reference pattern has to be available, which often corresponds to a storage of the template (e.g. on an RFID chip, in a 2D-Barcode, or data base). As there are technical limitations on storage capacity, esp. still today in the context of a mobile application, there is a need for template compression. The compression, which can be lossy as well, has to fulfill various objectives: besides the small data size, also there should be smallest loss in the verification error rates after decompressing and using the pattern, and robustness to a small amount of errors in the memory read-out procedure. Exemplified by the minutia locations and directions that are commonly used for fingerprint templates, the work should consider new approaches to the compressed representation of such a template by means of graph theory and its corresponding combinatorial optimization problems.

The goal of the thesis is the study of graph-based approaches in fingerprint minutia representation. The template locations are represented as a graph, and an approach could be to search the minimal spanning tree of this graph to yield a smaller represenation of the same graph, or to split the set of locations into subsets that can be represented by the smallest traveling salespersons' route. Since a biometric template is never precisely the same if taken twice from the same person, the smaller representation does not need to be exact. The imprecision has to be balanced against verification errors and read-out errors.


Graph-based Simulation Study for the Tearing of Paper

Umfang
Diplomarbeit
Auskunft
Prof. Raidl
Besonderheit
Dieses Projekt wird gemeinsam mit dem Berliner Fraunhofer Institut für Produktionsanlagen und Konstruktionstechnik (IPK) durchgeführt bzw. betreut.

For the reconstruction of torn documents from scanned images of the pieces, knowledge about the tearing process is necessary. The step-by-step tearing of papers can be represented by graphical structures like binary trees, which are directly linked to properties of the paper pieces (distribution of the number of corners, distribution of the border parts that are paper edges asf.). For matching the features of a real set of torn paper pieces to the production process that generated them, simulations can be used, since the knowledge about mathematical properties here is rather sparse.

The goal of the thesis is to devise simulation methods for a uniformly-distributed generation of graphical structures, which model the paper tearing process and help to derive statistical properties.

The achievment is to support the paper piece feature based reconstruction.


Lösungsarchiv für Generalisierte Netzwerkdesign Probleme

Umfang
Diplomarbeit oder Praktikum
Auskunft
Bin Hu

Mittels Lösungsarchiven lassen sich bereits betrachtete Lösungen eines Optimierungsproblem erkennen und effizient in neue umwandeln. Somit kann z.B. ein evolutionärer Algorithmus in der gleichen Zeit mehr neue Lösungen untersuchen. Für das Generalized Minimum Spanning Tree Problem konnte dieses Konzept bereits erfolgreich eingesetzt werden. Neben Erweitereungsmöglickkeiten und alternative Ansätze gibt es verwandte oder ähnliche Probleme, auf denen dieses Konzept angewandt werden können:

  • Generalisiertes Traveling Salesman Problem
  • Generalisiertes Vertex Biconnected Network Problem
  • Optimal Communication Spanning Tree Problem
  • usw.

Ziel der Arbeit ist der Entwurf bzw. die Umsetzung solcher Lösungsarchiven. Die Performanz soll mittels ausführlichen Tests evaluiert werden.


Genetischer Algorithmus für das Generalized Traveling Salesman Problem

Umfang
Praktikum
Auskunft
Bin Hu

Die generalisierte Version des klassischen Traveling Salesman Problems operiert auf Graphen, deren Knoten in Clustern partitioniert sind. Das Ziel besteht darin, einen Subgraphen zu finden, der genau einen Knoten aus jedem Cluster enthält und eine Rundreise minimaler Länge darstellt.

Ein möglicher Ansatz besteht darin, das Problem mittels einem Genetischen Algorithmus zu lösen, der die Individuen mittels Random-Keys codiert. Nach Operationen wie z.B. Initialisierung, Crossover, etc. werden die Lösungen mittels Lokaler Suche verbessert. Ein Populationsmanagement System verhindert ausserdem, dass mehrere Individuen mit gleichen oder zu ähnlichen Genen in einer Population enthalten sind, und garantiert dadurch die Diversität.

Das Ziel des Praktikum besteht darin, diesen Genetischen Algorithmus zu implementieren und mit Benchmark-Instanzen zu testen.


Railway Treveling Salesman Problem

Umfang
Praktikum oder Diplomarbeit
Auskunft
Bin Hu

Wir betrachten das Railway Treveling Salesman Problem, bei dem ein Kaufmann über ein Bahnnetz eine Reihe von Städte besuchen muss. Start- und Zielort sind dabei identisch. In jeder Stadt muss er eine gewisse Zeit verweilen, um sein Geschäft abzuwickeln. Weiteres muss er den Fahrplan in den jeweiligen Bahnhöfen beachten, um seine Rundsreise zu planen. Ziel ist es, den Zeitverbrauch zu minimieren.

Dieses praxisorientierte Problem hat eine große Ähnlichkeit zum Generalized Traveling Salesman Problem (GTSP). Man kann es entweder indirekt über eine Transformation auf das GTSP lösen, oder direkt mittels gängige Metaheuristiken oder exakten Lösungsverfahren bearbeiten. Ziel des Praktikums ist, sich mit diesem Problem auseinanderzusetzen und den einen oder anderen Ansatz zu verfolgen.


Genetischer Algorithmus für das Least Generalized Minimum Spanning Tree Problem

Umfang
Praktikum
Auskunft
Bin Hu

Wir betrachten hier das Least Generalized Minimum Spanning Tree (L-GMST) Problem: Die Knoten eines Graphen sind in Clustern partitioniert und das Ziel besteht darin, einen kostenminimalen Spannbaum zu finden, der mindestens einen Knoten aus jedem Cluster enthält.

Viele Genetische Algorithmen haben den Nachteil, dass der Crossover Operator stark zufallsbasiert arbeitet und daher die Erzeugung von schlechten Sprösslingen trotz guter Elternlösungen schwer vermeidbar ist. Wir möchten eine exakte Crossover Methode für das L-GMST Problem entwickeln, die aus zwei (oder mehr) Lösungen einen lokal optimalen Nachfolger generiert. Dieses Ziel erreichen wir, indem wir die Elternlösungen übereinander legen und einen optimalen Spannbaum auf diesem Teilgraph mittels einer MST-Heuristik und/oder Integer Programming berechnen.


Dekompositionsalgorithmus für das Least Generalized Minimum Spanning Tree Problem

Umfang
Praktikum
Auskunft
Bin Hu

Für das exakte Generalized Minimum Spanning Tree Problem, bei dem pro Cluster ein Knoten verbunden wird, existiert ein effizienter Dekompositionsalgorithmus: Er geht von einem globalen Spannbaum aus (wie die Cluster verbunden sind) und berechnet mittels dynamischer Programmierung die optimalen Knoten, die aus jedem Cluster verbunden werden müssen, damit der Spannbaum kostenminimal ist.

Für das Least Generalized Minimum Spanning Tree Problem, wo mehrere Knoten pro Cluster verbunden werden können, ist noch kein solcher Dekompositionsalgorithmus bekannt. Die Schwierigkeit liegt in der erhöhten Rechenaufwand, denn wenn aus einem Cluster zwei Knoten verbunden werden, müssen all zweier-Kombinationen getestet werden, usw. Die Aufgabe wäre, den Dekompositionsalgorithmus für den Least-Fall zu adaptieren.

Genetischer Algorithmus mit fortgeschrittenem Crossover Operator für das Generalized Minimum Edge Biconnected Network Problem

Umfang
Praktikum oder Diplomarbeit
Auskunft
Bin Hu

Gegeben sei ein Graph, dessen Knoten in Clustern partitioniert sind. Das Ziel besteht darin, einen möglichst kostengünstigen Subgraphen zu finden, der genau einen Knoten aus jedem Cluster enthält und kanten-zweizusammenhängend ist.

Viele Genetische Algorithmen haben den Nachteil, dass der Crossover Operator stark zufallsbasiert arbeitet und daher die Erzeugung von schlechten Sprösslingen trotz guter Elternlösungen schwer vermeidbar ist. Wir möchten eine fortgeschrittene Crossover Methode für das GMEBCN Problem entwickeln, die aus zwei (oder mehr) Lösungen einen Nachfolger generiert, der möglichst gut ist. Dieses Ziel erreichen wir, indem wir die Elternlösungen übereinander legen und einen Subgraphen auf diesem Teilgraph mittels Heuristik und/oder Integer Programming berechnen.

Das Ziel des Praktikum besteht darin, diesen Genetischen Algorithmus zu implementieren bzw. in ein Framework für Metaheuristiken (EALIB) zu integrieren und mit Benchmark-Instanzen zu testen.

Branch-and-Cut Verfahren für das Least Generalized Minimum Spanning Tree Problem

Umfang
Praktikum oder Diplomarbeit
Auskunft
Bin Hu

Wir betrachten hier das Least Generalized Minimum Spanning Tree (L-GMST) Problem: Die Knoten eines Graphen sind in Clustern partitioniert und das Ziel besteht darin, einen kostenminimalen Spannbaum zu finden, der mindestens einen Knoten aus jedem Cluster enthält.

Branch-and-Cut ist ein gängiges Verfahren, um kombinatorische Optimierungsprobleme exakt zu lösen. Basierend auf Integer Linear Programming Formulierungen werden die Probleme vorerst nur mit einer Teilmenge der Restriktionen gelöst, dann kommen anhand der verletzten Nebenbedingungen nach und nach Cuts hinzu, um die Lösung gültig zu machen. Wenn keine weiteren verletzten Nebenbedingungen gefunden werden können, wird das Problem nach dem Branch-and-Bound Prinzip aufgeteilt.

Das Ziel der Arbeit besteht darin, eine "Directed Cut" Formulierung für das L-GMST Problem zu programmieren und zu testen. Danach sollen anhand typischer Eigenschaften von Lösungen weitere Cuts ausprobiert werden, die den Branch-and-Cut Prozess beschleunigen könnten.

Interaktive Optimierung: Generalized Minimum Spanning Tree

Umfang
Praktikum
Auskunft
Bin Hu

Mittels Human Guided Search kann der Benutzer beim Optimierungsprozess mit seinem Wissen eingreifen und den Suchvorgang in vielversprechende Richtungen leiten, Teilbereiche manuell optimieren, usw. Wichtige voraussetzung dafür ist eine optisch ansprechende Visualisierung und eine intuitive Bedienung.

Ziel der Arbeit ist die Einbettung des Generalized Minimum Spanning Tree Problems in dieses Framework. Hierfür müssen Schnittstellen implementiert, Visualisierung gestaltet und gegebenenfalls Bedienelemente erweitert werden. Im Framework selbst ist ein leistungsfähiger Tabu-Search Algorithmus implementiert, somit muss lediglich die Suchstrategie (in form von Nachbarschaftsstrukturen) entworfen werden, aber keine komplette Metaheuristik.

Heuristiken für ein Survivable Network Design Problem

Umfang
Praktikum oder Diplomarbeit
Auskunft
Daniel Wagner

Beim Survivable Network Design geht es darum ausfallssichere Netzwerke zu planen. In unserer speziellen Variante für das Projekt NETQUEST sind zusätzlich noch einige reale Randbedingungen zu berücksichtigen.

Es existieren verschiedene heuristische Ansätze für änliche Probleme, wie z.B. Augmentierung.

Das Ziel des Praktikum besteht darin, verschiedene Heuristiken auf ihre Verwendbarkeit hin zu untersuchen und dann eine oder mehrere geeignete auch zu implementieren. Die Resultate sollen dann in einem bereits in Entwicklung befindlichen ILP als primale Heuristiken zum Einsatz kommen.


Entwicklung eines Visualisierungs/Analyse Tools für Evolutionäre Algorithmen

Umfang
Praktikum oder Diplomarbeit
Auskunft
Andreas Chwatal

Bei der Entwicklung/Feinabstimmung von Evolutionären Algorithmen (EAs) möchte man oftmals bestimmte Kenngrössen der Population, Extremwerte verschiedener Variablen oder Parameter berechnen, bzw. diese grafisch darstellen. Ziel diese Praktikums wäre die Implementierung eines derartigen Tools in Java. Da dieses Tool für eine möglichst große Bandbreite von EAs (oder auch anderen Metaheuristiken) einsetzbar sein soll, sind Flexibilität und Konfigurierbarkeit von zentraler Bedeutung. Insbesondere erscheint es auch sinnvoll, Elemente bestehender Statistiktools (z.B.: R) flexibel integrieren zu können. Der Implementierung vorrangehend sollen gemeinsam Konzepte entworfen und deren Umsetzbarkeit untersucht werden.

Archiv noch älterer Themen

Siehe hier.

Views
Personal tools