Graph-Zerlegungsschemata in diskreter Optimierung

Viele Planungsprobleme (Finanzplanung, Platzierung von Anlagen, Portfolio-Optimierung), Design-Probleme (optimales Design von Netzwerken in der Telekommunikation oder im Transportwesen, VLSI-Design) und Probleme im Scheduling, in der Robotik, der Mustererkennung, der Beweistheorie und der künstlichen Intelligenz können als diskrete Optimierungsprobleme (DO) formuliert werden. Leider haben DO Probleme, die realistische Probleme beschreiben, riesige Größen, die für derzeitige state-of-the- art DO Lösungsalgorithmen unbehandelbar sind. Um sich der Herausforderung, riesige DO Probleme zu lösen, zu stellen, werden dringend neue Dekompositionsmethoden benötigt. Denn praxisrelevante DO Probleme sind meist nicht nur riesig sondern zeichnen sich üblicherweise auch durch Dünnbesetztheit und andere Strukturen aus, die ein Lösungsalgorithmus ausnützen könnte. Das Ziel dieses Projektes ist es, effektive Algorithmen zur Lösung von DO Problemen zu entwickeln, die Dekompositionsmethoden aus der Graphentheorie, wie sie etwa in der nichtseriellen dynamischen Programmierung verwendet werden, Baumzerlegung und lokale Dekompositionsverfahren mit Logik- basierten Zugängen (Pseudo-boolesche Verfahren und binäre Entscheidungsdiagramme (BDD), Postoptimalitätsanalyse basierend auf Inferenzdualität in DO) kombinieren. Dekomposition und Sensitivitätsanalyse in DO sind eng miteinander verwoben. Dekompositionsmethoden bestehen darin, Familien verwandter DO Probleme zu erzeugen und zu lösen, die dieselbe Struktur aber unterschiedliche Datenwerte aufweisen. Sensitivitätsanalyse erlaubt es, Informationen, die während der Lösung eines speziellen DO Problems erlangt werden, zur schnelleren Lösung anderer Probleme in derselben Familie heranzuziehen. Eliminations-Dekompositionsverfahren (Nichtserielle dynamische Programmierung, Baumzerlegung und lokale Zerlegungsmethoden) verwenden parametrisierte DO Probleme, in denen manche Variablen fixiert werden. Um alle Lösungen zu finden, müssten dann alle Kombinationen binärer Werte für die fixierten Variablen durchgetestet werden. Dies resultiert in einer Familie verwandter DO Probleme mit unterschiedlichen rechten Seiten. Sind die Blöcke in solchen DO Problemen nicht zu groß, dann ist es möglich eine binäres Entscheidungsdiagramm für jeden Block zu konstruieren, mit dessen Hilfe die Aufgabe verwandte DO Probleme zu lösen zurückgeführt wird, kürzeste Pfade im BDD zu finden. Hier ist es wesentlich, dass dasselbe BDD verwendet wird, um alle kürzesten Pfade für jede mögliche binäre Belegung von Separatoren zu finden. BDDs enummerieren zulässige Punkte in DO Problemen als kürzeste Pfade vom Wurzelknoten zum Blattknoten zum logischen Wert 1. Üblicherweise ist die Anzahl der Knoten im BDD deutlich kleiner als die Anzahl der kürzesten Pfade ("implizite Aufzählung"). Ein natürlicher Zugang ist es daher, Hybrid-Algorithmen zu entwickeln, die sowohl Logik-basierte als auch Inferenz- basierte Sensitivitätsanalyse, BDDs mit Graph-Zerlegungsmethoden zu kombinieren, um Lösungen für riesige DO Probleme zu finden. Die Hauptziele des Forschungsprojektes sind: Die Analyse der Kombinationsmöglichkeiten von Graphzerlegungs- Schemata (nichtserielle dynamische Programmierung, Baumzerlegung, lokale Zerlegungsmethoden) mit Logik- basierten Zugängen (Inferenz-Sensitivitätsanalyse und BDDs), um effiziente Lösungsverfahren für DO Probleme zu entwickeln. Die folgenden Methoden werden im Projekt verwendet werden: 1. Eliminationsmethoden um speziell strukturierte DO Probleme zu lösen, 2. Postoptimalitätsanalyse um Familien verwandter DO Probleme zu lösen, 3. BDDs kombiniert mit Pseudo-booleschen Verfahren, 4. Kondensation und kondensierte Strukturgraphen von DO Problemen, Entwicklung von effizienten Kondensationsschemata, 5. Die Verwendung der COCONUT-API, um die Entwicklung der verschiedenen Module unabhängig voneinander zu machen, 6. Branch-and-Bound Verfahren zur BDD-Erzeugung und Postoptimalitätsanalyse eingebettet in Eliminationsverfahren.

Viele Planungsprobleme (Finanzplanung, Platzierung von Anlagen, Portfolio-Optimierung), Design-Probleme (optimales Design von Netzwerken in der Telekommunikation oder im Transportwesen, VLSI-Design) und Probleme im Scheduling, in der Robotik, der Mustererkennung, der Beweistheorie und der künstlichen Intelligenz können als diskrete Optimierungsprobleme (DO) formuliert werden. Leider haben DO Probleme, die realistische Probleme beschreiben, riesige Größen, die für derzeitige state-of-the- art DO Lösungsalgorithmen unbehandelbar sind. Um sich der Herausforderung, riesige DO Probleme zu lösen, zu stellen, werden dringend neue Dekompositionsmethoden benötigt. Denn praxisrelevante DO Probleme sind meist nicht nur riesig sondern zeichnen sich üblicherweise auch durch Dünnbesetztheit und andere Strukturen aus, die ein Lösungsalgorithmus ausnützen könnte. Das Ziel dieses Projektes ist es, effektive Algorithmen zur Lösung von DO Problemen zu entwickeln, die Dekompositionsmethoden aus der Graphentheorie, wie sie etwa in der nichtseriellen dynamischen Programmierung verwendet werden, Baumzerlegung und lokale Dekompositionsverfahren mit Logik- basierten Zugängen (Pseudo-boolesche Verfahren und binäre Entscheidungsdiagramme (BDD), Postoptimalitätsanalyse basierend auf Inferenzdualität in DO) kombinieren. Dekomposition und Sensitivitätsanalyse in DO sind eng miteinander verwoben. Dekompositionsmethoden bestehen darin, Familien verwandter DO Probleme zu erzeugen und zu lösen, die dieselbe Struktur aber unterschiedliche Datenwerte aufweisen. Sensitivitätsanalyse erlaubt es, Informationen, die während der Lösung eines speziellen DO Problems erlangt werden, zur schnelleren Lösung anderer Probleme in derselben Familie heranzuziehen. Eliminations-Dekompositionsverfahren (Nichtserielle dynamische Programmierung, Baumzerlegung und lokale Zerlegungsmethoden) verwenden parametrisierte DO Probleme, in denen manche Variablen fixiert werden. Um alle Lösungen zu finden, müssten dann alle Kombinationen binärer Werte für die fixierten Variablen durchgetestet werden. Dies resultiert in einer Familie verwandter DO Probleme mit unterschiedlichen rechten Seiten. Sind die Blöcke in solchen DO Problemen nicht zu groß, dann ist es möglich eine binäres Entscheidungsdiagramm für jeden Block zu konstruieren, mit dessen Hilfe die Aufgabe verwandte DO Probleme zu lösen zurückgeführt wird, kürzeste Pfade im BDD zu finden. Hier ist es wesentlich, dass dasselbe BDD verwendet wird, um alle kürzesten Pfade für jede mögliche binäre Belegung von Separatoren zu finden. BDDs enummerieren zulässige Punkte in DO Problemen als kürzeste Pfade vom Wurzelknoten zum Blattknoten zum logischen Wert 1. Üblicherweise ist die Anzahl der Knoten im BDD deutlich kleiner als die Anzahl der kürzesten Pfade ("implizite Aufzählung"). Ein natürlicher Zugang ist es daher, Hybrid-Algorithmen zu entwickeln, die sowohl Logik-basierte als auch Inferenz- basierte Sensitivitätsanalyse, BDDs mit Graph-Zerlegungsmethoden zu kombinieren, um Lösungen für riesige DO Probleme zu finden. Die Hauptziele des Forschungsprojektes sind: Die Analyse der Kombinationsmöglichkeiten von Graphzerlegungs- Schemata (nichtserielle dynamische Programmierung, Baumzerlegung, lokale Zerlegungsmethoden) mit Logik- basierten Zugängen (Inferenz-Sensitivitätsanalyse und BDDs), um effiziente Lösungsverfahren für DO Probleme zu entwickeln. Die folgenden Methoden werden im Projekt verwendet werden: 1. Eliminationsmethoden um speziell strukturierte DO Probleme zu lösen, 2. Postoptimalitätsanalyse um Familien verwandter DO Probleme zu lösen, 3. BDDs kombiniert mit Pseudo-booleschen Verfahren, 4. Kondensation und kondensierte Strukturgraphen von DO Problemen, Entwicklung von effizienten Kondensationsschemata, 5. Die Verwendung der COCONUT- API, um die Entwicklung der verschiedenen Module unabhängig voneinander zu machen, 6. Branch-and-Bound Verfahren zur BDD-Erzeugung und Postoptimalitätsanalyse eingebettet in Eliminationsverfahren.