5.3.7.2 Erweiterungen des Ansatzes

Durch die Repräsentation als $2^k$-Baum können Constraints mit beliebiger Stelligkeit beschrieben werden. Die Komplexität steigt allerdings mit zunehmender Stelligkeit signifikant an, im worst-case exponentiell. Sam-Haroud und Faltings (1996a, S. 94 f.) weisen deshalb darauf hin, wie n-äre Constraints in ein System äquivalenter ternärer Constraints umgewandelt werden können, und behandeln in Folge ausschließlich binäre bzw. ternäre Constraints. Zur effizienteren Verarbeitung dieser Constraints wird von Sam-Haroud und Faltings (1996b, S. 413 ff.) eine neue Konsistenz eingeführt, $(3,2)$-relational consistency, die ausreichend ist, für ternäre Constraints globale Konsistenz zu garantieren, dabei allerdings weniger aufwendig ist, als die sonst benötigte strenge $5$-Konsistenz. $(3,2)$-relational consistency garantiert, dass für jedes Triplett ternärer Relationen $R_1(v_1,v_4,v_5)$, $R_2(v_2,v_4,v_5)$ und $R_3(v_3,v_4,v_5)$ über zwei gemeinsame Variablen,^5.112 bei einer konsistenten Belegung von $v_1$, $v_2$, $v_3$ die Variablen $v_4$, $v_5$ so belegt werden können, dass die Relationen $R_1$, $R_2$ und $R_3$ erfüllt werden. Für jedes konvexe, ternäre Constraint-Netz ist $(3,2)$-relational consistency äquivalent mit globaler Konsistenz. Sam-Haroud und Faltings verallgemeinern dieses Prinzip zur (r,r-1)-relational consistency für $r$-stellige Constraints bzw. Constraint-Gruppen.

Außerdem ist es möglich, die Konvexitätsbedingung auf eine partielle Konvexität abzuschwächen, so dass für eine größere Anzahl Problemstellungen bereits durch Pfadkonsistenz bzw. $(3,2)$-relational consistency globale Konsistenz erreicht werden kann. Weil die Voraussetzung von konvexen, non-disjunctive Constraints sehr streng ist, definieren Sam-Haroud und Faltings axis-convexity für binäre Constraints, eine schwächere Form von Konvexität, die ausreichend ist, globale Konsistenz sicherzustellen vgl. Sam-Haroud und Faltings, 1996a, S. 101 ff.; Sam-Haroud und Faltings, 1996b, S. 417 ff.. Axis-convexity bzgl. einer Variablen $v_k$ bzw. $(v_k)$-convexity bezieht sich auf die Konvexität der Projektionen von Verbindungen zwischen Punkten aus einer Relation $R$, die sich parallel zur Achse von $v_k$ befinden. Da axis-convexity ausschließlich die Konvexität der parallelen Verbindungen voraussetzt, ist diese Form weniger restriktiv als die Forderung nach allgemeiner Konvexität, d.h. von Projektionen beliebiger Verbindungen zwischen Punkten aus $R$. Auch das Prinzip der axis-convexity für binäre Constraints wird von Sam-Haroud und Faltings zur sog. $(v_1,\ldots,v_k)$-convexity für n-äre Constraints verallgemeinert.

Der Ansatz, die Berechnung von Lösungsräumen anstatt punktgenaue Lösungen konsequenter zu unterstützen, wird in diversen Veröffentlichungen weiter verfolgt (vgl. Vu et al., 2003c; Silaghi et al., 2001). In Anlehnung an die $2^k$-Baum-Methode wird dabei die Einteilung des Lösungsraums in drei Kategorien beibehalten. Zum Einsatz kommen außerdem erweiterte Splitting-Strategien, die zwischen Gleichheits- und Ungleichheits-Constraints unterscheiden und unterschiedliche Heuristiken einsetzen, sowie Kombinationen mit Verfahren zum Herstellen von Hull-Konsistenz zur konventionellen Einschränkung von Wertebereichen.^5.113

Fußnoten

...^5.112

Wobei $v_4$ und $v_5$ identisch sein können.

...^5.113

Für die Algorithmen von Silaghi et al. (2001) und Vu et al. (2003c) wird zum Herstellen von 3B-Konsistenz der ILOG Solver eingesetzt.