Prof. Dr. Frühwirth: Probleme lösen mit Constraint-Programmierung

Video Vortrag: Computer knacken harte Nuesse: Von Sudoku ueber den Aktienhandel zum Robotersegeln, auch bei iTunes U, Thom Fruehwirth, 2013.
Video Vortrag: Einfuehrung in die Constraint-Programmierung, auch bei iTunes U, Thom Fruehwirth, 2012.

Produktions- und Personalplanung, Transportoptimierung und Konfiguration von Maschinen oder Software sind nur einige der schwierigen Probleme, die in Wirtschaft und Technik auftreten. Derartige Probleme sind so schwierig, dass sie sich im schlimmsten Fall nur durch Ausprobieren aller möglichen Lösungen behandeln lassen. Und dies ist meist nicht in vertretbarer Zeit machbar.

Constraint-Programmierung

Um solche harten Probleme mit dem Computer zu lösen, bedient man sich in den letzten Jahren immer öfters des Konzeptes der "Constraints". Man gibt dabei in abstrakter, mathematischer Form die Constraints (Bedingungen) an, die von einer Lösung erfüllt werden müssen. Mittels ausgeklügelter Verfahren werden diese Constraints vereinfacht, um so effizient einer Lösung näher zu kommen, ohne dass man nach ihr aufwendig suchen muss. Diese Vereinfachungen kann man elegant durch Regeln angeben, ganz ähnlich wie es Regeln und Tipps für Sudoku, das Damenproblem und andere Logeleien gibt. Auch diese und andere Denksportaufgaben lassen sich einfach durch Constraints beschreiben und lösen.

Abb.1 Beispiel: Sudoku, copyright wikipedia creative commons.

Abb.1 Beispiel: Sudoku, copyright wikipedia creative commons

Programmieren mit Constraints war von Anfang an nicht nur ein Forschungsthema, sondern auch Gegenstand kommerzieller Anwendungen. Lufthansa verwendet den Ansatz zur kurzfristigen Personalplanung, Renault in der Autofertigung, Nokia zum Konfigurieren für Software von Mobiltelefonen. Fast 2000 Zugfolgen täglich werden am Pariser Gare du Nord mit dieser Technologie geplant, oder die Schiffsent- und beladungen am Containerhafen Hongkong, einem der größten der Welt.

Forschungsgruppe Constraints

Das Constraint-Team um Öffnet einen externen Link in einem neuen FensterProfessor Frühwirth am Institut für Öffnet einen externen Link in einem neuen FensterProgrammiersprachen und Compilerbau geht der Frage nach, wie Programmiersprachen in zwanzig Jahren aussehen könnten. Constraints werden dabei eine wichtige Rolle spielen, ist man überzeugt. Dazu entwickelt das Team die Programmiersprache Öffnet einen externen Link in einem neuen Fenster"Constraint Handling Rules (CHR)". In dieser Computer-Sprache geben Regeln an, wie sich Constraints vereinfachen lassen. Das Constraint-Team ist eines der weltweiten Zentren für Constraint-Programmierung und entsprechend international vernetzt.

Abb.2 CHR Logo

Abb.2: CHR Logo

Computersprache Constraint Handling Rules (CHR)

Die Computersprache CHR ist inzwischen weltweit Gegenstand theoretischer Forschungen und praktischer Anwendungen. Jährlich findet ein internationaler Öffnet einen externen Link in einem neuen FensterWorkshop zu CHR statt, 2013 zum zehnten Mal. Die internationale Öffnet einen externen Link in einem neuen FensterCHR Sommerschule, eine der größten ihrer Art, findet 2013 zum dritten Mal statt. Viele hundert Öffnet einen externen Link in einem neuen Fensterwissenschaftliche Publikationen erwähnen CHR. CHR hat eine eigene Öffnet einen externen Link in einem neuen FensterEinstiegsseite und eine Öffnet einen externen Link in einem neuen Fensterumfangreiche Website, wo auch freie Implementierungen der Sprache heruntergeladen werden können. Mit Öffnet einen externen Link in einem neuen FensterWebCHR kann die Computersprache auch ganz einfach online ausprobiert werden.

Exemplarische Anwendungen Constraint Handling Rules (CHR)

CHR Software wurde unter anderem zur Verifikation von smarten Chipkarten im Öffnet einen externen Link in einem neuen FensterAutofocus System an der TU München verwendet, zur Öffnet einen externen Link in einem neuen Fensterräumlich-zeitlichen Steuerung von Robotern an der Universidad Jaume I, Castellón, Spanien, für Typsysteme der Programmiersprache Haskell bei Microsoft Research Cambridge und der Uni Singapur, zur Integration von heterogener Information im Öffnet einen externen Link in einem neuen FensterSemantic Web am MIT Cambridge/Boston, zur Lungenkrebsdiagnose an der Simon Fraser University in Vancouver und an der Uni Amsterdam zur Generierung von Multimedia-Präsentationen des Reichsmuseums.

Abb.3: Beispiel: Multimediaanwendung im Reichsmuseum Amsterdam

Abb.3: Beispiel: Multimediaanwendung im Reichsmuseum Amsterdam

Noch am European-Computer-Industry-Research-Centre hat Prof. Frühwirth zusammen mit der Universität München den Öffnet einen externen Link in einem neuen FensterMünchener Mietspiegel mittels CHR online gestellt. Er erlaubte es erstmals, durch eine Formularseite in wenigen Minuten die ortsübliche Vergleichsmiete einer Wohnung zu berechnen, auch wenn die Angaben ungenau sind. Davor konnte die Miete nur von Hand in stundenlanger Arbeit berechnet werden. Für die Universität München selbst wurde ein System zur Stunden- und Raumplanung entwickelt und erfolgreich eingesetzt.

Abb.4: Beispiel: System zur Stunden- und Raumplanung

Abb.4: System zur Stunden- und Raumplanung

In den USA wurde die Anwendung Öffnet einen externen Link in einem neuen FensterPOPULAR vom IEEE Expert Magazine als innovative Anwendung in der Telekommunikation ausgezeichnet. POPULAR entstand in Zusammenarbeit mit Siemens und optimiert mit CHR die Anzahl und Positionierung von lokalen Sendern für DECT-Funknetze in Gebäudekomplexen.

Abb.5: Grundriss Klosterkomplex

Abb.5: Grundriss Klosterkomplex

MTSeq ist eine Software, die ausgehend von Vorlagen das Komponieren automatisch erlernt. Dazu gibt es ein Demo-Video: Video: CHR-powered TTable MTSeq Multitouch Music Generation System Demo, auch auf iTunes U.

Mit dem Weltmeister im Robotersegeln wird Software für die Langzeit-Routenplanung von Überwachungsmissionen durch autonome Segelboote entwickelt. Bei einem Langstreckenweltrekordversuch hat sich die Software bestens bewährt.

In zwei großen staatlichen Projekten ist CHR ebenfalls vertreten: Im INRIA Projekt MANIFICO des französischen Wissenschaftsministeriums wurde eine Variante von CHR für die Modellierung von Geschäftsprozessen entwickelt. Im australischen Öffnet einen externen Link in einem neuen FensterNICTA Projekt G12 fließen die Erkenntnisse um CHR ein, um Optimierungsprobleme in der Industrie zu lösen.

Am Schweizer Kernforschungszentrum CERN wird derzeit der Einsatz von CHR-basierter Hardware für das effiziente Filtern von Daten vorbereitet, die in Sekundenbruchteilen bei Teilchenbeschleuniger-Experimenten anfallen.

Einige kommerzielle Anwender von Constraint Handling Rules


Aktienhandel - SecuritEase, Wellington, Neuseeland.
Die Bankensoftware des Marktführers in Neuseeland ermöglicht allein in Australien bis zu 50.000 Handelsvorgänge mit einem Volumen von bis zu 250 Millionen US Dollar am Tag.


Computergehirn für Service-Roboter - Cognitive Robots, Castellon, Spanien.

Automatisches Design von Einspritzgußformen - Cornerstone Intelligent Software Corp, Windsor, Kanada.


Routing von Optischen Netzwerken - Mitre Corp, Bedford, USA.


Automatische Testdatengenerierung - BSSE, Immenstaad, Deutschland.


Mehr zum Thema

Das Constraint-Team von Öffnet einen externen Link in einem neuen FensterProf. Dr. Frühwirth an der Uni-Ulm ist eines der weltweiten Zentren für Constraint-Programmierung. Im renommierten Wissenschaftsverlag Cambridge University Press ist eine Öffnet einen externen Link in einem neuen FensterMonografie über CHR erscheinen. Er war auch Co-Autor des ersten deutschsprachigen Öffnet einen externen Link in einem neuen FensterLehrbuches über Constraint-Programmierung, das später Öffnet einen externen Link in einem neuen Fensterins Englische übersetzt wurde. Mehr unter Öffnet einen externen Link in einem neuen FensterPublikationen und Öffnet einen externen Link in einem neuen FensterDrittmittelprojekte.

Weltrekordversuch im Roboter-Segeln, (Presse-Artikel), Eckernfoerde, 2012. In Zusammenarbeit mit Roboter-Segel-Weltmeister Roland Stelzer, INNOC Wien. Video: Das Roboter-Segelboot Roboat in Aktion (from INNOC).

Es gibt einen Online-Mitschnitt des Vortrags Computer knacken harte Nüsse: Von Sudoku über den Aktienhandel zum Robotersegeln, auch auf iTunes U, UUG-Vortragsreihe, Prof. Dr. Dr. Thom Frühwirth, Februar 2013, Ulm.

Stand April 2013. Basierend auf einem Artikel der Pressestelle der Uni Ulm.


Thom Frühwirth, October 7, 2014. This page is part of a multi-frame html document.