Generalized hypertree decomposition for solving non binary CSP with compressed table constraints.

*(English)*Zbl 1357.68207Summary: 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.

##### MSC:

68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |

##### Keywords:

constraint satisfaction problems; generalized hypertree decomposition; compressed table constraints##### Software:

STR2
PDF
BibTeX
Cite

\textit{Z. Habbas} et al., RAIRO, Oper. Res. 50, No. 2, 241--267 (2016; Zbl 1357.68207)

Full Text:
DOI

##### References:

[1] | 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 1192.05104 |

[2] | 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. |

[3] | 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. |

[4] | 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. · Zbl 1151.68640 |

[5] | R. Dechter and J. Pearl, Tree clustering for constraint networks. J. Artif. Intell.38 (1989) 353-366. · Zbl 0665.68084 |

[6] | 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. |

[7] | E.C. Freuder, A sufficient condition for Backtrack-free search. J. ACM29 (1982) 24-32. · Zbl 0477.68063 |

[8] | E.C. Freuder, A sufficient condition for backtrack-bounded search. J. ACM32 (1985) 755-761. · Zbl 0633.68096 |

[9] | 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. |

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

[11] | G. Gottlob, N. Leone and F. Scarcello, A comparison of structural CSP decomposition methods. Artif. Intell.124 (2000) 243-282. · Zbl 0952.68044 |

[12] | G. Gottlob, N. Leone and F. Scarcello, Hypertree decompositions and tractable queries. J. Comput. System Sci.64 (2002) 579-627. · Zbl 1052.68025 |

[13] | 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. · Zbl 1054.68044 |

[14] | G. Gottlob, Z. Miklos and T. Schwentick, Generalized hypertree decompositions: NP - hardness and tractable variants. J. ACM56 (2009). · Zbl 1325.68097 |

[15] | M. Grohe and D. Marx, Constraint Solving via Fractional Edge Covers. In Proc. of SODA 2006 (2006) 289-298. · Zbl 1192.68642 |

[16] | M. Gyssens, P.G. Jeavons and D.A. Cohen, Decomposing constraint satisfaction problems using database techniques. Artif. Intell. J.66 (1994) 57-89. · Zbl 0803.68090 |

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

[18] | L. Hyafil and R.L. Rivest, Constructing optimal binary decision trees is NP-complete. Inf. Process. Lett.5 (1976) 15-17. · Zbl 0333.68029 |

[19] | P. Jégou and C. Terrioux, Hybrid backtracking bounded by tree-decomposition of constraint networks. Artif. Intell. J.146 (2003) 43-75. · Zbl 1082.68803 |

[20] | 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. |

[21] | T. Kam, T. Villa, R.K. Brayton and A.L. Sangiovanni-Vincentelli, Multivalued decision diagrams: Theory and applications. Int. J. Multiple Valued Logic4 (1998) 9-62. · Zbl 1025.94515 |

[22] | G. Katsirelos and F. Bacchus, Generalized Nogoods in CSPs. In Proc. of AAAI’05, Pittsburgh (2005) 390-396. |

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

[24] | 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. Constraints15 (2010) 265-304. · Zbl 1204.68188 |

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

[26] | C. Lecoutre, STR2: optimized simple table reduction for table constraints. Constraints16 (2011) 341-371. · Zbl 1244.90232 |

[27] | A. Mackworth, On Reading Sketch Maps. In Proc. of IJCAI-77 (1977) 598-606. |

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

[29] | U. Montanari, Networks of constraints: fundamental properties and applications to pictures processing. Inf. Sci. J.7 (1974) 95-132. · Zbl 0284.68074 |

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

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

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

[33] | G. Pesant, A Regular Language Membership Constraint for Finite Sequences of Variables. In Proc. of CP’04 (2004) 482-495. · Zbl 1152.68573 |

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

[35] | N. Robertson and P.D. Seymour, Graph minors .II. algorithmic aspects of treewidth. J. Algorithms7 (1986) 309-322. · Zbl 0611.05017 |

[36] | M. Samer, Hypertree-Decomposition via Branch-Decomposition. In Proc. of IJCAI’05 (2005) 1535-1536. |

[37] | 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. |

[38] | J.R. Ullmann, Partition search for non binary constraint satisfaction. Inf. Sci. J.177 (2007) 3639-3678. · Zbl 1119.68446 |

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

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.