Exakte Ganzzahlige Optimierung

• Antragsteller: Professor Dr. Martin Grötschel
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2007 bis 2013
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 49333131

Verfügbare Löser für gemischt-ganzzahlige Programme (mixed-integer programs, MIPs) sind auf die schnelle Berechnung von annähernd optimalen Lösungen für zulässige Instanzen ausgelegt. Die Nutzer wissen, dass die Antworten nur im Rahmen von Zulässigkeits- und Optimalitätstoleranzen verlässlich sind, legen aber in vielen Fällen auf exakte Lösungen keinen besonderen Wert. Die Lage ändert sich fundamental, wenn MIPs verwendet werden, um theoretische Fragen zu untersuchen, wenn Instanzen reine Zulässigkeitsprobleme sind (die unzulässig sind), und wenn falsche Antworten rechtliche Konsequenzen haben. Beispiele für solche Anwendungen sind die Designtheorie, die Chip-Verifikation, und die Vertragsvergabe mittels kombinatorischer Auktionen. Wir entwickeln und implementieren in diesem Projekt einen Ansatz zur exakten Lösung von MIPs. Auf Basis des Constraint Programming/MIP-Lösers SCIP wollen wir der wissenschaftlichen Gemeinschaft ein frei erhältliches Werkzeug zur Verfügung stellen, mit dem exakte Optimallösungen bzw., was vielleicht noch wichtiger ist, exakte Unzulässigkeitsbeweise berechnet werden können.

• DFG-Verfahren: Schwerpunktprogramme
• Teilprojekt zu: SPP 1307: Algorithm Engineering