Ein neuer polynomieller Algorithmus für lineare Programmierung mit Anwendungen in kombinatorischer und konvexer Optimierung

• Antragsteller: Privatdozent Dr. Sergei Chubanov
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2012 bis 2016
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 214066775

Das Thema des laufenden Projektes ist "Ein neuer polynomieller Algorithmus für lineare Optimierung mit Anwendungen in kombinatorischer und konvexer Optimierung". Die schon erreichten Ergebnisse: E1) Ein neuer polynomieller Algorithmus für lineare Optimierung. Neben einer optimalen Lösung findet der neue Algorithmus eine polyedrische Beschreibung der optimalen Fläche in Zeit O(n^4L), wobei n die Anzahl von Variablen und L die Größe des linearen Programms ist. Diese Laufzeit ist mindestens so gut wie die Laufzeit, die wir durch eine Anwendung herkömmlicher Verfahren zur Lösung derselben Aufgabe erreichen. E2) Ein streng polynomieller Algorithmus für lineare Optimierungsprobleme mit 0-1 optimalen Lösungen. Das ist der erste streng polynomielle Algorithmus für diese Klasse von Optimierungsproblemen. Der Algorithmus findet eine optimale Lösung und ein Optimalitätskriterium für 0-1 optimale Lösungen. E3) Ein polynomieller Algorithmus für quadratische konvexe Optimierung mit linearen Nebenbedingungen. (Polynomiell in der Größe der Instanz und in log(1/e), wobei e ein Approximationsfehler ist.) E4) Ein polynomieller Algorithmus, der entweder eine Lösung zu Ax = b, Cx >= d, findet oder beweist, dass keine 0-1 Lösungen existieren. C ist 0-1 Matrix. Das System Cx >= d ist durch ein polynomielles Separationsorakel gegeben. (Das bedeutet z.B., das wir mit Hilfe dieses Algorithmus in pollynomieller Zeit eine untere Schranke für den optimalen Zielfunktionswert des Traveling-Salesman-Problems finden können, die mindestens so gut wie die bekannte Subtour-Schranke ist.) Die entwickelten Methoden basieren auf meinen neuen Projektionsalgorithmen und haben die folgenden Anwendungsaussichten: Lineare Optimierungsprobleme mit exponentiell vielen Variablen und konvexe und quasikonvexe Optimierungsprobleme. Diese Optimierungsprobleme entstehen häufig als Relaxationen NP-schwerer Probleme. Richtungen zukünftiger Forschung: R1) Neue polynomielle Algorithmen für konvexe und quasi-konvexe Optimierung. Das Verfahren von E2 ist auf konvexe und quasi-konvexe Optimierungsprobleme anwendbar. R2) Lineare Probleme mit exponentiell vielen Variablen. Die Algorithmen von E2 und E4 sind Grundlage für einen neuen Algorithmus zur Lösung dieser Probleme. R3) Neue Pivot-Regeln für den Simplex-Algorithmus. Traditionelle Pivot-Regeln führen häufig zu Stalling. Auf der Basis der neuen Projektionsverfahren können wir Pivot-Regeln entwickeln, die solche Effekte wie Stalling ausschließen. R4) Numerische Experimente. Eine effiziente Implementierung der neuen Algorithmen soll unter anderem auf die weitere Verwendung in Branch-and-Bound Verfahren orientiert werden. Die neuen Techniken ermöglichen eine deutliche Verbesserung der Einschätzungen der optimalen Zielfunktionswerte, die sich durch lineare und konvexe Relaxationen ergeben. Das neue Verfahren ist darüber hinaus in der Lage, einige strukturelle Eigenschaften optimaler Lösungen zu erkennen.

• DFG-Verfahren: Sachbeihilfen