FAKULTÄT FÜR

MATHEMATIK

Das Projekt wird von den genannten Principal Investigators getragen. Diese sind den Instituten für Mathematische Optimierung (Kaibel, Sager), für Algebra und Geometrie (Kahle), für Mathematische Stochastik (Kirch, Janßen) und für Analysis und Numerik (Benner, Richter, Heiland) der Fakultät zugeordnet. Benner ist zudem Direktor des Max-Planck Institutes für Dynamik komplexer technischer Systeme. Die Fakultät für Elektrotechnik und Informationstechnik ist über Findeisen beteiligt.

Im Kontext des vorgeschlagenen Graduiertenkollegs (GK) verstehen wir Komplexität als eine intrinsische Eigenschaft, die einen mathematischen Zugang zu einem Problem auf drei Ebenen erschwert. Diese Ebenen sind eine angemessene mathematische Darstellung eines realen Problems, die Erkenntnis fundamentaler Eigenschaften und Strukturen mathematischer Objekte und das algorithmische Lösen einer mathematischen Problemstellung. Wir bezeichnen alle Ansätze, die systematisch auf einer dieser drei Ebenen zu einer zumindest partiellen Verbesserung führen, als mathematische Komplexitätsreduktion.

Für viele mathematische Fragestellungen sind Approximation und Dimensionsreduktion die wichtigsten Werkzeuge auf dem Weg zu einer vereinfachten Darstellung und Rechenzeitgewinnen. Wir sehen die Komplexitätsreduktionin einem allgemeineren Sinne und werden zusätzlich auch Liftings in höherdimensionale Räume und den Einfluss der Kosten von Datenerhebungen systematisch untersuchen. Unsere Forschungsziele sind die Entwicklung von mathematischer Theorie und Algorithmen sowie die Identifikation relevanter Problemklassen und möglicher Strukturausnutzung im Fokus der oben beschriebenen Komplexitätsreduktion.

Unsere Vision ist ein umfassendes Lehr- und Forschungsprogramm, das auf geometrischen, algebraischen, stochastischen und analytischen Ansätzen beruht und durch effiziente numerische Implementierungen komplementiert wird. Die Doktorandinnen und Doktoranden werden an einem maßgeschneiderten Ausbildungsprogramm teilnehmen. Dieses enthält unter anderem Kompaktkurse, ein wöchentliches Seminar und ermutigt zu einer frühzeitigen Integration in die wissenschaftliche Community. Wir erwarten, dass das GK als ein Katalysator zur Etablierung dieser erfolgreichen DFG-Ausbildungskonzepte an der Fakultät für Mathematik dienen und zudem helfen wird, die Gleichstellungssituation zu verbessern.

Die Komplexitätsreduktion ist ein elementarer Aspekt der wissenschaftlichen Hintergründe der beteiligten Wissenschaftler. Die Kombination von Expertisen unterschiedlicher mathematischer Bereiche gibt dem GK ein Alleinstellungsmerkmal mit großen Chancen für wissenschaftliche Durchbrüche. Das GK wird Anknüpfungspunkte an zwei Fakultäten der OVGU, an ein Max Planck Institut und mehrere nationale und internationale Forschungsaktivitäten in verschiedenen wissenschaftlichen Communities haben. Die Studierenden im GK werden in einer Fülle von mathematischen Methoden und Konzepten ausgebildet und erlangen dadurch die Fähigkeit, herausfordernde Aufgaben zu lösen. Wir erwarten Erfolge in der Forschung und in der Ausbildung der nächsten Generation führender Wissenschaftler in Akademia und Industrie.

Projekt im Forschungsportal ansehen

Das Projekt wird von den genannten Principal Investigators getragen. Diese sind den Instituten für Mathematische Optimierung (Averkov, Kaibel, Sager), für Algebra und Geometrie (Kahle, Nill, Pott), für Mathematische Stochastik (Kirch, Schwabe) und für Analysis und Numerik (Benner) der Fakultät zugeordnet. Benner ist zudem Direktor des Max-Planck Institutes für Dynamik komplexer technischer Systeme. Die Fakultät für Elektrotechnik und Informationstechnik ist über Findeisen beteiligt.

Im Kontext des vorgeschlagenen Graduiertenkollegs (GK) verstehen wir Komplexität als eine intrinsische Eigenschaft, die einen mathematischen Zugang zu einem Problem auf drei Ebenen erschwert. Diese Ebenen sind eine angemessene mathematische Darstellung eines realen Problems, die Erkenntnis fundamentaler Eigenschaften und Strukturen mathematischer Objekte und das algorithmische Lösen einer mathematischen Problemstellung. Wir bezeichnen alle Ansätze, die systematisch auf einer dieser drei Ebenen zu einer zumindest partiellen Verbesserung führen, als mathematische Komplexitätsreduktion.

Für viele mathematische Fragestellungen sind Approximation und Dimensionsreduktion die wichtigsten Werkzeuge auf dem Weg zu einer vereinfachten Darstellung und Rechenzeitgewinnen. Wir sehen die Komplexitätsreduktionin einem allgemeineren Sinne und werden zusätzlich auch Liftings in höherdimensionale Räume und den Einfluss der Kosten von Datenerhebungen systematisch untersuchen. Unsere Forschungsziele sind die Entwicklung von mathematischer Theorie und Algorithmen sowie die Identifikation relevanter Problemklassen und möglicher Strukturausnutzung im Fokus der oben beschriebenen Komplexitätsreduktion.

Unsere Vision ist ein umfassendes Lehr- und Forschungsprogramm, das auf geometrischen, algebraischen, stochastischen und analytischen Ansätzen beruht und durch effiziente numerische Implementierungen komplementiert wird. Die Doktorandinnen und Doktoranden werden an einem maßgeschneiderten Ausbildungsprogramm teilnehmen. Dieses enthält unter anderem Kompaktkurse, ein wöchentliches Seminar und ermutigt zu einer frühzeitigen Integration in die wissenschaftliche Community. Wir erwarten, dass das GK als ein Katalysator zur Etablierung dieser erfolgreichen DFG-Ausbildungskonzepte an der Fakultät für Mathematik dienen und zudem helfen wird, die Gleichstellungssituation zu verbessern.

Die Komplexitätsreduktion ist ein elementarer Aspekt der wissenschaftlichen Hintergründe der beteiligten Wissenschaftler. Die Kombination von Expertisen unterschiedlicher mathematischer Bereiche gibt dem GK ein Alleinstellungsmerkmal mit großen Chancen für wissenschaftliche Durchbrüche. Das GK wird Anknüpfungspunkte an zwei Fakultäten der OVGU, an ein Max Planck Institut und mehrere nationale und internationale Forschungsaktivitäten in verschiedenen wissenschaftlichen Communities haben. Die Studierenden im GK werden in einer Fülle von mathematischen Methoden und Konzepten ausgebildet und erlangen dadurch die Fähigkeit, herausfordernde Aufgaben zu lösen. Wir erwarten Erfolge in der Forschung und in der Ausbildung der nächsten Generation führender Wissenschaftler in Akademia und Industrie.

Projekt im Forschungsportal ansehen

Die meisten für die kombinatorische Optimierung relevanten Polytope haben exponentiell in der Größe der Probleminstanz viele Facetten, so dass für den linearen Optimierungsansatz exponentiell viele Nebenbedingungen beachtet werden müssen. Das Konzept der erweiterten Formulierungen erlaubt es, Polytope als affine Projektionen höher-dimensionaler, aber wesentlich einfacher zu beschreibender Polyeder darzustellen. Das Ziel dieses Projekts ist, das grundlegende Verständnis des Konzepts der erweiterten Formulierungen signifikant zu verbessern und neue Methoden sowohl für die Konstruktion als auch für die Bestimmung unterer Schranken an die kleinste mögliche Größe solcher Formulierungen zu entwickeln.

Projekt im Forschungsportal ansehen

Die meisten für die kombinatorische Optimierung relevanten Polytope haben exponentiell in der Größe der Probleminstanz viele Facetten, so dass für den linearen Optimierungsansatz exponentiell viele Nebenbedingungen beachtet werden müssen. Das Konzept der erweiterten Formulierungen erlaubt es, Polytope als affine Projektionen höher-dimensionaler, aber wesentlich einfacher zu beschreibender Polyeder darzustellen. Das Ziel dieses Projekts ist, das grundlegende Verständnis des Konzepts der erweiterten Formulierungen signifikant zu verbessern und neue Methoden sowohl für die Konstruktion als auch für die Bestimmung unterer Schranken an die kleinste mögliche Größe solcher Formulierungen zu entwickeln.

Projekt im Forschungsportal ansehen

Im Rahmen dieses Projektes werden grundlegende Fragen zu Symmetrien in der Ganzzahligen Linearen Optimierung untersucht. Insbesondere geht es dabei um die Beschreibung und Analyse von Polytopen, die Symmetrien beschreiben. Optimierungsprobleme, deren Lösungen Symmetrien aufweisen, führen in der Praxis häufig zu Problemen, da sie schlechte Schranken und ein schlechtes Enumerationsverhalten aufweisen. Ein besseres Verständnis der Polytope, die diesem Phänomen zu Grunde liegen, soll daher zu einer besseren Lesbarkeit dieser Probleme führen.

Projekt im Forschungsportal ansehen

Für viele kombinatorische Optimierungsprobleme sind die Beschreibungen der in natürlicher Weise zugeordneten Polytope notwendigerweise sehr kompliziert und groß. In machen Fällen kann man jedoch diese komlizierten Polytope als lineare Projektionen einfach zu beschreibender  höher dimensionaler Polyeder darstellen und mit diesen Darstellungen in der gleichen Weise Theorie und Praxis der Linearen Optimierung für das vorliegende kombinatorische Optimierungsproblem nutzbar machen. In diesem Projekt leiten wir zum einen Methoden zum Aufstellen solcher erweiterter Formulierungen her und untersuchen zum andern, welche grundsätzlichen Grenzen dieser Methodik gesetzt sind.

Projekt im Forschungsportal ansehen

Orbitope sind Polyeder, die erfolgreich zur Ausnutzung von speziellen Symmetrien in ganzzahligen linearen Optimierungsproblemen benutzt werden. In diesem Projekt untersuchen wir grundlegende Fragen zu Orbitopen, also zu konvexen Hüllen von 0/1-Matrizen, die lexikographisch maximal in ihrem Orbit unter einer durch Spaltenpermutation operierenden Gruppe sind. Ziel des Projekts ist es, heraus zu finden, welche Einschränkungen an die 0/1-Matrizen die Orbitope so kompliziert werden lassen, dass man unter komplexitätstheoretischen Annahmen keine brauchbaren Beschreibungen erwarten kann, und andererseits für Klassen, bei denen dies nicht der Fall ist, Ungleichungsbeschreibungen herzuleiten.

Projekt im Forschungsportal ansehen

Die Einführung von zeitindizierten Variablen in der gemischt-ganzzahligen Optimierung zur Abbildung zeitlicher Dynamik wie zum Beispiel in biologischen Signal-Netzwerken führt zu Modellen, für deren effiziente Lösung eine spezielle Analyse der mathematischen Struktur erforderlich ist. Dabei muss in besonderer Weise die durch die Zeitindizierung in das Modell importierte Symmetrie untersucht und ausgenutzt werden. In diesem Projekt sollen zum Einen für die Symmetriebrechung in der ganzzahligen linearen Optimierung grundlegende Polytope untersucht werden und zum anderen anhand von Modellen für Signal-Netzwerke spezifische Verfahren zur Symmetrie-Ausnutzung in dynamischen gemischt-ganzzahligen Optimierungsproblemen entwickelt werden.

Projekt im Forschungsportal ansehen

Teilprojekt der DFG-Forschergruppe "Algorithmen, Struktur, Zufall", in der außerdem Projekte der Arbeitgruppen von Prof. Dr. Günter Ziegler (TU Berlin), Prof. Dr. Martin Grötschel (Zuse-Institut Berlin) und Prof. Dr. Hans-Jürgen Prömel (HU Berlin) gefördert werden. In diesem letzten Jahr der Förderperiode werden insbesondere Beispiele untersucht, die eine Vermutung von Mihail und Vazirani über die Expansionseigenschaften der Graphen von 0/1-Polytopen unterstützen. Ein Beweis dieser Vermutung hätte weitreichende Folgen für das algorithmische Zählen komplexer kombinatorischer Objekte.

Projekt im Forschungsportal ansehen

Ganzzahlige Lineare Modelle werden für eine Vielzahl von Optimierungsproblemen verwendet. Häufig weisen diese Modelle eine hohe ymmetrie auf, die dazu führt, dass Algorithmen unnötig viel Arbeit verrichten müssen. In diesem Projekt untersuchen wir Möglichkeiten, solche Symmetrien zu brechen und damit die Effizienz von Algorithmen für die zu lösenden Optimierungsprobleme deutlich zu steigern.

Projekt im Forschungsportal ansehen