Einfache und schnelle Implementierung von exakten Optimierungsalgorithmen mit SCIL

• Antragsteller: Professor Dr. Ernst Althaus; Professor Dr. Christoph Buchheim
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2007 bis 2014
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 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-Verfahren: Schwerpunktprogramme
• Teilprojekt zu: SPP 1307: Algorithm Engineering