Genetic algorithms for generalised hypertree decompositions

Nysret Musliu and Werner Schafhauser

European Journal of Industrial Engineering, 2007, vol. 1, issue 3, 317-340

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. (search for similar items in EconPapers)
Date: 2007
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=14690 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:eujine:v:1:y:2007:i:3:p:317-340

Access Statistics for this article

More articles in European Journal of Industrial Engineering from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().