Generic Decomposition Algorithms for Integer Programs

• Applicant: Professor Dr. Marco Lübbecke
• Subject Area: Theoretical Computer Science
• Term: from 2009 to 2015
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 150304528

Dekompositionsalgorithmen nutzen spezielle Problemstrukturen in ganzzahligen Programmen aus und sind rechnerisch sehr erfolgreich, wenn sie auf Anwendungen zugeschnitten werden. Die zugrundeliegenden Strukturen sind theoretisch gut verstanden, aber ihr praktischer Nutzen fällt demgegenüber stark zurück. Dies ist insofern unbefriedigend, als dass es eine Wiederverwendung von Code verhindert und Nicht-Experten vom Stand der Technik ausschließt. Dieses Projekt zielt auf das Schließen dieser Lücke. Wir haben jüngst die generelle Machbarkeit nachgewiesen und damit in der Community einige Beachtung gefunden. Unsere Experimente legen nahe, dass die Modellstärke durch den generischen Ansatz stark verbessert wird. Verschiedene theoretische, algorithmische und rechnerische Fragen wurden so aufgeworfen, die nun beantwortet werden müssen: Welche Eigenschaften haben die kombinatorischen Probleme hinter der Strukturerkennung? Wie können wir, theoretisch und experimentell, die Güte einer Dekomposition bewerten? Wie kann eine gegebene Dekomposition verändert werden? Wie kann die strukturelle Information genutzt werden, z.B. für neue Branchingregeln, Primalheuristiken oder Symmetriebrechung? Dieses Projekt will diese Fragen theoretisch und experimentell beantworten. Das Feedback soll in die Entwicklung eines generischen Dekompositions-Algorithmus einfließen, der das Potenzial für ein allgemeines Werkzeug zum Lösen ganzzahliger Programme besitzt.

• DFG Programme: Priority Programmes
• Subproject of: SPP 1307: Algorithm Engineering