AG Optimierung


Unsere Forschungsgebiete

Unsere Arbeitsgruppe arbeitet unter anderem in der Angewandten Diskreten Mathematik, dem Operations Research und der Mathematischen Optimierung. Neben dem theoretischen Fokus basiert unsere Forschung meistens auf anwendungsbezogenen Problemstellungen aus dem realen Leben und ist eng mit der Informatik und der Ingenieurwissenschaft verknüpft. Unsere Methoden umfassen unter anderem:

  • Ganzzahlige und Kombinatorische Optimierung
  • Netzwerkflüsse und Graphentheorie
  • Multikriterielle Optimierung
  • Algorithmische Spieltheorie
  • Online-Optimierung
  • Scheduling und Standortplanung

Was ist Optimierung?

Diskrete Optimierung

Die diskrete Optimierung ist ein Teilgebiet der angewandten, diskreten Mathematik. Innerhalb der diskreten Optimierung unterscheiden wir kombinatorische Optimierungsprobleme sowie (gemischt) ganzzahlige (lineare) Optimierungsprobleme.


Kombinatorische Optimierung analysiert Struktureigenschaften einer abzählbaren Menge von Elementen und nutzt diese bestmöglich um Zielfunktionen über dieser Menge zu maximieren oder minimieren. Beispiele für die diskrete Optimierungsprobleme, die wir erforschen sind Schedulingprobleme, Rucksackprobleme, Schnittprobleme in Graphen oder etwa Matchings. Wir beschäftigen uns außerdem mit Varianten klassischer Formulierungen wie z.B. verallgemeinerten Bottlenck-Zielfunktionen oder mehreren, sich widersprechenden Zielfunktionen. Sehr häufig sind die von uns betrachteten Probleme schwer und wir untersuchen daher — neben exakten Lösungsverfahren - auch Approximationen.


In der ganzzahligen Optimierung suchen wir nach ganzzahligen Lösungen in einem (hochdimensionalen) polyedrischen Gebiet, die eine gegebene lineare Zielfunktion maximieren bzw. minimieren. Ganzzahlige Modelle tauchen in sehr untesrchiedlichen Anwendungen auf. Im Speziellen beschäftigen wir uns z.B. mit der Frage, wie in der digitalen Kommunikation das Maximum-Likelihood Dekodierproblem durch Methoden der ganzzahligen Optimierung gelöst werden kann. Damit liefern wir Referenzergebnisse für die Entwicklung von heuristischen Verfahren, wie sie z.B. gegenwärtig im Mobilfunk eingesetzt werden.

Graphen und Netzwerke

Mathematik beschäftigt sich mit abstrakten Strukturen und eine solche Struktur, die wir häufig betrachten sind sogenannte Graphen. In der einfachsten Form besteht ein mathematischer Graph aus einer Menge von Objekten (Knoten) und Verbindungen dazwischen (Kanten). Mithilfe von Graphen modellieren wir im Rahmen von Anwendungen dann z.B. Straßennetze, elektrische Schaltungen oder soziale Netzwerke. Reichert man mathematische Graphen mit weiteren Daten wie z.B. den Eigenschaften von Kanten (Längen, Kosten, Kapazitäten, …) an, so spricht man auch tatsächlich von mathematischen Netzwerken.


Über diese Strukturen lösen wir eine ganze Reihe von unterschiedlichen Optimierungsproblemen aus den Disziplinen der Standortplanung, der Netzwerkflüsse, der digitalen Kommunikation oder etwa des Supply Chain Managements. Konkret beschäftigen wir uns gegenwärtig unter anderem mit Vereinfachung von Tanner-Graphen, mit Edge Cover Problemen, mit dynamische Netzwerkflussproblemen oder etwa mit Resultaten für Graphen mit beschränkter Baumweite.


Neben der strukturmathematischen Analyse und der komplexitätstheoretischen Klassifikation von graphentheoretischen bzw. netzwerkbasierten Optimierungsproblemen ist ein weiterer wichtiger Bestandteil unserer Arbeit der Entwurf und die Implementierung von effizienten Algorithmen. Je nach Problemklasse streben wir nach exakten bzw. approximativen Algorithmen bzw. Schemata mit möglichst geringen (Worst-Case-)Laufzeiten. Nicht selten implementieren wir diese Algorithmen und lösen damit tatsächlich reale Problemstellungen.

Multikriterielle Optimierung

Beim Modellieren von realen Problemstellungen ist es oft notwendig mehrere gegenläufige Zielfunktionen zu optimieren, so auch bei einfachen Problemen wie dem Autokauf: Im Normalfall kommt es nicht vor, dass das günstigste Auto auch die beste Motorleistung hat. Daher muss ein Zielkonflikt gelöst und eine Kompromisslösung gefunden werden. Die multikriterielle Optimierung (oder Vektoroptimierung oder Pareto Optimierung) befasst sich mit dem Lösen von Problemen mit mehreren Zielfunktionen. Da normalerweise nicht eine Lösung gleichzeitig für alle Zielfunktionen optimal ist, werden mehrere Trade-Off-Lösungen, sogenannte Pareto optimalen Lösungen, berechnet.

Die multikriterielle Optimierung besitzt mannigfaltige Anwendungsgebiete wie zum Beispiel Produktionsplanung, Portfoliomanagement, Controlling, Prozessoptimierung, Standortplanung, zivile Sicherheit und vieles mehr. Daher ist dieses Forschungsgebiet nicht nur für Mathematiker sondern auch für Forscher aus den Wirtschaftswissenschaften und der Informatik interessant. Dadurch entstehen verschiedene Herangehensweisen: Das Finden aller Pareto optimalen Lösungen, das Finden mithilfe einer Präferenzfunktion oder mithilfe eines Entscheiders, der interaktiv am Lösungsprozess teilnimmt.  

Da die Forschung in diesem Gebiet noch am Anfang steht, ist es unser Ziel, die Forschung in der multikriteriellen Optimierung sowohl von einem theoretischen als auch von einem praktischen Standpunkt mithilfe von Grundlagenforschung und realen Problemen voranzutreiben.

Anwendungen

Unsere theoretischen Arbeiten im Bereich der Optimierung werden oft durch Anwendungen aus sehr unterschiedlichen Bereichen motiviert. Dazu gehören aktuell z.B. Fragen der strategisch günstigen räumlichen Positionierung in der Notfallrettung  und Optimierung der ambulanten medizinischen Versorgung sowie viele Anwendungen aus der Verkehrsplanung wie beispielsweise die Routenplanung in Schienennetzwerken, die optimale Erstellung von Linien-, Fahr- und Umlaufplänen im öffentlichen Personenverkehr oder das Finden möglichst guter Tarifsysteme. Einige Anwendungen in der Vergangenheit waren die Planung von Demonstrationen und Protestmärschen, die Optimierung von Hausdämmungen, die Erstellung von Schichtplänen in Krankenhäusern und die Unterstützung von großflächigen Evakuierungen. Interessanterweise können viele Herausforderungen aus diesen so unterschiedlichen Anwendungsdomänen auf verwandte mathematische Fragestellungen zurückgeführt werden. Besondere Freude bereiten uns neue Herausforderungen und natürlich stehen wir gerne als Ansprechpartner bei Problemen aus Technik und Wirtschaft zur Verfügung.


Anwendungen motivieren uns besonders, denn im Rahmen von realen Fragestellungen erfährt man unmittelbar den Nutzen von angewandter Mathematik. Diese Motivation geben wir gerne auch an Studierende weiter, indem wir sie frühzeitig in Praxisprojekte einbinden und z.B. Praktika, Hiwi-Tätigkeiten und Abschlussarbeiten im Rahmen von anwendungsorientierten Projekten vergeben. Außerdem eignen sich Anwendungen natürlich auch, um Schülerinnen und Schülern sowie Lehrkräften die Bedeutung moderner Mathematik zu vermitteln — auch dies ist eine Aufgabe, der wir in unterschiedlichen Formen gerne nachkommen.

Zum Seitenanfang