Exakte Ganzzahlige Optimierung

• Applicant: Professor Dr. Martin Grötschel
• Subject Area: Theoretical Computer Science
• Term: from 2007 to 2013
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Priority Programmes
• Subproject of: SPP 1307: Algorithm Engineering