Project Details
Projekt
Einfache und schnelle Implementierung von exakten Optimierungsalgorithmen mit SCIL
Subject Area
Theoretical Computer Science
Term
from 2007 to 2014
Project identifier
Deutsche Forschungsgemeinschaft (DFG) - Project number 48021572
Die Software SCIL erlaubt eine einfache Implementierung von exakten Algorithmen für schwierige Optimierungsprobleme. Sie basiert auf effizienten Branch&Cut-Verfahren, unterstützt aber anders als vergleichbare Ansätze auch symbolische Nebenbedingungen anstelle von linearen Ungleichungen. Diese haben sich im Constraint Programming bewährt und machen SCIL zu einem benutzerfreundlichen Tool, das auch Nichtexperten einen einfachen Zugang zu modernen und leistungsstarken Optimierungsverfahren ermöglicht. Ziel des Projekts ist die Weiterentwicklung von SCIL. Ein Schwerpunkt wird dabei auf der Integration neuer Separierungsverfahren liegen, die einerseits zu einer deutlichen Beschleunigung führen sollen und andererseits zu einer Erweiterung der Modellierungsmöglichkeiten. Ein wichtiger Punkt ist hierbei die Verwendbarkeit polynomieller Zielfunktionen und logischer Nebenbedingungen. Beides ist praktisch von großer Bedeutung und zunehmend Gegenstand der Forschung. Ferner soll SCIL dahingehend erweitert werden, dass eine numerisch exakte optimale Lösung der Probleme berechnet werden kann. Dies ist bei sicherheitskritischen Anwendungen, wie z.B. der automatischen Verifikation von hybriden Systemen, Grundvoraussetzung zur Nutzbarkeit der Verfahren. Um eine praxisorientierte Entwicklung sicherzustellen, beschäftigt sich ein weiterer Teil des Projekts mit der Lösung schwerer praxisrelevanter Optimierungsprobleme, die sich als Anwendungen für SCIL besonders gut eignen.
DFG Programme
Priority Programmes
Subproject of
SPP 1307:
Algorithm Engineering
