Solving CSP is in general N P-Complete. However, there are various subsets of CSPs that can be solved in polynomial time. Some of them can be identified by analyzing their structure. Unfortunately the proposed methods for exploiting these structural proprieties are not efficient in practice. So exploiting these structural properties for solving CSPs is a crucial challenge. In this paper, we propose efficient algorithms which exploit these structural proprieties, for both sequential and parallel resolutions. Some experiments done on academic benchmarks show the efficiciency of our approach.
time assumptions. The experimental results outline the practical efficiency of this algorithm and its performances in term of space memory.
This paper is organized as follows : section 2 gives preliminaries of
constraint satisfaction problems and well known CSP decomposition methods
by developing more particulary the (generalized) hypertree decomposition
method which is the most general one. In section 3, we present our
sequential algorithm called S HBR (for Sequential Hash Based Resolution) which
solves the hypertree structured CSP and we give some experiments of our
proposition with respect to the algorithm proposed in [
The notion of Constraint Satisfaction Problem CSP was introduced by [
tion problem is defined as a 3-tuple P = hX; D; Ci where : X = fx1; x2; :::; xng is a set of n variables.
D = fd1; d2; :::; dng is a set of finite domains; a variable xi takes its values in its domain di.
C = fC1; C2; :::; Cmg is a set of m constraints. Each constraint Ci is a pair (S(Ci), R(Ci)) where S(Ci) µ X, is a subset of variables, called scope of Ci and R(Ci) ½ Qxk2S(C)i) dk is the constraint relation, which specifies the allowed values combinations.
A solution of a CSP is an assignment of values to variables which satisfies all constraints.
Definition 2. Hypergraph: The constraint hypergraph [
In this paper, hyperedges(H) is the set of the hyperedges of the
hypergraph H. If h is a hyperedge, then var(h) is the set of variables of h.
Definition 3. A join tree for a hypergraph H is a tree T whose nodes are
the hyperedges of H, such that, when a vertex v of H occurs in two
hyperedges e1 and e2 then v occurs in each node of the unique path connecting e1
and e2 in the tree T.
Definition 4. Hypertree: A hypertree for a hypergraph H is a triple
< T; Â; ¸ > where T = (N; E) is a rooted tree, and  and ¸ are labelling
functions which associate each vertex p 2 N with two sets Â(p) µ var(H)
and ¸(p) µ hyperedges(H). If T 0 = (N 0; E0) is a subtree of T, we define
Â(T 0) = Sv2N0 Â(v). We denote the set of vertices N of T by vertices(T)
and the root of T by root(T). Tp denotes the subtree of T rooted at the node p.
Proposition 1. A CSP whose structure is acyclic can be solved in
polynomial time [
The goal of all structural decomposition methods is to transform a CSP into an equivalent acyclic CSP which can be solved in polynomial time. A decomposition method D associates to each hypergraph H a parameter D-width called the width of H. The method D ensures that for a fixed k, each CSP instance with D-width · k is tractable and then can be solved in polynomial time. Among these methods, the generalized hypertree decomposition (GHD) dominates all the other structural decomposition methods. In the next paragraph, we present the (generalized) hypertree decomposition method.
Definition 5. A generalized hypertree decomposition [
A hypertree decomposition of a hypergraph H =< V; E >, is a generalized hypertree decomposition HD =< T; Â; ¸ > which additionally satisfies the following special condition : For each vertex p 2 vertices(T ), var(¸(p)) T Â(Tp) µ Â(p).
The width of a (generalized) hypertree decomposition < T; Â; ¸ > is maxp2vertices(T )j¸(p)j. The (generalized) hypertree width (g)hw(H) of a hypergraph H is the minimum width over all its (generalized) hypertree decompositions.
A hyperedge h of a hypergraph H = hV; Ei is strongly covered in HD = hT ; Â; ¸i if there exists p 2 vertices(T ) such that the vertices in h are contained in Â(p) and h 2 ¸(p). A (generalized) hypertree decomposition HD = hT ; Â; ¸i of H = hV; Ei is called complete if every hyperedge h of H is strongly covered in HD.
The sequential resolution of a CSP represented by its hypertree
decomposition is given by the following algorithm [
1: Input : HD = hT ; Â; ¸i 2: step1: complete the hypertree decomposition HD 3: step2: Solve each ¸-term using multi-join operation. 4: step3: Solve the resulting CSP using semi-join operation. 5: Output: A solution of the given problem.
The second step consists in Solving each sub-problem represented as the ¸-term in each node of the hypertree. As a result, we have a new hypertree whose the ¸-terms are replaced by a unique constraint relation Rp corresponding to the projection on the variables in Â(p) of the join of the constraint relations in ¸(p). More formally Rp = (./t2¸(p) t)[Â(p)]. This operation is expensive. The third step consists in semi-join operation which is an other expensive operation. 3.2
Some notations : #i represents the intersection variables of the constraint Ci with the set of all variables in the union of Cj where j < i in a given order. HT i is the hash table associated to Ri.
The S HBR for Sequential Hash Based Resolution algorithm, is
formally presented by Algorithm 2. It proceeds in two steps : The SP HBR
for Sub Problem Hash Based Resolution algorithm (lines 3 to 6 ) is the
optimization of the join operation. The A HBR for (Acyclic Hash Based
Resolution) algorithm (line7) is an optimization of the classical Acyclic
solving algorithm [
We now give more details about SP HBR and A HBR algorithms. a) SP HBR algorithm: The result of the SP HBR execution is a join-tree whose every node n contains only one table Rn composed of the tuples satisfying all sub-problems constraints. Nodes of this join-tree are represented as follows: Rn = hÂ(p); Hrel(p)i where Â(p) is the set of variables of the node p, and Hrel(p) is the constraint relation generated by the join operation. Additionally, for the leaves nodes, Hrel(p)’s tuples are hashed on intersection variables with the parent node of p. This algorithm decomposes each node of the join tree into connected components. Then it applies the join operation algorithm for each component using the hash join Algorithm 2 Sequential hash Based Resolution(S HBR) 1: Input: a hypertree < T ; Â; ¸ > of a hypergraph < H = V; E > where T is a tree, Â associates to each t of T a set of nodes Â(t) ½ V , and ¸, a set of arcs ¸(t) ½ E 2: Output : A solution. 3: Step1: 4: for each node n of T do 5: Apply the SP HBR algorithm on the node n. 6: end for 7: Step2: Apply A HBR algorithm on T . principle. For doing that, we establish an order among relations in the same component. Then, we hash each relation Ri of the constraint Ci, except the first one, on intersection variables with the relations of the constraints that are before Ci in this order. The join operation is applied using the Join procedure. These procedures cannot be described in this paper for restricted space reason. We illustrate SP HBR by the following example. Example 1. We consider a node p of a hypertree HD labelled as follows: ¸(p) = fC1; C2; C3; C4; C5; C6g, with: S(C1) = fa; b; cg, S(C2) = fi; jg, S(C3) = fa; dg, S(C4) = fd; b; f g, S(C5) = ff; gg, S(C6) = fi; kg.
There are two connected components R1 = fC1; C3; C4; C5g and R2 = fC2; C6g. According to the order of the constraints in each component, we have: #3 = S(C3) \ S(C1) = f g
a , #4 = S(C4) \ fS(C1) [ S(C3)g = fb; dg, #5 = S(C5) \ fS(C1) [ S(C3) [ S(C4)g = ff g, #6 = S(C6) \ S(C2) = fig.(if C is a hyperedge, then S(C) denotes the scope of C).
Therefore, for the first component, the R3’s tuples will be hashed on the set of intersection variables #3 = fag, those of R4 and R5 on, respectively, #4 = fb; dg and #5 = ff g. For the second component, the tuples of R6 will be hashed on #6 = fig. After computing a cartesian product of the components, the resulting tuples t are hashed according to the intersection variables with the parent node of p, if p is a leaf. So, t will be ready for the semi-join operation in A-HBR algorithm. We do not add t to its related partition P unless if P = Á. Thus, we will have one and only one tuple in each partition by eliminating the duplicated tuples. This elimination has no impact on the resolution because, for the A-HBR algorithm, each parent node is filtered on its sons 1. Moreover, we are interested to get only one solution for the CSP.
b) The A HBR algorithm: The A HBR algorithms tests the consistency of a constraint acyclic network and generates a solution if it exists. 1It is sufficient to have only one tuple by partition in the son node relations. This algorithm takes the hypertree resulting from the SP HBR algorithm as its input. The A HBR algorithm (see. Algorithm 3 ) proceeds in two steps: the CONTRACT step and the S SEARCH step. The first step contracts the deep-rooted hypertree HT . A semi-join operation is associated to each contraction operation. The result is a directional from root toward leaves arc consistent hypertree HT 0 (line 3). The second step is the solution search operation, which develops the solution from the HT 0’s root to leaf nodes (line 4).
Algorithm 3 Acyclic Hash Based Resolution algorithm (A HBR) 1: Input: A hypertree HT = hT ; Â; ¸i 2: Output : Determine a directional arc consistent and generate a solution. 3: HT 0 = CONTRACT (HT ) 4: S SEARCH (HT 0),
The CONTRACT algorithm strengths the directional arc consistency of the input hypertree. Given a hypertree, a contraction operation is realized between each leaf node and its parent. For each contraction operation we hash each tuple t of a parent node (p) relation on intersection variables with its sons leaves nodes ai. We denote hi the hashed values. If ai’s hash tables partitions related to hi are not empty , we hash t on intersection variables of p with its parent node and save it. Otherwise, we eliminate t. The leaves nodes ai are marked and considered as pruned. We make the same with the obtained hypertree, and so on, until all the nodes, excepted the root, will be marked. The final result of the contraction operation of a parent node p with its sons leaves nodes, is a node p0 = hÂ(p0); Hrel(p0)i, whose relation is arc consistent with those of the son nodes relations, and hashed on the intersection variables of p with its parent node. If the hashed relation Hrel(p0) is empty, the problem has no solution.
The S SEARCH algorithm is a classical Backtrack free algorithm applied to the directional arc consistent hypertree resulting from the CONTRACT algorithm execution. 3.3
The complexity of the SP HBR algorithm is Where r is the the maximum relation size, h is the hypertree width, P is the maximum number of tuples in the partition of hashing on the variables of # (# represents the intersection variables of Ci with all variables in Cj where j < i ). For the A HBR algorithm, its complexity is O(nP 2). Where n is h¡1 X(r ¤ P i) i=1 the number of constraints in the obtained CSP. But in our case, we have only one tuple by partition, so the complexity of A HBR algorithm is only O(n). 3.4
We have implemented the S HBR algorithm and the basic algorithm [
n X((xi + 1) ¤ 10ln(f(t))+1) i=1 (2) We observe that S-HBR clearly improves the B A algorithm in terms of CPU time for all the instances.
The S HBR algorithm gets more better results for the instances which have large relations, because it browses only a sub- part of the relation rather than the totality one as in B A. 4
In this section, we introduce a parallel version of our previous sequential algorithm S HBR. We called it P HT R for Parallel Hypertree Resolution algorithm and it is described by the algorithm 4. This algorithm uses both pipeline technique and the parallel tree contraction technique. The pipeline avoids the storage of intermediate results so it reduces the memory space explosion. The parallel tree contraction is the most well known adapted approach for the semi-join operation. However the known parallel 2http://www.cril.univ-artois.fr/ lecoutre/research/benchmarks/benchmarks.html 3http://www.cs.rpi.edu/ puninj/XGMML/GML-XGMML/gml-parser.html 4http://www.cril.univ-artois.fr/ roussel/CSP-XML-parser/ Name 3-insertions-3-3 domino-100-100 domino-100-200 domino-100-300 series-7 hanoi-7 haystacks-06 haystacks-07 langford-2-4 Renault bf-1355-e-63 bf-1355-g-63 bf-2670-b bf-2670-c tree contraction considers at each iteration, for each parent node with only one son node leaf. To increase the parallelism degree in this operation, we developed a new alternative of this technique, based on partitioning the parent node relation (the critical resource) between all processors, which allows an asynchronous updating.
The P HT R(algorithm 4) procedure proceeds in two steps. The first one concerns the parallel resolution of sub-problems using the P SBR algorithm (line 4). The second step is the resolution of the whole problem. It is performed using the P Solving algorithm (line 6).
Algorithm 4 P HT R (Parallel HyperT ree Resolution) algorithm 1: Input: a hypertree hT ; Â; ¸i of a hypergraph H = (V(H); E (H)) 2: Output : The solution of the problem 3: for each node n of T in parallel do 4: P SBR (n) // Apply the P SBR algorithm on the node n. 5: end for 6: P Solving(T’) // Apply P Solving algorithm on T 0 (T 0 is the obtained hypertree in the step 3). 4.1
The P SBR for Parallel Sub Problem Resolution algorithm uses the hash technique. The P SBR algorithm proceeds as the SP HBR algorithm. After establishing an order on the constraints, it builds a pipeline line composed of join operators whose the first relation is the probe relation and the remaining ones are build relations. The join operation is performed according to the hash pipelined join principle. Thus, each build relation is hashed on its intersection variables (#i) with the union of the previous relations. The parallelism in this algorithm is provided by the Pipeline. At each level of the pipeline corresponds a join operation with two operands. The first one is R1 (the probe relation) for the first operator, Rtmp[i ¡ 1] for the ith operator. The second one is the build relation Ri for the ith operator. We make a join operation between each tuple of the first operand and all the tuples of the second operand. The obtained tuples from the ith operator are saved in the temporary relation of (Rtmp[i + 1]) of the following operator. 4.2
P Solving algorithm is the parallel version of A HBR algorithm. It consists in two operations, P CON T RACT (for Parallel CONTRACT), and P S SEARCH (for Parallel SEARCH ). The first operation concerns the parallelization of the CONTRACT operation, while the second one corresponds to the parallel version of the S SEARCH operation.
1: Input: A join tree T . 2: Output : The solution for the problem. 3: T 0 = P CON T RACT (T ).
4: P S SEARCH(T 0). 4.2.1
The P CON T RACT operation strengths the directional arc consistency in
the input hypertree. It is based on two operations, P RAKE (for Parallel
RAKE), and P COM P RESS (for Parallel COMPRESS ), where RAKE
and COM P RESS are the basic operations of a parallel tree contraction [
P RAKE operation: is based on the fact that the existence of only one resource is the reason of the sequential execution. This resource is the parent node relation. This resource must be manipulated simultaneously by all processors. Therefore, it must be shared between them. Thus, this technique consists in partitioning the parent relation between all processors which compute the semi-join operation of this last relation with its son nodes relations. These partitions are manipulated periodically between processors.
P COM P RESS operation : is a pipelined execution of COMPRESS operation. It is applied on a sequence of nodes or a chain. Let fn1; n2; :::; nj g be a chain of a tree T where ni+1 is the ni’s only son, the application of P COM P RESS to this chain results in a new tree contracted T 0 in which the node n1 is transformed thus: ² ÂT 0 (n1) = ÂT (n1) ² HrelT 0 (n1) = ΠÂ(n1)(HrelT (n2) ./ HrelT (n3) ./ ¢ ¢ ¢ ./ HrelT (nj )).
It makes a pipeline of join operations between the chain’s nodes, and at each time when it takes a tuple from the probe relation, it joins it with all tuples of the corresponding partition in the hash table of the build relation. Then it communicates it to the probe relation of the next operator. After the execution of the last operator, it projects the tuples results on the variable set  of each node of the chain, it hashes it on the intersection variables of each node with its parent node, and puts the tuple result in the corresponding node relation. P S SEARCH algorithm is the parallel version of S SEARCH algorithm. It works in the same way, except that, each time, after taking a tuple from a parent node, the research of corresponding tuples in the son nodes is made in parallel. For a binary hypertree, the complexity of the P SBR algorithm is O(r ¤ P h¡1) (3) using O(h) operations in a PRAM of type EREW. r is the the maximum relation size, h is the hypertree width, P is the maximum number of tuples in the partition of hashing on the variables of # (# represents the intersection variables of Ci with all variables in Cj where j < i ). For the P Solving algorithm, its complexity is O(log n2 ) using O(n) operations. n is the hypertree size (number of nodes). 5
We have developed a simulation model for P SBR and P Solving algorithms based on logical time assumptions. 5.1
Our system is composed of simple modules described as classical sequential programs, which are collected and executed in a parallel way by the simulator. A module is the set of operations performed by a processor we called a process. For the internal working of a process, we split operations that can be performed in three main types : Reading a tuple, Searching in hash tables including the tuples join operation and Writing a result tuple. These operations are executed sequentially between them and in parallel with those of the other processes. Each process explores the maximum of potential parallelism if its environment (its input variables) do not conflict during the other process execution. For a pipeline execution, if the processes are not adjacent, there is no conflict. Otherwise, we use the semaphore mechanism to synchronize them. 5.2
Each operation or each event is performed in an interval of time and the simulator must therefore keep a logical time counter. The asked question is : When we increment this counter, and what is the relation between this counter and the events execution time (physical counter)? We make a stepby-step simulation so that for each step (logical time unit) all operations which can be performed at the same time start as follows : 1. The simulator executes all processes and it increments the logical time counter at each iteration. 2. For all processes that are not in conflict, the simulator increments the physical time counter. 3. After a logical time step, the simulator updates all the shared variables. 4. It restarts a new step by considering the new variable states. 5.3
We developed a simulation of P HT R algorithm in order to check: first, if
it gives good temporal and spatial complexities and second, if the new
approach of parallel tree contraction proposed in this paper can be considered
as an interesting alternative of the one considered in [
The simulation has been accomplished on a PC under Linux 6.0.52 version with CPU Intel Pentium IV 2.4 GHz and 512 Mb of RAM. We use a set of benchmarks CSP which exist in the literature. We take the average of the data obtained after several executions. In our results, jV j, jEj et jrj represent respectively the variables number, the constraints number and the maximum relations cardinality. Nd, Nf and HT W are respectively, the nodes number, the leaf nodes number and the hypertree width. Np represents the processors number and N bS represents the number of pipeline stages.
In order to be hardware independent, measure units are Tuple for space and Operation (Reading, Searching or Writing) for time. 5.4
The table 2 presents the space memory required for a pipeline (R P SBR) and no pipeline (R join) execution of the join operations for different CSP instances (consistent and inconsistent).
N N W > 2 denotes the number of nodes in the hypertree with width more than 2. We observed that the gain in space memory is very important in instances for which the pipeline executions number (NNW>2) is important (haystacks-07 ). We also observed that the gain depends on the number of nodes in hypertree (mug-100-25-4 ). It is also proportional to the number of tuples by relation. As the two factors that influence on CSP problems complexity are the constraints relations size, and the structural decomposition width, and in order to estimate the contribution of P SBR, we evaluate in figure 1, in (a) and (b), the P SBR algorithm behavior w.r.t respectively the constraints relations size and the stages number in pipeline for two classes of CSP problems: aim-100-6 and full-Insertion.
N.B: P SBR algorithm forms a pipeline in each node of the hypertree. So, the stages number in the pipeline is the number of constraints in the node minus one.
Spatial gain (a)
Spatial gain (b) Relations size
Pipeline stages number
P RAKE tries to optimize the CPU time of the whole problem. We present here a simulation of this operation by computing its efficiency Ef f =
Ts NP ¤Tp where NP is the processors number and Ts(reps. Tp) the time of sequential (reps. parallel) resolution of the sub- hypertree.
Speed up
Theoritical
P-RAKE
Nbr of processors
The P RAKE algorithm speedup is presented in Figure 2. It is obvious that it is close to theoretical speedup (linear).
Before comparing P Solving with A HBR, it seems natural to compare P CON T RACT algorithm with an algorithm applying the tree contraction.
Name hayst06 dom200 hanoi-6 mug25-4 myc-3-4 myc-4-4 Renault series-6 hole-6
Nc represents the number of contraction operations performed and T the computational time. We have considered 1000 operations as a measure unit. Table 4 gives the CPU time of both A HBR algorithm and P T AC algorithm (CONTRACT operation) and the one of P Solving (P CON T RACT operation). It results that P CON T RACT generates a gain in temporal complexity inversely proportional to the number of contractions. More the number of the leaf nodes contracted is big more the number of contraction is less and more the gain in time is important (myc-3-4, Renault and hole-6 ), and vice versa, which is the case for hayst06 and mug25-4. We can also remark for the problem hole-6, the CPU time gain (29 instead of 1201) is considerable. This is due to the fact the hypertree is contracted on only one step, instead of taking 81 steps. In this paper, we have presented sequential and parallel algorithms to solve CSPs by exploiting their structural properties. The algorithms exploit the hash technique. For the sequential algorithm, we have done some experiments on benchmarks from the literature and the results we have obtained are promising. Good results are observed when the number of tuples of relations is important. The parallel algorithm is based on the notion of pipeline and parallel tree contraction which is a parallel version of the well known tree contraction. We performed simulations on some benchmarks and the results are very good. Future works include the execution of our parallel algorithm on a parallel machine.