5.3.6 Box-Konsistenz

Sind die bisher vorgestellten Lösungsmethoden für ICSPs jeweils Abwandlungen bzw. Erweiterungen des Waltz-Filteralgorithmus, stellen Frédéric Benhamou et al. ein Konsistenzverfahren vor, welches ein numerisch-mathematisches Verfahren zum Einschränken der Wertebereiche von Constraint-Variablen nutzt (vgl. Benhamou et al., 1994a,b). Der erreichte Grad lokaler Konsistenz wird Box-Konsistenz genannt (engl. box consistency) und stellt eine Vereinigung zwischen Lösungsmethoden für CSPs aus der AI-Community und dem Bereich der Intervallanalysis dar. Box-Konsistenz ist ebenfalls eine Approximation von Kantenkonsistenz, die in kontinuierlichen Domänen, aufgrund der Präzisionsbeschränkungen von Rechenanlagen, grundsätzlich nicht erreicht werden kann. Benhamou et al. (1994a) setzen die Strategie des AC-3-Algorithmus und das Newton-Intervallverfahren zur Wertebereichseinschränkung ein. Das Newton-Intervallverfahren ist eine Erweiterung des iterativen Newton-Verfahrens zur numerischen Nullstellenberechnung. In Verbindung mit einer internen Splitting-Technik ist es möglich, durch die Intervall-Version dieses Verfahrens Box-Konsistenz für nichtlineare Gleichungen und Ungleichungen herzustellen indem die jeweils äußerste linke und rechte Nullstelle einer Intervallfunktion berechnet wird.

Ebenso wie Hull-Konsistenz und deren verwandten Konsistenzgrade beschränkt sich Box-Konsistenz auf konvexe Domänen, d.h. ununterbrochene Intervalle. Der Fokus liegt hier darauf, die Außengrenzen dieser Wertebereiche so weit wie möglich einzuschränken. Die Definition von Box-Konsistenz ist dementsprechend allgemein gehalten und wird in neueren Publikationen übersichtlich folgendermaßen notiert (vgl. Collavizza et al., 1999, S. 220):

Definition 5.3.16   (Box-Konsistenz/box consistency)
Sei P ein ICSP, $C_j$, $j \in \{1,\ldots,m\}$ ein k-stelliges Constraint in P über die Variablen $(v_1,\ldots,v_k)$. $C_j$ ist Box-konsistent, gdw. $\forall v_i \in \{v_1,\ldots,v_k\}$ mit $I_i=[a,b]$ die folgenden Relationen gelten:

1. $C_j(I_1,\ldots,I_{i-1},[a,a^+[,I_{i+1},\ldots,I_k)$,

2. $C_j(I_1,\ldots,I_{i-1},]b^-,b],I_{i+1},\ldots,I_k)$.

Ein ICSP ist Box-konsistent, gdw. alle Constraints $C_j$ Box-konsistent sind.

Wobei $a^+$ für die kleinste innerhalb der Präzisionsgrenzen darstellbare Zahl größer als $a$, und $a^-$ für die größte darstellbare Zahl kleiner als $a$ steht. Durch die Definition wird lediglich bezeichnet, dass jeweils das $i$-te Intervall nicht weiter eingeschränkt werden kann. Der Zustand erreichter Box-Konsistenz für das ICSP P wird $\Phi_{Box}(P)$ genannt.

Damit die Constraints durch ein numerisches Näherungsverfahren verarbeitet werden können, müssen sie sich in der Form $E\,\diamond\,0$ befinden, wobei $E$ ein Term ist, und $\diamond{}\in{}\{=,\geq\}$.^5.107 Ein wichtiger Aspekt bei der Herstellung von Box-Konsistenz ist die Art und Weise, wie die Generierung von Projektionen erfolgt. Diese werden, wie in den vorher bereits beschriebenen Verfahren, dazu benötigt, den Wertebereich einzelner Variablen einzuschränken. Ein Constraint ist entsprechend Box-konsistent, wenn alle seine Projektionen Box-konsistent sind. Benhamou et al. (1994a) erzeugen Projektionen, indem sie in den ursprünglichen Constraints jeweils sämtliche Variablen bis auf eine durch ihre Intervalldomänen ersetzen. Diese Projektions-Constraints bilden ein System von unären Intervallfunktionen, die von numerischen Verfahren behandelt werden können. Eine Zerlegung komplexer Constraints in primitive Constraints und die Einführung zusätzlicher Variablen, wie bei der Hull-Konsistenz, entfällt, was sich positiv auf die Effizienz bei der Lösung größerer Probleme auswirkt. Zudem sind die Ergebnisse i.A. genauer als die mit 2B-Konsistenz generierten Lösungen. Allerdings sind die Voraussetzungen zur Herstellung von Box-Konsistenz durch numerische Verfahren strenger und die Ergebnisse weniger präzise als 3B-konsistente Lösungen vgl. Collavizza et al., 1998, S. 158; Collavizza et al., 1999, S. 224; Sam-Haroud, 1995, S. 31.

Fußnoten

...^5.107

Die Umformung gestaltet sich trivial, indem jeweils die rechte Seite von der linken Seite einer Gleichung bzw. Ungleichung subtrahiert und der resultierende Term gleich 0 gesetzt wird.