Solving non-binary constraint satisfaction problems using GHD and restart.

Abstract

The non-binary instances of the Constraint Satisfaction Problem (CSP) could be efficiently solved if their constraint hypergraphs have small generalized hypertree widths. Several algorithms based on Generalized Hypertree Decomposition (GHD) have been proposed in the literature to solve instances of CSPs. One of these algorithms, called Forward Checking based on Generalized Hypertree Decomposition (FC-GHD+NG+DR), combines the advantages of an enumerative search algorithm with those of Generalized Hypertree Decomposition. However, like all structural decomposition methods, FC-GHD+NG+DR depends on the order in which the clusters are processed. In this paper, we propose a new version of the FC-GHD+NG+DR algorithm with a restart technique that allows changing the order of the nodes of GHD to improve performance. The experiments carried out are very promising, particularly on the satisfiable instances where we achieved better results using the restart method in 52.63% of the modified Renault satisfiable benchmarks and an average time resolution of  for the normalized Pret and normalized Dubois benchmarks.