ECAI 2004 Conference Paper

[full paper]

Boosting systematic search by weighting constraints

Frederic Boussemart, Fred Hemery, Christophe Lecoutre, Lakhdar Sais

In this paper, we present a dynamic and adaptive variable ordering heuristic which guides systematic search toward inconsistent or hard parts of a Constraint Satisfaction Problem (CSP). This generic heuristic, denoted wdeg, is able to exploit information about previous states of the search process whereas traditional dynamic ones only exploit information about the current state. Intuitively, wdeg avoids some trashing by first instantiating variables involved in the constraints that have frequently participated in dead-end situations. Such information is recorded by associating a weight with each constraint. This weight is increased whenever the associated constraint is violated during search. The extensive experiments that we have conducted prove that our approach is the most efficient current one with respect to significant and large classes of academic, random and real-world instances.

Keywords: constraint satisfaction, systematic search, variable ordering heuristic

Citation: Frederic Boussemart, Fred Hemery, Christophe Lecoutre, Lakhdar Sais: Boosting systematic search by weighting constraints. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.146-150.