A compression algorithm to improve generalized hypertree decomposition-based solving approaches for large extensional non binary CSP

ABSTRACT. Many approaches exploiting Generalized Hypertree Decomposition are proposed in the literature for solving extensional Constraint Satisfaction Problems on finite domains. The most recent one, called FC-GHD, combines both the merits of an enumerative search algorithm which is memory efficient with those of the Hypertree Decomposition which is time efficient. Although FC-GHD is proved to be efficient, some large instances, however, remain unresolved because of the memory fault problem. This present article proposes to enhance the FC-GHD method with the notion of compressed table constraints to deal with memory explosion problems. This leads to a new compressed enumerative algorithm called CFC-GHD powerful when processing generalized hypertree decompositions. This paper describes this algorithm and presents the results obtained with this new approach. The experiments which were carried out validate the method from a practical viewpoint.