On the Power of Restarts for CSP

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

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