Generalized Hypertree Decomposition for solving non binary CSP with compressed table constraints

Habbas, Zineb; Amroun, Kamal; Singer, Daniel

RAIRO - Operations Research - Recherche Opérationnelle, Tome 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.

Classification : 68T20
Mots clés : Constraint Satisfaction Problems, Generalized Hypertree Decomposition, compressed table constraints

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.