SOLVING NON BINARY CONSTRAINT SATISFACTION PROBLEMS WITH DUAL BACKTRACKING ON HYPERTREE DECOMPOSITION

Zineb Habbas, Kamal Amroun, Daniel Singer

2011

Abstract

Solving a CSP (Constraint Satisfaction Problem) is NP-Complete in general. However, there are various classes of CSPs that can be solved in polynomial time. Some of them can be identified by analyzing their structure. It is theoretically well established that a tree (or hypertree) structured CSP can be solved in a backtrack-free way leading to tractability. Different methods exist for converting CSPs in a tree (or hypertree) structured representation. Among these methods Hypertree Decomposition has been proved to be the most general one for non-binary CSPs. Unfortunately, in spite of its good theoretical bound, the unique algorithm for solving CSP from its hypertree structure is inefficient in practice due to its memory explosion. To overcome this problem, we propose in this paper a new approach exploiting a Generalized Hypertree Decomposition. We present the so called HD DBT algorithm (Dual BackTracking algorithm guided by an order induced by a generalized Hypertree Decomposition). Different heuristics and implementations are presented showing its practical interest.

Paper Citation

in Harvard Style

Habbas Z., Amroun K. and Singer D. (2011). SOLVING NON BINARY CONSTRAINT SATISFACTION PROBLEMS WITH DUAL BACKTRACKING ON HYPERTREE DECOMPOSITION . In Proceedings of the 3rd International Conference on Agents and Artificial Intelligence - Volume 1: ICAART, ISBN 978-989-8425-40-9, pages 146-156. DOI: 10.5220/0003184801460156

in Bibtex Style

@conference{icaart11,
author={Zineb Habbas and Kamal Amroun and Daniel Singer},
title={SOLVING NON BINARY CONSTRAINT SATISFACTION PROBLEMS WITH DUAL BACKTRACKING ON HYPERTREE DECOMPOSITION},
booktitle={Proceedings of the 3rd International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,},
year={2011},
pages={146-156},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0003184801460156},
isbn={978-989-8425-40-9},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 3rd International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,
TI - SOLVING NON BINARY CONSTRAINT SATISFACTION PROBLEMS WITH DUAL BACKTRACKING ON HYPERTREE DECOMPOSITION
SN - 978-989-8425-40-9
AU - Habbas Z.
AU - Amroun K.
AU - Singer D.
PY - 2011
SP - 146
EP - 156
DO - 10.5220/0003184801460156