Globale Optimierungstechniken in kombinatorische Optimierung

Die Forschungsrichtung des Projektes ist wichtig und vielversprechend, da sie es ermöglicht, Algorithmen mit polynomialem Zeitaufwand für dünnbesetzte Optimierungsprobleme zu konstruieren. Optimierungsverfahren stellen einen wesentlichen Faktor für ein Bestehen im globalen Wettbewerb dar. Im Rahmen mathematischer Modellierung und Optimierung werden komplexe Prozesse erfasst und in ein mathematisch abbildbares Modell übertragen, das als Ergebnis den optimalen Ressourceneinsatz liefern soll. Die derzeit am Markt operierenden Anbieter von Optimierungslösungen verwenden Lösungsverfahren, bei denen die angewendete mathematische Optimierungsmethode im Vorhinein definiert ist, was zu Standardlösungen führt und individuelle Probleme vernachlässigt. Dadurch wird das durch die Optimierung erreichbare Kosteneinsparungspotential nicht voll ausgeschöpft. Die Hauptziele dieses Projektes sind die Analyse von Kombinationsmöglichkeiten aus globalen Optimierungstechniken mit kombinatorischen Zugängen wie nichtserieller dynamischer Programmierung und lokalen Zerlegungsalgorithmen, um effektive Verfahren zur Lösung von diskreten Optimierungsroblemen zu entwickeln, die zu den wichtigsten Klassen von Optimierungsproblemen gehören. Anwendungen der diskreten Optimierung tauchen in so unterschiedlichen Gebieten auf wie VLSI-Design, Zeitplanung, Netzwerk-Optimierung, Verbindungszuordnungen in Kommunikationsnetzwerken, ökonomischen Zuordnungsprobleme, mehrdimensionalen Glätten zur Mustererkennung, automatischem Beweisen, Spieltheorie und künstlicher Intelligenz. Ziel dieser Forschung ist die Entwicklung und Einführung einer neuen Methodik, die nichtserielle dynamische Programmierung verwendet, um in großem Umfang diskrete Optimierungsprobleme zu lösen, wobei Techniken zur globalen Optimierung und zur Lösung bestimmter MINLP aus dem Vorgänger-EU-Projekt-COCONUT, IST-2000- 26063 verwendet werden. Die im Projekt betrachteten Algorithmen der diskreten Optimierung sind die Folgenden: die nichtserielle dynamische Programmierung (NSDP), die lokalen Algorithmen der Dekomposition und die Baumzerlegung, die alle die Idee der dynamischen Programmierung verwenden. Die Erforschung folgender graphentheoretischer Konzepte ist erledigt: die Struktur von diskreten Optimierungsproblemen, Wegzerlegungen, Baumzerlegungen, Baumweitenbestimmung und die Beschreibung minimaler Separatorenmengen in einem Graphen. Die Interpretation dieser Konzepte wurde für diskrete Optimierungsprobleme mit spezieller Blockstruktur gemacht. Ein NSDP-Algorithmus für die Lösung von diskreten Optimierungsproblemen mit spezieller Blockstruktur wurde entwickelt. Die Verbindung mit lokalen Zerlegungsalgorithmen in der diskreten Optimierung wurde untersucht. Graphentheoretische Verfahren zum Finden von Blockzerlegungen für diskrete Optimierungsprobleme wurden verwendet. Ein Vergleich eines lokalen zerlegungsalgorithmischen Schemas für Blockzerlegungen mit Baum- und Pfadzerlegung über theoretische Abschätzung und Rechenverfahren wurde durchgeführt. Die folgenden Modifikationen der Algorithmen wurden vorgeschlagen: - Ein Hybridalgorithmus - nichtserieller lokaler Algorithmus, der die Nische in die Theorie der lokalen Algorithmen ausfüllt und der auf einheitliche Weise erlaubt, sie zu beschreiben. - Ein NSDP-Algorithmus wird entwickelt, der Blockeliminierung benutzt. Bei der Lösung des Blockproblems der diskreten Optimierung kann man moderne Löser der diskreten Optimierung ausnutzen. - Im NSDP-Blockalgorithmus und im Algorithmus, der die Baumzerlegung verwendet, wird es vorgeschlagen, die Ideen der Branch-and-Bound-Verfahren für das Entfernen der nicht perspektivischen Varianten auszunutzen.