Using nogoods information from restarts in domain-splitting search

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

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