Hochkarätiger Preis für Nachwuchswissenschaftler

Dr. Sergei Chubanov aus der Fakultät III erhielt den INFORMS Optimization Prize für Young Researchers.

Ende vergangenen Jahres wurde Dr. Sergei Chubanov, Mitarbeiter am Lehrstuhl Management Information Science der Fakultät III, für seine Arbeit zur linearen Optimierung in den USA mit dem INFORMS Optimization Prize for Young Researchers ausgezeichnet. Die international höchste Anerkennung für junge Wissenschaftler bringt die Universität Siegen damit in den Kreis von MIT, Princeton, Stanford, Berkeley oder INRIA. Die INFORMS, Institute for Operations Research and the Management Sciences, ist die größte Gesellschaft mit dem Ziel, „to improve operational processes, decision-making, and management by individuals and organizations through ... related scientific methods" und umfasst nahezu 10.000 Mitglieder weltweit. Der Preis wird jedes Jahr an einen Nachwuchswissenschaftler vergeben.

Seit mehr als einem halben Jahrhundert ist die lineare Optimierung ein zentraler Bestandteil der wirtschaftswissenschaftlichen Grundlagenausbildung an allen renommierten Business Schools, was sicherlich auch auf der extrem großen Anzahl und Vielfalt an Anwendungen in allen wirtschaftswissenschaftlichen Bereichen (Produktion, Logistik, Finanzierung, Investition, Operations Research, Spieltheorie, Marketing, etc.) basiert. Viele praktische Anwendungen werden als lineares Optimierungsproblem formuliert oder in ein solches transformiert und - je nach Komplexität - mit Standardsoftware oder speziell auf die Problemstellung zugeschnittenen Algorithmen optimal oder approximativ gelöst. Keine andere Methodik hat offenbar Theorie und insbesondere die Praxis mehr geprägt und verändert als die lineare Optimierung. Mit dem Simplex Algorithmus, in den 50er Jahren von George Dantzig entwickelt, und der ihn verwendenden Optimierungssoftware lassen sich Probleme der (nicht-ganzzahligen) linearen Optimierung in der Regel schnell lösen. Allerdings ist das Verfahren nicht polynomial, und es lassen sich mühelos Beispiele finden, die zu einer exponentiellen Laufzeit des Simplexalgorithmus führen. Mit anderen Worten, für solche Beispiele sind auch die schnellsten Computer heute nicht in der Lage noch zu unseren Lebzeiten optimale oder auch nur garantiert sehr gute Lösungen zu berechnen. Sensationell war 1979 die durch Khachiyan entwickelte Ellipsoid Methode als erster polynomialer Algorithmus zur linearen Optimierung, der jedoch in praktischen Anwendungen sehr langsam ist. Ein Grund für die schlechte Performance der Ellipsoid Methode liegt vermutlich darin, dass die Rechenzeit nicht nur von der Dimension des Problems abhängt, d.h. der Anzahl der Variablen und Restriktionen, sondern ebenfalls von weiteren Parametern, wie etwa dem größten Matrixwert. In streng polynomialen Verfahren würde dieser Wert nicht die Zahl der Iterationen beeinflussen. Mit anderen Worten, bei streng polynomialen Verfahren zur linearen Programmierung hängt die Rechenzeit polynomial von der Dimension der Probleminstanz ab und nicht von der Größe der Matrixwerte.

Bis jetzt ist kein streng polynomialer Algorithmus zur linearen Optimierung bekannt. Dr. Chubanov hat in seiner Arbeit „A strongly polynomial algorithm for linear systems having a binary solution“ einen sehr entscheidenden Durchbruch zur Lösung dieser Fragestellung erzielt und formuliert einen streng polynomialen Algorithmus zur linearen Optimierung für den Fall, dass die Variablenwerte im Intervall [0,1] liegen. In diesem Fall wird eine Lösung gefunden oder der Algorithmus terminiert mit dem Ergebnis, dass keine ganzzahlige Lösung für das System existiert. Der Algorithmus liefert eine völlig neues polynomiales Verfahren im allgemeinen Fall, das er in seiner Arbeit „A polynomial relaxation-type algorithm for linear programming“ beschreibt.