Storing Learnt (No)Goods in ROBDDs for Solving Structured CSPs

Karim Boutaleb, Philippe Jégou, Cyril Terrioux

It was shown that constraint satisfaction problems (CSPs) with a low width can be solved effectively by structural methods. In particular, the BTD method which exploits the concepts of goods and nogoods makes it possible to solve efficiently difficult instances. However, the memory space required for the storage of these (no)goods may make difficult or impossible the resolution of certain problems. We propose here to represent goods and nogoods with Binary Decision Diagrams (BDD). BDDs are data structures which efficiently represent informations in a compact and canonical form. Then, the practical interest of this trade-off which allows to save space memory to the detriment of time is assessed.

Subjects: 15.2 Constraint Satisfaction; 15.7 Search

Submitted: May 17, 2006

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.