A compressed Generalized Hypertree Decomposition-based solving technique for non-binary Constraint Satisfaction Problems

摘要

In theory, an algorithm exists for solving non-binary Constraint Satisfaction Problems (CSPs) by using a Generalized Hypertree Decomposition (GHD). However in practice, this algorithm called GLS (due to Gottlob et al.) which is based on the Join Acyclic Solving (JAS) algorithm is inefficient when dealing with large instances because of memory fault or time out problem. In our research works, several approaches have been developed in order to exploit GHD for a practical resolution of extensional non-binary CSPs. One of them, called Forward-Checking based on Generalized Hypertree Decomposition (FC-GHD) algorithm, combines both the merits of an enumerative search algorithm which is memory efficient with those of the Generalized Hypertree Decomposition which is time efficient. In this present article, compressed table constraints are used with FC-GHD in order to study the benefit of such a technique for large CSPs. The resulting algorithm called CFC-GHD is described in this paper together with two improved extended versions of it called CFC-GHD+NG (for structural NoGoods) and CFC-GHD+NG+DR (for Dynamic Reordering of subtrees). Although the new algorithms present computation times comparable to those obtained with the non compressed versions of the algorithms, the new approach is a better candidate for solving optimization problems and more specifically multi-objective ones which involve taking decisions over several possible solutions.