next up previous contents index
Nächste Seite: 4.5.3 Frameworks Aufwärts: 4.5 Verfügbare Constraint-Systeme Vorherige Seite: 4.5.1 Integrierte Constraint-Solver   Inhalt   Index

4.5.2 Bibliotheken

Die Mechanismen zur Constraint-Verarbeitung sind mittlerweile so weit ausgereift, dass eine Reihe von Bibliotheken bzw. eigenständige Constraint-Satisfaction-Systeme erhältlich sind. Diese Systeme bzw. Werkzeuge sind dazu vorgesehen, über Programmierschnittstellen an andere Programme und Systeme angebunden zu werden. Es sind ebenfalls eine Reihe von sowohl kommerziellen als auch frei verfügbaren Systemen erhältlich. Das Leistungsspektrum der einzelnen Constraint-Bibliotheken deckt jedoch, wie nachfolgend gezeigt wird und in Tabelle 4.1 übersichtlich aufgeführt ist, jeweils nur einen Teil der für ENGCON benötigten Eigenschaften ab.

So lassen sich die in Abschnitt 4.4.3 vorgestellten Constraint-Hierarchien, deren Anwendung in einem Konfigurierungssystem zweifellos interessante Möglichkeiten eröffnen würde, bedingt durch die Einschränkungen der verfügbaren Algorithmen und Constraint-Solver, nur begrenzt einsetzen. Von dem im Quellcode frei verfügbaren Constraint-Solver Cassowary4.37 ist neben einer Version für C++ und für Smalltalk ebenso eine Java-Version erhältlich. Cassowary steht unter der GNU Lesser General Public License, wodurch auch eine kommerzielle Nutzung möglich ist. Allerdings ist der in Cassowary verwendete inkrementelle Simplex-Algorithmus ausschließlich in der Lage, lineare Constraints zu verarbeiten. Zudem ist weder die Propagation von Intervallen noch von finiten Domänen vorgesehen, Cassowary ist auf reellwertige Variablen beschränkt (vgl. Badros et al., 2001).

Die Firma ILOG ist seit den 90er Jahren sehr erfolgreich in Bezug auf die Entwicklung und Vermarktung von Constraint-Werkzeugen (vgl. Freuder und Wallace, 2000). Der ILOG Solver4.38 (vgl. Puget, 1994; Puget und Leconte, 1995) ist als Komponente innerhalb der ILOG OPTIMIZATION SUITE erhältlich (vgl. Abschnitt A.2). Neben der C++-Version ist mit dem ILOG JSolver4.39 ebenfalls eine Java-Variante verfügbar (vgl. Chun, 1999c,a,b).4.40 Mit den Produkten von ILOG lassen sich sowohl finite Domänen als auch reellwertige Intervalldomänen verarbeiten.4.41 Zur Steigerung der Ausführungsgeschwindigkeit ist die parallele und (auf mehrere Prozessoren) verteilte Ausführung der Suchalgorithmen möglich (vgl. ILOG, 2004b). Allerdings bietet der ILOG Solver nicht die Möglichkeit, ein inkrementell anwachsendes Constraint-Netz zu verwalten vgl. Ranze et al., 2002, S. 850; Ringwelski, 2002, S. 195; Ringwelski, 2003, S. 24.

Ein Werkzeug mit ebenfalls hoher Funktionalität ist das kommerzielle System UniCalc4.42. UniCalc wurde entwickelt von der Novosibirsk Division of the Russian Research Institute of Artificial Intelligence. Das System basiert auf einer Kombination von Intervall-Constraint-Propagation, Intervallmathematik und Computeralgebra. Mit UniCalc lassen sich lineare und nichtlineare algebraische Ausdrücke bzw. Systeme, sowohl über die reellen Zahlen als auch ganzzahlig (integer programming), verarbeiten. Das Ergebnis einer Berechnung ist eine Menge von Intervallen, die alle reellen Lösungen enthalten. UniCalc ist in erster Linie ein mathematischer Problemlöser mit Schwerpunkt auf der Intervallverarbeitung. Es ist dagegen kein FD-Solver enthalten und es fehlt ebenfalls die Möglichkeit, ein inkrementell anwachsendes Constraint-Netz zu verwalten. Zudem ist UniCalc nicht in der Lage, unterbrochene Intervalle zu verarbeiten. UniCalc ist lauffähig in einer DOS/Windows-Umgebung und verfügt über eine C-Schnittstelle. Die Verfügbarkeit von UniCalc ist allerdings fraglich, da der Server des Instituts mit der offiziellen Homepage4.43 aktuell online nicht erreichbar ist, und die im Internet verfügbare Demo-Version von UniCalc ein bereits beträchtliches Alter aufweist. Ob eine Weiterentwicklung bzw. Pflege des Systems erfolgt ist daher offen. Da UniCalc nicht im Quellcode vorliegt, ist ebenso keine eigene Weiterentwicklung möglich bzw. nicht durch die Open-Source-Gemeinde zu erwarten.

Ebenfalls fokussiert auf die Intervallverarbeitung ist die Bibliothek ALIAS4.44. ALIAS ist eine leistungsfähige Constraint-Bibliothek, die in einer Version für C++ und als Modul für das Mathematik-Programm Maple erhältlich ist.4.45 Sie wird seit 1999 im COPRIN-Projekt4.46 des französischen INRIA4.47 entwickelt (vgl. Merlet, 2002). Neben Solvern zur Verarbeitung von reellwertigen Intervall-Constraints stellt ALIAS eine große Zahl weiterer intervallmathematischer Verfahren zur Verfügung. ALIAS ist Freeware für den akademischen Gebrauch und als Bibliothek sowie als ausführbares Binary unter Linux und Solaris erhältlich. Eine Live-Demo ist im Internet verfügbar.4.48 Leider liegt ALIAS nicht im Quellcode vor und kann daher nicht unter Windows (z.B. mittels Cygwin) compiliert bzw. genutzt werden (vgl. COPRIN, 2004).

Im Gegensatz zu ALIAS ist die C++-Bibliothek RealPaver4.49 von Laurent Granvilliers im Quellcode verfügbar, da sie unter einer Open-Source-Lizenz steht. War der RealPaver vormals ebenfalls nur eingeschränkt für die wissenschaftliche Forschung verfügbar, steht er in der neuesten Version unter BSD-Lizenz, und ist dementsprechend auch kommerziell einsetzbar.4.50 Die neueste Version ist dazu außer für die Betriebssysteme Linux und Solaris in einer mit Cygwin unter Windows lauffähigen Variante erhältlich. Allerdings lassen sich mit RealPaver ebenso wie mit der ALIAS-Bibliothek keine FD-Constraints behandeln. Zwar ist der RealPaver in der Lage, Integer-Werte zu verarbeiten, bietet hierfür aber keinen separaten Constraint-Solver an. Zudem werden von RealPaver weder die inkrementelle Verarbeitung von Constraints noch unterbrochene Intervalle, in Bezug auf die Wertebereiche der Constraint-Variablen, unterstützt (vgl. Granvilliers, 2004).

Eine Bibliothek mit Algorithmen zur Verarbeitung von FD-Constraints ist die Bibliothek C-Lib von Peter van Beek.4.51 Die Routinen dieser in der Programmiersprache C geschriebenen Bibliothek sind im Quellcode frei verfügbar (Public Domain) und bieten dem Entwickler Bibliotheksfunktionen für Such- und Konsistenzverfahren über finite Domänen. Allerdings ist diese Bibliothek auf FD-Constraints beschränkt und zudem ausschließlich in der Lage, binäre Tupel-Constraints anstatt implizite, intensional repräsentierte Relationen zu verarbeiten. Ein inkrementell anwachsendes Constraint-Netz ist ebenso nicht vorgesehen.

Das Java-Pendant zu van Beeks C-Bibliothek (mit einigen Erweiterungen) ist die Java Constraint Library (JCL)4.52 von Marc Torrens, entstanden im Rahmen einer Diplomarbeit an der Eidgenössisch Technischen Hochschule (ETH) Lausanne4.53 (vgl. Torrens, 1997). Die Bibliothek ist Open-Source und steht unter LGPL. Sie kann daher ebenfalls kommerziell genutzt werden. Auch für die JCL wird im Internet eine Demonstration bereitgestellt.4.54 Die JCL bietet ebenfalls eine Reihe unterschiedlicher Suchverfahren, die z.T. mit Konsistenzverfahren kombiniert werden. Selbige können allerdings auch lediglich als Preprozessing zum Einsatz kommen. Ein CSP wird zur Verarbeitung durch die JCL in einer eigens implementierten Sprache, der CSP Description Language (CSPDL), definiert und geparst. Zur Unterstützung des Entwicklungsprozesses existiert eine grafische Oberfläche (,,Constraint-Shell``), in der CSPs editiert und die Lösungsprozesse initiiert werden können (vgl. Torrens et al., 1997a,1998,1997b).

War die JCL in ihrer ersten Version ebenfalls ausschließlich in der Lage, extensionale Tupel-Constraints zu verarbeiten, ist sie mittlerweile um die Möglichkeit der Verarbeitung arithmetischer Constraints mit numerischen Wertebereichen, d.h. von Gleichungs- und Ungleichungssystemen über ganze Zahlen, erweitert worden. Die Entwicklung der JCL wird fortgeführt, und die nächste (stabile) Version wird voraussichtlich um die Unterstützung für SoftCSPs erweitert (vgl. Neagu et al., 2003). Jedoch unterstützt auch die JCL ausschließlich binäre FD-Constraints, d.h. es können ebenfalls weder n-äre FD-Constraints noch Intervalldomänen verarbeitet werden. Zudem bietet auch die JCL nicht die Möglichkeit zur inkrementellen Constraint-Verarbeitung.

Declarative Java (DJ)4.55 stellt die Einbettung des Prolog-Dialekts B-Prolog4.56 in die Programmiersprache Java dar (vgl. Zhou et al., 1998). In B-Prolog wurde dazu ein Compiler implementiert, der DJ-Programme interpretiert und das Constraint-Problem extrahiert. Anschließend wird der Constraint-Solver von B-Prolog zur Berechnung von entsprechenden Lösungen genutzt und als Ergebnis ein Java-Programm sowie eine HTML-Seite zur Visualisierung erzeugt. DJ kann daher, außer mit dem Schwerpunkt auf der Constraint-Berechnung, zur Visualisierung von Lösungen und für grafische Komponenten und GUIs, insbesondere Java-Applets in Internet-Anwendungen, eingesetzt werden. Mittels DJ lassen sich algebraische Constraints definieren, allerdings ausschließlich lineare Constraints mit finiten Domänen. Neben Wertebereichen mit finiten Wertemengen schließt dies Integer-Intervalle ein. Der Constraint-Mechanismus von DJ erlaubt kein inkrementelles Anwachsen des Constraint-Netzes. DJ ist frei verfügbar und sowohl für Windows als auch für Solaris erhältlich (vgl. Zhou, 1999).

Eine weitere wie JCL vollständig in Java implementierte Constraint-Bibliothek ist der Koalog Constraint Solver (KCS)4.57. Der KCS der französischen Firma Koalog ist eine Bibliothek zur Programmierung mit Constraints (CP). KCS verfügt ausschließlich über fest vorgegebene FD-Constraints (global constraints), wie sie für spezielle Problemstellungen, benötigt werden (vgl. Abschnitt 4.1). Der KCS kann auf programmiersprachlicher Ebene um einzelne Constraints oder Constraint-Solver erweitert werden. Eine Schnittstelle, mit deren Hilfe beliebige Constraints formuliert werden können, ein inkrementeller Constraint-Solver oder Intervallverarbeitung ist in dieser Bibliothek nicht vorgesehen (vgl. Koalog, 2005).

Der Constraint-Solver J.CP von Georg Ringwelski ist eine weitere aktuelle Java Lösung (vgl. Ringwelski, 2002,2001b). J.CP ist als Prototyp im Rahmen einer Dissertation entstanden (vgl. Ringwelski, 2003) und implementiert Asynchronous Constraint Solving (vgl. Abschnitt 4.4.4). Mittels J.CP ist daher das verteilte Lösen von Constraints, der inkrementelle Aufbau des Constraint-Netzes sowie Constraint-Relaxierung möglich.4.58 Derzeit lassen sich mit J.CP ausschließlich Constraints mit Variablen über finite Domänen verarbeiten. Ringwelski (2003, S.158) beschreibt aber, wie der Prototyp von J.CP bspw. um einen Simplex-Solver ergänzt werden kann. Allerdings ist J.CP grundsätzlich ebenso wie KCS ein System zur Programmierung mit Constraints, d.h. J.CP verfügt über eine Reihe fest implementierter Constraints. Für jedes weitere mögliche Constraint ist es erforderlich, dass jeweils eine spezielle Propagationsfunktion implementiert wird. Derartige Systeme sind für den Bereich CP geeignet, da sie die hier je nach Problemstellung erforderlichen, speziellen Constraints anbieten.4.59 Im Fall von ENGCON sind allerdings ,,generische`` Constraint-Solver für algebraische Constraints erforderlich, d.h. es muss möglich sein, anstatt einiger weniger vorgegebener Constraints, beliebige Relationen abbilden zu können.

Ein Java-basierter Constraint-Solver, der in der Lage ist, reellwertige Intervall-Constraints zu verarbeiten, ist der Brandeis Interval Arithmetic Constraint Solver, auch kurz IASolver genannt, von Timothy J. Hickey. Der IASolver ist als Forschungsprototyp entstanden (vgl. Hickey et al., 2000). Eine Online-Demo ist auf der Homepage des Autors verfügbar.4.60 Der IASolver nutzt eine eigens in Java entwickelte Intervallarithmetik-Bibliothek namens IAMath. Sämtliche Komponenten des IASolver sind Open-Source. Sie wurden ursprünglich unter LGPL veröffentlicht, wobei die IAMath mittlerweile unter der noch weniger restriktiven ,,zlib/libpng``-Lizenz erhältlich ist.4.61 Beide Lizenzen ermöglichen auch einen kommerziellen Einsatz der Software. Der IASolver verarbeitet ausschließlich reellwertige, kontinuierliche Intervalle und damit keine FD-Constraints. Unterbrochene Intervalle sind bisher ebenso wenig vorgesehen wie ein inkrementell anwachsendes Constraint-Netz.


Tabelle 4.1: Vergleich unterschiedlicher Constraint-Bibliotheken
  FD IN RW IS RE HO NL IK KO QC SP MS
Cassowary - - x x x x - x - x Java x
ILOG Solver x x (x) x x x x - x - C++ x
ILOG JSolver x - - x x - - x x - Java x
UniCalc - x - x x x x - x - C x
ALIAS - x - x x x x - - - C++ -
RealPaver - x - x x x x - - x C++ x
C-Lib x - - - x - - - - x C x
JCL x - - x x - - - - x Java x
DJ x - - x x x - - - - Java x
KCS x - - x - x - - x - Java x
J.CP x - - x - x - x - - Java x
IASolver - x - x x x x - - x Java x
                
FD  :  finite Domänen  NL  :  nichtlineare Constraints
IN  :  reellwertige Intervalldomänen  IK  :  Inkrementalität
RW  :  reellwertige Domänen  KO  :  kommerzielle Bibliothek
IS  :  intensionale Constraints  QC  :  Quellcode verfügbar
RE  :  beliebige Relationen möglich  SP  :  Sprache der Schnittstelle
HO  :  n-äre Constraints  MS  :  für Microsoft Windows verfügbar


In Tabelle 4.1 sind die für ENGCON wichtigsten Eigenschaften der vorgestellten Constraint-Bibliotheken übersichtlich dargestellt. Der ILOG Solver ist der einzige Constraint-Solver, der sowohl finite als auch infinite, d.h. reellwertige Intervalldomänen unterstützt. Rein reellwertige Wertebereiche besitzen keine Priorität für ENGCON, der hierarchische Constraint-Solver Cassowary unterstützt diese ausschließlich, der ILOG Solver mit Hilfe einer Erweiterungsbibliothek. Bis auf die C-Lib lassen sich mit allen Bibliotheken Constraints in Form von intensionalen Relationen modellieren. Der KCS und J.CP fokussieren den Bereich der Programmierung mit Constraints (CP) und sind daher nicht ohne weiteres in der Lage, neben einer Reihe von vorgegebenen Constraints beliebige Relationen zu verarbeiten. Nichtlineare Constraints sind hier bezogen auf reellwertige (Intervall-)Domänen. Sie können von allen Intervallbibliotheken verarbeitet werden, FD-Solver sind nicht berücksichtigt. Ein inkrementell anwachsendes Constraint-Netz wird lediglich von ILOG JSolver, Cassowary und J.CP unterstützt. Die Erweiterbarkeit durch vorhandenen Quellcode ist bei kommerziellen Systemen naturgemäß nicht gegeben. Bibliotheken, die unter einer Open-Source-Lizenz stehen oder als Public Domain verfügbar sind, bieten im Gegensatz dazu diese Möglichkeit. Die APIs aller Bibliotheken sind entweder in der Programmiersprache C bzw. C++ oder in Java verfügbar.4.62 Die sehr leistungsfähige Intervallbibliothek ALIAS ist leider nicht, wie für ENGCON vorausgesetzt, unter dem Betriebssystem Microsoft Windows nutzbar. Für alle anderen Bibliotheken steht für diese Plattform eine Version zur Verfügung, oder sie sind durch Java plattformübergreifend einsetzbar.

Die vorgestellten Constraint-Solver decken jeder für sich genommen ein unterschiedliches Leistungsspektrum ab. Es konnte keine Bibliothek ausfindig gemacht werden, welche die Anforderungen von ENGCON vollständig erfüllt. Inkrementalität wird nur von ILOG JSolver, Cassowary und J.CP unterstützt. Mit ILOG JSolver allerdings lassen sich keine Intervall-Constraints, mit Cassowary keine der erforderlichen Wertedomänen sowie keine nichtlinearen Constraints verarbeiten. J.CP hingegen ist ein Forschungsprototyp, der ausschließlich Solver für spezielle Constraints aufweist. Zudem eignen sich existierende Constraint-Solver häufig ausschließlich für bestimmte Problemstellungen, insbesondere betrifft dies die unterstützten Wertebereiche. Bis auf den ILOG Solver unterstützt keine Bibliothek sowohl finite Wertebereiche als auch Intervalldomänen.

Zur Unterstützung unterschiedlicher Domänen ist eine Kombination von Constraint-Solvern notwendig. Um Constraint-Solver mit unterschiedlichen Eigenschaften für eine Anbindung an ENGCON zu kombinieren ist eine einheitliche Schnittstelle für deren Integration bzw. ein Framework erforderlich, in dem diese Solver implementiert werden können. Im Folgenden Abschnitt werden einige Ansätze für derartige Constraint-Frameworks vorgestellt.



Fußnoten

...4.37
http://www.cs.washington.edu/research/constraints/cassowary/
...4.38
http://www.ilog.com/products/solver/
...4.39
http://www.ilog.com/products/jsolver/
...4.40
Der ILOG JSolver stammt ursprünglich nicht vom ILOG Solver, sondern von dem von Andy Hon Wai Chun entwickelten JSolver ab. Der JSolver wurde anfangs zu Ausbildungs- und Forschungszwecken frei verfügbar im Internet zum Download angeboten und war in der Lage, Constraint-Relationen über finite Domänen (Integer- und Boolesche-Variablen) zu verarbeiten (vgl. Chun, 1999c,a,b). Mittlerweile wurde der JSolver in die kommerzielle Produktpalette von ILOG integriert (vgl. ILOG, 2002) und ist daher nicht mehr frei im Internet zu beziehen.
...4.41
Durch die Erweiterung des ILOG Solver um die mathematische Bibliothek ILOG CPLEX lassen sich reellwertige Constraint-Probleme auch durch reell-mathematische Lösungsverfahren behandeln (vgl. ILOG, 2004a): http://www.ilog.com/products/cplex/.
...4.42
http://archives.math.utk.edu/software/msdos/miscellaneous/unicalc/
...4.43
http://www.rriai.org.ru/UniCalc/
...4.44
http://www-sop.inria.fr/coprin/logiciels/ALIAS/ALIAS.html
...4.45
ftp://ftp-sop.inria.fr/coprin/ALIAS
...4.46
Constraints solving, OPtimisation, Robust INterval analysis
...4.47
Institut National de Recherche en Informatique et en Automatique: http://www.inria.fr
...4.48
ALIAS On Line: http://www-sop.inria.fr/coprin/aol/form.html
...4.49
http://www.sciences.univ-nantes.fr/info/perso/permanents/granvil/realpaver/
...4.50
http://sourceforge.net/projects/realpaver
...4.51
http://ai.uwaterloo.ca/~vanbeek/software/software.html
...4.52
http://liawww.epfl.ch/JCL/
...4.53
École Polytechnique Fédérale de Lausanne (EPFL)
...4.54
http://www.marctorrens.com/downloads/projects/JCL/exercise/exercise.html
...4.55
http://www.cad.mse.kyutech.ac.jp/people/zhou/dj.html
...4.56
http://www.cad.mse.kyutech.ac.jp/people/zhou/bprolog.html
...4.57
http://www.koalog.com/php/jcs.php
...4.58
Constraint-Relaxierung wird von Ringwelski (2003) engl. constraint retraction genannt.
...4.59
Wie auch CLP-Systeme, vgl. Abschnitt 4.5.1.
...4.60
http://www.cs.brandeis.edu/~tim/Applets/IAsolver.html
...4.61
http://interval.sourceforge.net/interval/java/ia_math/
...4.62
Systeme mit einer Schnittstelle in C/C++ können per JNI an an ENGCON angebunden werden (vgl. Stearns, 1997,1998).

next up previous contents index
Nächste Seite: 4.5.3 Frameworks Aufwärts: 4.5 Verfügbare Constraint-Systeme Vorherige Seite: 4.5.1 Integrierte Constraint-Solver   Inhalt   Index