Search Ordering Heuristics for Restarts-based Constraint Solving

Margarita Razgon, Barry O'Sullivan, Gregory Provan

Over the past decade impressive advances have been made in solving Constraint Satisfaction Problems by using of randomization and restarts. In this paper we propose a new class of variable and value ordering heuristics based on learning from nogoods without storing them. We show empirically that these heuristics dramatically improve the performance of restarts-based constraint solving.

Subjects: 15.2 Constraint Satisfaction; 15.7 Search

Submitted: Feb 9, 2007

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.