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.

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.

Received:
Accepted:
DOI: 10.1051/ro/2015017
Classification: 68T20
Keywords: Constraint Satisfaction Problems, Generalized Hypertree Decomposition, compressed table constraints
Habbas, Zineb 1; Amroun, Kamal 2; Singer, Daniel 1

1 LCOMS EA 7306, University of Lorraine, Metz, France.
2 LIMED, Faculté des Sciences Exactes, Université de Bejaia, 06000 Bejaia, Algeria.
@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.

D. Cohen, P. Jeavons and M. Gyssens, A unified theory of structural tractability for Constraint Satisfaction Problems. J. Comput. System Sci. 74 (2008) 721–743. | DOI | MR | Zbl

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

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.

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

E.C. Freuder, 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.

G. Gottlob and M. Samer, A Backtracking-based algorithm for hypertree decomposition. ACM J. Exp. Algorithmics (JEA) 13 (2009). | MR | Zbl

G. Gottlob, N. Leone and F. Scarcello, A comparison of structural CSP decomposition methods. Artif. Intell. 124 (2000) 243–282. | DOI | MR | Zbl

G. Gottlob, N. Leone and F. Scarcello, Hypertree decompositions and tractable queries. J. Comput. System Sci. 64 (2002) 579–627. | DOI | MR | Zbl

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

G. Gottlob, Z. Miklos and T. Schwentick, Generalized hypertree decompositions: NP – hardness and tractable variants. J. ACM 56 (2009). | DOI | MR | Zbl

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

M. Gyssens, P.G. Jeavons and D.A. Cohen, Decomposing constraint satisfaction problems using database techniques. Artif. Intell. J. 66 (1994) 57–89. | DOI | MR | Zbl

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

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

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

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.

T. Kam, T. Villa, R.K. Brayton and A.L. Sangiovanni-Vincentelli, Multivalued decision diagrams: Theory and applications. Int. J. Multiple Valued Logic 4 (1998) 9–62. | MR | Zbl

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.

C.K. Kenil Cheng and R.H.C. Yap, 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

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

C. Lecoutre, 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).

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

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

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).

N. Robertson and P.D. Seymour, Graph minors .II. algorithmic aspects of treewidth. J. Algorithms 7 (1986) 309–322. | DOI | MR | Zbl

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.

J.R. Ullmann, 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: