Durch die Repräsentation als -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,
-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
-Konsistenz.
-relational consistency
garantiert, dass für jedes Triplett ternärer Relationen
,
und
über
zwei gemeinsame Variablen,5.112 bei einer konsistenten Belegung von
,
,
die Variablen
,
so belegt werden können, dass die
Relationen
,
und
erfüllt werden. Für jedes konvexe,
ternäre Constraint-Netz ist
-relational
consistency äquivalent mit globaler Konsistenz. Sam-Haroud und
Faltings verallgemeinern dieses Prinzip zur
(r,r-1)-relational consistency fü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. -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
bzw.
-convexity
bezieht sich auf die Konvexität der Projektionen von
Verbindungen zwischen Punkten aus einer Relation
, die sich
parallel zur Achse von
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
. Auch das Prinzip der axis-convexity für
binäre Constraints wird von Sam-Haroud und Faltings zur sog.
-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
-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