Many real-world problems can be modelled as Constraint Satisfaction Problems (CSPs). Although CSP is NP-complete, it has been proved that non binary CSP instances may be efficiently solved if they are representable as Generalized Hypertree Decomposition (GHD) with small width. Algorithms for solving CSPs based on a GHD consider an extensional representation of constraints together with join and semi-join operations giving rise to new large constraint tables (or relations) needed to be temporarily saved. Extensional representation of constraints is quite natural and adapted to the specification of real problems but unfortunately limits significantly the practical performance of these algorithms. The present work tackles this problem using a compact representation of constraint tables. Consequently, to make algorithms compatible with this compact representation, new “compressed join” and “compressed semi-join” operations have to be defined. This last step constitutes our main contribution which, as far as we know, has never been presented. The correctness of this approach is proved and validated on multiple benchmarks. Experimental results show that using compressed relations and compressed operations improves significantly the practical performance of the basic algorithm proposed by Gottlob et al. for solving non binary CSPs with a Generalized Hypertree Decomposition.

Accepted:

DOI: 10.1051/ro/2015017

Keywords: Constraint Satisfaction Problems, Generalized Hypertree Decomposition, compressed table constraints

^{1}; Amroun, Kamal

^{2}; Singer, Daniel

^{1}

@article{RO_2016__50_2_241_0, author = {Habbas, Zineb and Amroun, Kamal and Singer, Daniel}, title = {Generalized {Hypertree} {Decomposition} for solving non binary {CSP} with compressed table constraints}, journal = {RAIRO - Operations Research - Recherche Op\'erationnelle}, pages = {241--267}, publisher = {EDP-Sciences}, volume = {50}, number = {2}, year = {2016}, doi = {10.1051/ro/2015017}, mrnumber = {3479867}, zbl = {1357.68207}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ro/2015017/} }

TY - JOUR AU - Habbas, Zineb AU - Amroun, Kamal AU - Singer, Daniel TI - Generalized Hypertree Decomposition for solving non binary CSP with compressed table constraints JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2016 SP - 241 EP - 267 VL - 50 IS - 2 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ro/2015017/ DO - 10.1051/ro/2015017 LA - en ID - RO_2016__50_2_241_0 ER -

%0 Journal Article %A Habbas, Zineb %A Amroun, Kamal %A Singer, Daniel %T Generalized Hypertree Decomposition for solving non binary CSP with compressed table constraints %J RAIRO - Operations Research - Recherche Opérationnelle %D 2016 %P 241-267 %V 50 %N 2 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ro/2015017/ %R 10.1051/ro/2015017 %G en %F RO_2016__50_2_241_0

Habbas, Zineb; Amroun, Kamal; Singer, Daniel. Generalized Hypertree Decomposition for solving non binary CSP with compressed table constraints. RAIRO - Operations Research - Recherche Opérationnelle, Volume 50 (2016) no. 2, pp. 241-267. doi : 10.1051/ro/2015017. http://archive.numdam.org/articles/10.1051/ro/2015017/

I. Adler, G. Gottlob and M. Grohe, Hypertree-width and related hypergraph invariants. In Proc. of the 3rd European Conference on Combinatorics, Graph Theory, and Applications (EUROCOMB’05), DMTCS Proceedings Series, vol. AE (2005) 5–10. | Zbl

A. Ait-Amokhtar, K. Amroun and Z. Habbas, Hypertree Decomposition for Solving Constraint Satisfaction Problems. In Proc. of International conference on Agents and Artificial Intelligence, ICAART’2009 (2009) 398–404.

C. Bessière and J.C. Régin, Arc Consistency for General Constraint Networks: Preliminary Results. In Proc. of the Sixtenteenth International Joint Conference on Artificial Intelligence (1997) 398–404.

A unified theory of structural tractability for Constraint Satisfaction Problems. J. Comput. System Sci. 74 (2008) 721–743. | DOI | MR | Zbl

, and ,Tree clustering for constraint networks. J. Artif. Intell. 38 (1989) 353–366. | DOI | MR | Zbl

and ,A. Dermaku, T. Ganzow, G. Gottlob, B. McMahan, N. Musliu and M. Samer, Heuristic Methods for Hypertree Decompositions. In Proc. of the 7th. Mexican Int. Conf. on Artificial Intelligence: Advances in Artificial Intelligence (2008) 1–11.

A sufficient condition for Backtrack-free search. J. ACM 29 (1982) 24–32. | DOI | MR | Zbl

,A sufficient condition for backtrack-bounded search. J. ACM 32 (1985) 755–761. | DOI | MR | Zbl

,I.P. Gent, C. Jefferson and P. Nightingale, Data Structures for Generalized arc Consistency for Extensional Constraints. In Proc. of AAAI’07 (2007) 191–197.

A Backtracking-based algorithm for hypertree decomposition. ACM J. Exp. Algorithmics (JEA) 13 (2009). | MR | Zbl

and ,A comparison of structural CSP decomposition methods. Artif. Intell. 124 (2000) 243–282. | DOI | MR | Zbl

, and ,Hypertree decompositions and tractable queries. J. Comput. System Sci. 64 (2002) 579–627. | DOI | MR | Zbl

, and ,Robbers, marshals, and guards: game theoretic and logical characterisations of hypertree width. J. Comput. System Sci. 66 (2003) 775–808. | DOI | MR | Zbl

, and ,Generalized hypertree decompositions: NP – hardness and tractable variants. J. ACM 56 (2009). | DOI | MR | Zbl

, and ,M. Grohe and D. Marx, Constraint Solving via Fractional Edge Covers. In Proc. of SODA 2006 (2006) 289–298. | MR | Zbl

Decomposing constraint satisfaction problems using database techniques. Artif. Intell. J. 66 (1994) 57–89. | DOI | MR | Zbl

, and ,P. Harvey and A. Ghose, Reducing Redundancy in The Hypertree Decomposition Scheme. In Proc. of ICTAI’03, Montreal (2003) 474–481.

Constructing optimal binary decision trees is NP-complete. Inf. Process. Lett. 5 (1976) 15–17. | DOI | MR | Zbl

and ,Hybrid backtracking bounded by tree-decomposition of constraint networks. Artif. Intell. J. 146 (2003) 43–75. | DOI | MR | Zbl

and ,P. Jégou, S.N. Ndiaye and C. Terrioux, Combined Strategies for Decomposition-based Methods for Solving CSPs. In Proc. of ICTAI’09 (2009) 184–192.

Multivalued decision diagrams: Theory and applications. Int. J. Multiple Valued Logic 4 (1998) 9–62. | MR | Zbl

, , and ,G. Katsirelos and F. Bacchus, Generalized Nogoods in CSPs. In Proc. of AAAI’05, Pittsburgh (2005) 390–396.

G. Katsirelos and T. Walsh, A Compression Algorithm for Large Arity Extensional Constraints. In Proc. of CP’07 (2007) 379–393.

An MDD-based generalized arc consistency algorithm for positive and negative table constraints and some global constraints. Constraints 15 (2010) 265–304. | DOI | MR | Zbl

and ,T. Korimort, Heuristic hypertree decomposition. Ph. D. thesis, Vienna University of Technology (2003).

STR2: optimized simple table reduction for table constraints. Constraints 16 (2011) 341–371. | DOI | MR | Zbl

,A. Mackworth, On Reading Sketch Maps. In Proc. of IJCAI-77 (1977) 598–606.

Z. Miklos, Understanding Tractable Decompositions for Constraint Satisfaction. Ph. D. thesis, University of Oxford (2008).

Networks of constraints: fundamental properties and applications to pictures processing. Inf. Sci. J. 7 (1974) 95–132. | DOI | MR | Zbl

,Genetic algorithms for Generalized hypertree decompositions. Eur. J. Ind. Eng. 1 (2005) 317–340. | DOI

and ,W. Pang and S.D. Goodwin, Constraint-directed backtracking. Vol. 1342 of Lect. Notes Comput. Sci. (1997) 47–56.

W. Pang and S.D. Goodwin, A graph based backtracking algorithm for solving general CSPs. Lect. Notes Comput. Sci. of AI (2003) 114–128. | MR

G. Pesant, A Regular Language Membership Constraint for Finite Sequences of Variables. In Proc. of CP’04 (2004) 482–495. | Zbl

J.-C. Régin, Improving the Expressiveness of Table Constraints. In Proc. of workshop ModRef 11 at CP’11 (2011).

Graph minors .II. algorithmic aspects of treewidth. J. Algorithms 7 (1986) 309–322. | DOI | MR | Zbl

and ,M. Samer, Hypertree-Decomposition via Branch-Decomposition. In Proc. of IJCAI’05 (2005) 1535–1536.

S. Subbarayan and H. Reif Anderson, Backtracking Procedures for Hypertree, Hyperspread and Connected Hypertree Decomposition of CSPs. In Proc. of IJCAI’07 (2007) 180–185.

Partition search for non binary constraint satisfaction. Inf. Sci. J. 177 (2007) 3639–3678. | DOI | MR | Zbl

,M. Yannakakis, Algorithms for Acyclic Database Schemes. In Proc. of VLDB’81. Edited by C. Zaniolo and C. Delobel, Cannes, France (1981) 82–94.

*Cited by Sources: *