Mathematische Theorien für die Anwendung in der Praxis

Primaler Ansatz in ganzzahliger Optimierung

Ganzzahlige Optimierung ist die Aufgabe, den maximalen oder minimalen Wert einer (in der Regel linearen) Funktion über einer gegebenen Menge von ganzzahligen Punkten zu finden. Diese mathematisch formulierte Aufgabe dringt seit vielen Jahren immer stärker in verschiedene Bereiche der Anwendungen ein. Zu nennen sind an dieser Stelle Fragestellungen aus dem Design elektronischer Schaltungen, aus der Telekommunikation und dem Transport.

Kein einheitliches und effizientes Verfahren

Ein einheitliches effizientes Verfahren zur Lösung allgemeiner ganzzahliger linearer Programme gibt es, nach derzeitiger wissenschaftlicher Überzeugung, nicht. Dennoch können viele praxisrelevante Probleme von allgemeinen Verfahren in vernünftiger Zeit gelöst werden. Der Erfolg dieser Algorithmen hängt wesentlich davon ab, Struktureigenschaften von Problemen oder Problemklassen zu erkennen und ausnützen zu können.

Als besonders erfolgreich haben sich in den letzten Jahren sogenannte Schnittebenenverfahren herauskristallisiert, welche auf dem Studium der konvexen Hülle der ganzzahligen Lösungen eines diskreten Optimierungsproblems beruhen.

In einem gewissen Gegensatz zu Schnittebenenverfahren und Methoden der polyedrischen Kombinatorik steht der klassische "primale Ansatz", welcher, ausgehend von einem zulässigen Punkt eines ganzzahligen Programms, versucht, diesen iterativ zu verbessern. Dieses Problem heißt Augmentierungsproblem und kann geometrisch auf die Berechnung kleiner Basen eines Gitters oder die Konstruktion eines Erzeugendensystems (Hilbert Basis) für die ganzzahligen Punkte in einem Kegel reduziert werden. Zur Lösung solcher Problemstellungen gibt es grundlegende Verfahren: einerseits Gitterreduktionsmethoden, andererseits Verfahren, die Testmengen für ganzzahlige Programme konstruieren.

Eine Testmenge eines ganzzahligen Programms ist eine endliche Menge von Vektoren, so dass jeder nicht optimale, zulässige Punkt des Programms durch Addition eines Elements aus der Testmenge verbessert werden kann. In der Literatur sind mehrere Arten und Beispiele von Testmengen bekannt. Zu nennen sind an dieser Stelle Augmentierungsmethoden für spezielle kombinatorische Optimierungsprobleme, wie etwa das Min-cost-flow-problem oder das Optimierungsproblem über dem Durchschnitt zweier Matroide.

Testmengen für ganzzahlige Programme definieren spezielle Erzeugendensysteme für die ganzzahligen Punkte in polyedrischen Kegeln. Solche Erzeugendensysteme spielen auch eine wichtige Rolle in anderen Gebieten der Mathematik.

Problematisch an einem Testmengenansatz für allgemeine ganzzahlige Programme ist jedoch die Tatsache, dass im allgemeinen solche Mengen exponentiell groß werden. Dies wirft die Frage auf, ob ein primaler Algorithmus für ganzzahlige Programme überhaupt algorithmisch vernünftig ist.

Neues Verfahren mit praktischem Potential

Dem Lehrstuhl für Diskrete Optimierung in Magdeburg gelang es unlängst, diese Frage positiv zu klären. Genauer gesagt wurde von der Arbeitsgruppe ein Verfahren entwickelt, welches mit einer zulässigen ganzzahligen Lösung startet. Iterativ werden Spalten des Systems durch andere neue Spalten ersetzt, welche irreduziblen Lösungen eines gewissen Ungleichungssystems entsprechen. Die Methode benutzt keine Schnittebenen, jedoch werden - wie im Fall polyedrischer Methoden - Informationen des linearen Programms verwendet. Erste numerische Tests an ganzzahligen Programmen mit mehreren 100 bis 1000 Variablen belegen das praktische Potential des Verfahrens.

Finanziell wird die Forschung des Lehrstuhls an den primalen Methoden durch Mittel der Deutschen Forschungsgemeinschaft (Gerhard-Hess-Forschungsförderpreis) und des Landes Sachsen-Anhalt unterstützt.

Prof. Dr. Robert Weismantel