Project Details
Projekt Print View

Generic Decomposition Algorithms for Integer Programs

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
 
 

Additional Information

Textvergrößerung und Kontrastanpassung