Hochleistungs-Solver für binäre quadratische Probleme

Etliche Problemstellungen aus Anwendungsbereichen wie Finanzwesen, Telekommunikation, Logistik, usw. lassen sich elegant als sogenannte binäre quadratische Probleme mit linearen Nebenbedingungen formulieren. "Binär" bedeutet dabei, dass die Variablen nur den Wert Null oder Eins annehmen können. Eine Software zur Lösung solcher Probleme mit einer moderaten Anzahl von Variablen ist nicht verfügbar. Anwendungen haben jedoch typischerweise sogar eine enorme Anzahl an Variablen und der Bedarf an Software zur Lösung dieser Probleme ist durch die Vielzahl und Bedeutung der Anwendungen sehr groß. Das Ziel dieses Projekts mit dem Titel "Hochleistungs-Solver für binäre quadratische Probleme" ist die Entwicklung von Methoden und Implementierung von Algorithmen zur Bestimmung der optimalen Lösung von Instanzen dieser Problemklassen. Resultat dieses Projektes ist die open-source Software "BiqBin", welche existierender open- source Software aber auch kommerziellen Softwarepaketen überlegen sein wird. Zur Entwicklung der Software bedarf es innovativer Ideen aus dem Bereich der mathematischen Optimierung. Eine Transformation des Problems mit Nebenbedingungen (Restriktionen) in ein unrestringiertes Problem bildet dabei den Ausgangspunkt. Die Transformation wirft eine Reihe von Fragen auf, deren Untersuchung und Erforschung zur Entwicklung von effizienten Algorithmen führen. Die Implementierung des Algorithmus nutzt alle Möglichkeiten der Parallelisierung von relevanten Teilen des Codes zur effizienten Ausführung auf einem Hochleistungsrechner. Die Software (verfügbar auf einem Hochleistungsrechner in Novo Mesto) wird schlussendlich via Webinterface nutzbar sein und auch open-source bereitgestellt. Mit BiqBin wird man die Möglichkeit haben, diverse derzeit unlösbare Instanzen von unterschiedlichsten Anwendungen erstmals optimal zu lösen. Ein weiterer essentieller Aspekt ist die Interdisziplinarität: Die Verbindung von Mathematik, High-Performance Computing und Internettechnologien ist in Natur- oder Ingenieurswissenschaften ein innovativer und kaum praktizierter Zugang. Dieses Projekt ist die Fortsetzung gemeinsamer erfolgreicher Forschung der involvierten WissenschaftlerInnen, bereichert durch die Aufnahme von jungen ForscherInnen in das Team. Die beteiligten Institutionen sind das Institut für Mathematik an der Alpen-Adria-Universität Klagenfurt (AAU), die Fakulteta za informacijske študije in Novo Mesto (FIŠ) and das Inštitut za matematiko, fiziko in mehaniko in Ljubljana (IMFM). Das Projekt stärkt die Vorreiterrolle der AAU in der Entwicklung von Software in der mathematischen Optimierung und verhilft der FIŠ zur Etablierung der Fakultät als Kompetenzzentrum für Hochleistungsrechnen, handelt es sich hierbei doch um die einzige akademische Einrichtung in Slowenien in den Bereichen Informatik oder Mathematik, die einen Hochleistungsrechner besitzt und High-Performance Computing als Forschungsschwerpunkt verankert hat.

Etliche Problemstellungen aus Anwendungsbereichen wie Finanzwesen, Telekommunikation, Logistik, usw. lassen sich elegant als sogenannte binäre quadratische Probleme mit linearen Nebenbedingungen formulieren. "Binär" bedeutet dabei, dass die Variablen nur den Wert Null oder Eins annehmen können. Eine Software zur Lösung solcher Probleme mit einer moderaten Anzahl von Variablen ist nicht verfügbar. Anwendungen haben jedoch typischerweise sogar eine enorme Anzahl an Variablen und der Bedarf an Software zur Lösung dieser Probleme ist durch die Vielzahl und Bedeutung der Anwendungen sehr groß. Das Projekt "Hochleistungs-Solver für binäre quadratische Probleme" hat sich mit der Entwicklung von Methoden und Implementierung von Algorithmen zur Bestimmung der optimalen Lösung von Instanzen dieser Problemklassen beschäftigt. Resultat dieses Projektes ist die open-source Software "BiqBin", welche existierender open-source Software aber auch kommerziellen Softwarepaketen in mehreren Problemklassen überlegen ist. Zur Entwicklung der Software bedarf es innovativer Ideen aus dem Bereich der mathematischen Optimierung. Eine Transformation des Problems mit Nebenbedingungen (Restriktionen) in ein unrestringiertes Problem bildet dabei den Ausgangspunkt. Die Transformation wirft eine Reihe von Fragen auf, deren Untersuchung und Erforschung zur Entwicklung von effizienten Algorithmen führen. Die Implementierung des Algorithmus nutzt alle Möglichkeiten der Parallelisierung von relevanten Teilen des Codes zur effizienten Ausführung auf einem Hochleistungsrechner. Die Software (verfügbar auf einem Hochleistungsrechner in Ljubljana) wurde schlussendlich via Webinterface via http://biqbin.eu nutzbar gemacht und ist auch open-source bereitgestellt. Ein Aspekt dieses Projektes ist die Interdisziplinarität: Die Verbindung von Mathematik, High-Performance Computing und Internettechnologien ist in Natur- oder Ingenieurswissenschaften ein innovativer und noch wenig praktizierter Zugang. Dieses Projekt war die Fortsetzung gemeinsamer erfolgreicher Forschung der involvierten Wissenschaftler*innen, bereichert durch die Aufnahme von jungen ForscherInnen in das Team. Die beteiligten Institutionen sind das Institut für Mathematik an der Alpen-Adria-Universität Klagenfurt (AAU), die Fakulteta za informacijske študije in Novo Mesto (FIŠ) und die Fakulteta za strojništvo der Universität Ljubljana. Das Projekt hat die Vorreiterrolle der AAU in der Entwicklung von Software in der mathematischen Optimierung weiter verstärkt und der FIŠ sowie der Fakulteta za strojništvo an der Universität Ljubljana zur Etablierung als Kompetenzzentrum für Hochleistungsrechnen verholfen, handelt es sich hierbei doch um zwei einer Handvoll akademischer Einrichtung in Slowenien in den Bereichen Informatik oder Mathematik, die einen Hochleistungsrechner besitzen und High-Performance Computing als Forschungsschwerpunkt verankert haben.