Using nogoods information from restarts in domain-splitting search

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

Abstract

The use of restart techniques associated with learning nogoods in solving Constraint Satisfaction Problems (CSPs) is starting to be considered of major importance for backtrack search algorithms. In a backtracking search algorithm, with domain-splitting branching, nogoods can be learned from the last branch of the search tree, immediately before the restart occurs. This type of nogoods, named domain-splitting (ds) nogoods, is still not proven to be effective in solving CSP. However, information retained within ds-nogoods can be used in heuristic decisions. Inspired by activity-based heuristics of SAT solvers, we propose to include ds-nogood information in the heuristic decision. Experimental results show that this allows some problems to be solved more efficiently.
Original languageUnknown
Title of host publicationNONE
Pages9 pages
Publication statusPublished - 1 Jan 2012
EventNogood Learning and Constraint Programming Workshop (NGL) -
Duration: 1 Jan 2012 → …

Conference

ConferenceNogood Learning and Constraint Programming Workshop (NGL)
Period1/01/12 → …

Cite this