Produktions- und Personalplanung, Transportoptimierung und Konfiguration von Maschinen oder Software sind nur einige der harten 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.

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

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 Professor Frühwirth am Institut für Programmiersprachen 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 "Constraint Handling Rules (CHR)". In dieser Computer-Sprache geben Regeln an, wie sich Constraints vereinfachen lassen.

Abb.2: Logo

Computersprache Constraint Handling Rules (CHR)

Die Computersprache CHR ist inzwischen weltweit Gegenstand theoretischer Forschungen und praktischer Anwendungen. Jährlich findet ein Workshop zu CHR statt, zuletzt im portugiesischen Porto. Viele hundert wissenschaftliche Publikationen erwähnen CHR. CHR hat eine eigene umfangreiche Website , wo es auch online ausprobiert werden kann und freie Implementierungen der Sprache heruntergeladen werden können.

CHR Programme werden zur Verifikation von smarten Chipkarten im Autofocus System an der TU München verwendet, zur rä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 Semantic 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

Noch am European-Computer-Industry-Research-Centre hat Prof. Frühwirth zusammen mit der Universität München den Mü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: System zur Stunden- und Raumplanung

In den USA wurde die Anwendung POPULAR 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.