HYPERTREE DECOMPOSITION FOR SOLVING CONSTRAINT SATISFACTION PROBLEMS

Abdelmalek Ait-Amokhtar, Kamal Amroun, Zineb Habbas

2009

Abstract

This paper deals with the structural decomposition methods and their use for solving Constraint Satisfaction problems (CSP). mong the numerous structural decomposition methods, hypertree decomposition has been shown to be the most general CSP decomposition. However so far the exact methods are not able to find optimal decomposition of realistic instances in a reasonable CPU time. We present Alea, a new heuristic to compute hypertree decomposition. Some experiments on a serial of benchmarks coming from the literature or the industry permit us to observe that Alea is in general better or comparable to BE (Bucket Elimination), the best well known heuristic, while it generally outperforms DBE (Dual Bucket Elimination), another successful heuristic. We also experiment an algorithm (acyclic solving algorithm) for solving an acyclic CSP obtained by using the heuristic Alea. The experimental results we obtain are promising comparing to those obtained by solving CSP using an enumerative search algorithm.

Paper Citation

in Harvard Style

Ait-Amokhtar A., Amroun K. and Habbas Z. (2009). HYPERTREE DECOMPOSITION FOR SOLVING CONSTRAINT SATISFACTION PROBLEMS . In Proceedings of the International Conference on Agents and Artificial Intelligence - Volume 1: ICAART, ISBN 978-989-8111-66-1, pages 85-92. DOI: 10.5220/0001662400850092

in Bibtex Style

@conference{icaart09,
author={Abdelmalek Ait-Amokhtar and Kamal Amroun and Zineb Habbas},
title={HYPERTREE DECOMPOSITION FOR SOLVING CONSTRAINT SATISFACTION PROBLEMS},
booktitle={Proceedings of the International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,},
year={2009},
pages={85-92},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0001662400850092},
isbn={978-989-8111-66-1},
}

in EndNote Style

TY - CONF
JO - Proceedings of the International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,
TI - HYPERTREE DECOMPOSITION FOR SOLVING CONSTRAINT SATISFACTION PROBLEMS
SN - 978-989-8111-66-1
AU - Ait-Amokhtar A.
AU - Amroun K.
AU - Habbas Z.
PY - 2009
SP - 85
EP - 92
DO - 10.5220/0001662400850092