4.4.3 Überbestimmte Constraint-Probleme

Auch wenn die Problemstellungen im Bereich der Konfigurierung häufig unterbestimmt sind, können sich insbesondere bei inkrementellen Konfiguratoren, die während des Konfigurierungsprozesses Benutzerinteraktionen zulassen, inkonsistente Zustände ergeben, weil der Benutzer während der Konfigurierung sich widersprechende oder zu starke Anforderungen an die Konfiguration stellt. Eine solche Situation ist überspezifiziert bzgl. der Abhängigkeiten innerhalb der Konfigurierung, die je nach eingesetztem Konfigurator z.T. oder gar vollständig durch Constraints repräsentiert sein können. Im Bereich des Constraint Satisfaction spricht man von überbestimmten Constraint-Systemen bzw. Over-Constrained Systems (OCS). Abhilfe wird durch Verfahren geschaffen, die spezielle Konzepte zur Behandlung derartiger Konflikte anbieten. Da für ein OCS keine Lösungen im herkömmlichen Sinn existieren, wird stattdessen versucht, suboptimale Lösungen durch Teilerfüllung der Beschränkungen zu finden.

Freuder (1989) bzw. Freuder und Wallace (1992) entwickeln hierfür ein allgemeines Rahmenkonzept zur partiellen Constraint-Erfüllung mit dem Namen Partial Constraint Satisfaction Problem (PCSP). Freuder (1989, S. 280) führt aus, dass vier Möglichkeiten auf der Ebene eines Constraint-Systems existieren, Inkonsistenzen in einem überbestimmten Constraint-Problem zu entschärfen:

• Erweiterung des Wertebereichs einer Variable um geeignete Werte.

• Erweiterung der Menge R der Relationstupel eines Constraints, die angibt welche Wertekombinationen der Variablen kompatibel sind.

• Eliminierung von Variablen und der zugehörigen Constraints.

• Eliminierung von Constraints.

Unabhängig von dem eingesetzten Verfahren zur (Teil-)Lösung eines OCS wird eine Bewertungsfunktion benötigt, um die für die jeweilige Anwendung möglichst bestgeeignete Lösung auswählen zu können. Diese Bewertungsfunktion, auch Metrik genannt, dient dazu, eine Ordnung auf den unterschiedlichen, suboptimalen Lösungen zu definieren.^4.13

Die Eliminierung von Constraints ist auch unter der Bezeichnung Constraint-Relaxierung bekannt (vgl. Güsgen, 2000, S. 268 u. S. 281).^4.14 Möglichkeiten zur Constraint-Relaxierung in das Constraint-System zu implementieren, wurden bereits für die Vorgänger von ENGCON, PLAKON bzw. KONWERK diskutiert vgl. Günter, 1992, S. 102 f.; Günter, 1995b, S. 114; Syska und Cunis, 1991, S. 88 f..

Von Freuder und Wallace (1992) wird im Wesentlichen eine bestimmte Ausprägung des PCSP behandelt, genannt das Maximal Constraint Satisfaction Problem (MaxCSP). Innerhalb eines MaxCSP kommt eine simple Metrik zum Einsatz, die besagt, dass eine Problemlösung umso besser ist, je mehr Constraints durch diese Lösung erfüllt werden. Dies kommt ebenfalls der Relaxierung bestimmter Constraints gleich, die nicht Bestandteil einer auf diesem Wege generierten Lösung sind.^4.15

Da innerhalb eines PCSP bestimmte Constraints nicht erfüllt werden können, wird das Rahmenkonzept für eine derartige Constraint-Behandlung z.T. auch Soft Constraint Satisfaction Problem (SoftCSP) genannt (vgl. Ruttkay, 1994). Ein SoftCSP beinhaltet die Unterscheidung in weiche Constraints (engl. soft constraints) und harte Constraints (engl. hard constraints). Während weiche Constraints im Konfliktfall nicht unbedingt erfüllt werden müssen, um trotzdem zu einer ,,konsistenten`` Lösung zu gelangen, entsprechen harte Constraints den klassischen Beschränkungen, die in jedem Fall erfüllt werden müssen und nicht zurückgenommen werden können.

Eine in diesem Sinne weiterführende Möglichkeit zur Behandlung von überbestimmten Constraint-Netzen besteht in einer differenzierteren Unterscheidung von Lösungen anhand deren Qualität. Dies kann in Form von Constraint-Hierarchien durch Hierarchical Constraint Satisfaction Problems (HCSP) geschehen, einer weiteren Ausprägung des PCSP (vgl. Borning et al., 1994,1987,1992). Das HCSP erlaubt ebenfalls eine Relaxierung bestimmter Constraints, in diesem Fall indem eine Gewichtung entsprechend einer endlichen Menge unterschiedlicher Prioritätsstufen vorgenommen wird. Innerhalb dieser Hierarchie sind Constraints nach Präferenz geordnet. Constraints der höchsten Stufe müssen erfüllt werden, während niedriger priorisierte Constraints verletzt werden dürfen. Eine lexikographische Ordnung der Hierarchiestufen bestimmt die Güte unterschiedlicher Lösungen anhand der Gewichtungen der erfüllten Constraints. Die Erfüllung eines höher gewichteten Constraints wird dabei immer höher gewertet als die Erfüllung beliebig vieler geringer gewichteter Constraints auf niedrigeren Hierarchiestufen.^4.16 Im Gegensatz zum MaxCSP von Freuder und Wallace (1992), deren Metrik sich auf den Problemraum bezieht, d.h. auf die unterschiedlichen Abstände von relaxierten Problemen zum Originalproblem, bezieht sich die Metrik in einem HCSP auf den Lösungsraum, da hier die Güte unterschiedlicher Lösungen bewertet wird (vgl. Borning et al., 1992, S. 261).^4.17

Die Arbeiten von Alan Borning et al. führten zu einer Reihe unterschiedlicher Lösungsalgorithmen für hierarchische Constraint-Probleme namens ,,Blue``, ,,DeltaBlue``, ,,DeltaStar``, ,,SkyBlue``, ,,Indigo``, ,,Ultraviolet`` und ,,Cassowary``, deren Anwendungsbereich überwiegend in der deklarativen Behandlung von Einschränkungen im Bereich constraint-basierter grafischer Benutzungsoberflächen angesiedelt ist. Die bisher bekannten Lösungsverfahren für HCSPs sind z.T. inkrementell nutzbar. Sie alle weisen jedoch einige gravierende Einschränkungen auf: So können die zum Einsatz kommenden Lösungsalgorithmen entweder zyklische Constraint-Netze gar nicht oder nur eingeschränkt verarbeiten (local propagation), oder sie sind zwar in der Lage, auch zyklische Constraint-Netze zu verarbeiten, dafür allerdings ausschließlich lineare Constraints (linear programming) vgl. Borning et al., 1992, S. 246 ff.; Güsgen, 2000, S. 282 f.; Van Hentenryck und Saraswat, 1996, S. 711 f..

Die Nutzung von Constraint-Hierarchien hat insbesondere in der logischen Programmierung durch Hierarchical Constraint Logic Programming (HCLP) eine besondere Ausprägung erfahren (vgl. Wilson und Borning, 1993). Das HCLP ist eine Erweiterung des CLP-Schemas, wobei hier die Constraints innerhalb der Prolog-Regeln mit Informationen bzgl. der Constraint-Hierarchien versehen werden. Die Nutzung von Constraint-Hierarchien unterliegt allerdings auch beim HCLP denselben Einschränkungen bzgl. der existierenden Lösungsmechanismen.

Die bisher vorgestellten Verfahren zur Behandlung von OCS bewirken eine Zweiteilung der Constraints: Während ein Teil der Constraints erfüllt werden kann, ist dies für den jeweils anderen Teil nicht möglich. Ein davon abweichendes Konzept zur unscharfen Berechnung von Constraint-Problemen wird mit Fuzzy-Constraints innerhalb von Fuzzy Constraint Satisfaction Problems (Fuzzy CSP) verfolgt (vgl. Ruttkay, 1994). Fuzzy-Constraints geben den Grad der Erfüllung einer Beschränkung für eine konkrete Wertebelegung einer Menge von Variablen an. Das heißt anstatt für eine Variable einen bestimmten Wert vorzuschreiben, wird untersucht wie weit die Belegung von dem Sollwert abweicht. Diese Abweichung wird als Wert aus dem Intervall von 0 bis 1 angegeben. Für bspw. die Variablen $v_1,\ldots,v_k$ berechnet das Fuzzy-Constraint $C(v_1,\ldots,v_k)$ für eine konkrete Belegung $(d_1,\ldots,d_k) \in D_1 \times \ldots \times D_k$ einen Wert zwischen 0 und 1. Wenn dieser Grad für $C(d_1,\ldots,d_k)=1$ ist, bedeutet dies, dass $(d_1,\ldots,d_k)$ das Constraint C vollständig erfüllt. Wenn dagegen $C(d_1,\ldots,d_k)=0$ ist, bedeutet dies, dass $(d_1,\ldots,d_k)$ das Constraint C vollständig verletzt. Da man bei einer Lösung für ein Fuzzy CSP nicht an einer beliebigen Wertebelegung mit einer u.U. entsprechend großen Abweichung interessiert ist, wird versucht eine Maximierung des Erfüllungsgrades für das gesamte Problem zu erreichen. Ein Fuzzy CSP ist somit ebenfalls ein Optimierungsproblem (vgl. Güsgen, 2000, S. 283 f.).^4.18

Fußnoten

...^4.13

Eine Metrik ist eine Abstandsfunktion, die in diesem Fall definiert, wie weit die jeweilige suboptimale Lösung von einer vollständigen Lösung ,,entfernt`` ist. Ziel ist die Minimierung dieses ,,Abstands``.

...^4.14

Von engl. to relax: entspannen, lockern. Gemeint ist die ,,Lockerung`` bzw. Verringerung des Beschränkungsgrades eines Constraint-Netzes. Nicht zu verwechseln ist dies mit der Relaxierung, wie sie durch Konsistenzverfahren erreicht wird, indem (ungültige) Werte aus den Wertebereichen der Constraint-Variablen eliminiert werden (vgl. Fußnote 14). Grundsätzlich ist ein Constraint-Netz relaxed, wenn alle Constraints erfüllt sind (vgl. Freuder, 1978, S. 963). Dies lässt sich auf unterschiedliche Weise erreichen, sowohl durch die Eliminierung von Constraints als auch durch Konsistenzverfahren und Constraint-Propagation.

...^4.15

Freuder und Wallace (1992) setzen ein vollständiges, systematisches Suchverfahren namens Branch & Bound zur Optimierung, d.h. zur Maximierung der Anzahl der erfüllten Constraints, ein.

...^4.16

Dies ist die klassische Variante eines HCSP. In neueren Veröffentlichungen werden weiterführende Konzepte zum Vergleich erfüllter Constraints auf unterschiedlichen Hierarchiestufen dargelegt.

...^4.17

Güsgen (1989, S. 51 f.) und Gülden (1993, S. 49 ff.) benennen mit Constraint-Hierarchien für CONSAT bzw. für das Constraint-System von KONWERK die Bündelung einfacher Constraints zu zusammengesetzten Constraints. Bei der Propagation ermöglicht dies eine effiziente Erkennung, welche (Sub-)Constraints bei Wertebereichseinschränkungen betroffen sind und erneut zu propagieren sind.

...^4.18

Zur Lösung eines Fuzzy CSP wird ebenfalls Branch & Bound eingesetzt.