Department Mathematik
print


Navigationspfad


Inhaltsbereich

Forschungsgruppe TQA


Kombinatorische Optimierung

Im Rahmen der Kombinatorischen Optimierung werden in der Forschungsgruppe klassische Themen wie Knapsack Problem, Travelling Salesman Problem, Cutting Stock Problem, Scheduling Problem und viele weitere Optimierungsprobleme studiert mit dem Ziel, Algorithmen zu finden, die in sehr kurzer Zeit Lösungen errechnen, die für die Praxis gut genug sind. Dabei sind wir bestrebt, die jeweilige Laufzeit praxisorientiert vorauszusagen. Hier gilt es neue Wege bei der Evaluierung von Algorithmen zu gehen.

Für die Praxis kann es auch sinnvoll sein, mehrere Algorithmen bereitzustellen, und eine Entscheidungszentrale zu entwickeln, die zu jeder vorgegebenen Instanz den Algorithmus auswählt, der am besten geeignet ist in dem Sinne, dass er schnell eine gute Lösung errechnet. Es geht also um eine Optimierung der Optimierungsalgorithmen in Bezug zu einer Instanz. Die in diesem Rahmen auftretenden Fragen sind schwer, vor allem wenn sie an konkreten Aufgaben gemessen werden, die sichtbare Verbesserungen liefern sollen. Wir verfolgen viele unterschiedliche Ansätze, um mit diesen Fragen umzugehen. Erste Resultate haben wir mit den Methoden der Künstlichen Intelligenz und des maschinellem Lernens erzielt.

Ein Schwerpunkt in der Arbeit der Forschungsgruppe ist die Untersuchung von komplexen Optimierungsproblemen, bei denen viele der oben genannten Probleme zugleich auftreten und in einer Abhängigkeit zueinander stehen, die bei einer Lösung zu berücksichtigen ist. Es gilt also Interaktionen zwischen Algorithmen bzw. zusammengesetzte Optimierungsaufgaben zu modellieren und mit einem Masteralgorithmus zu steuern oder auf andere Weise eine optimale Lösung des Gesamtproblems zu finden.

Die in den beiden vorangehenden Absätzen beschriebenen Probleme lassen sich mit Funktionalen Agentennetzwerken untersuchen.

Einige unserer favorisierten Forschungsthemen sind auf den folgenden Seiten detaillierter beschrieben: