On the Power of Restarts for CSP

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The use of restart techniques in solving Constraint Satisfaction Problems (CSPs) is considered of small importance for backtrack search algorithms. In this paper we propose to conduct a preliminary study on the impact of restarts in randomized backtrack search algorithms for solving CSPs. We show that the well-know n-queens problem has a heavy-tail distribution. We present empirical evidences that restarts can effectively improve the time to solve the n-queens problem. We implement a conflict-driven variable heuristic, and present empirical evidences that this heuristic effectively improve the time to solve the n-queens problem.
Original languageUnknown
Title of host publicationNONE
Pages7-12
Publication statusPublished - 1 Jan 2010
EventInternational Conference on Principles and Practices of Constraint Programming -
Duration: 1 Jan 2010 → …

Conference

ConferenceInternational Conference on Principles and Practices of Constraint Programming
Period1/01/10 → …

Cite this