Title: Genetic algorithms for generalised hypertree decompositions

Authors: Nysret Musliu, Werner Schafhauser

Addresses: Institute of Information Systems, Database and Artificial Intelligence Group (DBAI), Vienna University of Technology, Favoritenstrasse 9, Wien 1040, Austria. ' Institute of Information Systems, Database and Artificial Intelligence Group (DBAI), Vienna University of Technology, Favoritenstrasse 9, Wien 1040, Austria

Abstract: Many practical problems in mathematics and computer science may be formulated as Constraint Satisfaction Problems (CSPs). Although CSPs are NP-hard in general, it has been proven that instances of CSPs may be solved efficiently, if they have generalised hypertree decompositions of small width. Unfortunately, finding a generalised hypertree decomposition of minimum width is an NP-hard problem. Based on a Genetic Algorithm (GA) for tree decompositions we propose two extensions searching for small-width generalised hypertree decompositions. We carry out comprehensive experiments to obtain suitable operators and parameter settings and apply each GA to numerous benchmark examples for tree and generalised hypertree decompositions. Compared to the best solutions known from literature our GAs were able to return results of equal quality for many benchmark instances and even for some benchmarks improved solutions were obtained. [Received 6 February 2007; Revised 21 May 2007; Accepted 22 May 2007]

Keywords: constraint satisfaction problems; CSPs; structural decomposition methods; tree decompositions; generalised hypertree decompositions; genetic algorithms; GAs.

DOI: 10.1504/EJIE.2007.014690

European Journal of Industrial Engineering, 2007 Vol.1 No.3, pp.317 - 340

Published online: 25 Jul 2007 *

Full-text access for editors Access for subscribers Purchase this article Comment on this article