A heuristic based on domain-splitting nogoods from restarts

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

Abstract

Inspired by Boolean Satisfiability Problems (SAT), Constraint Satisfaction Problems (CSP) are starting to use restart techniques associated with learning nogoods widely. Recent developments show how to learn nogoods from restarts and that these nogoods are of major importance when solving a CSP. Using a backtracking search algorithm, with domain-splitting branching, nogoods are learned from the last branch of the search tree, immediately before the restart occurs. This type of nogoods, named ds-nogoods, is still not proven to be effective in solving CSP. Nevertheless, information retained within dsnogoods can be used in heuristic decisions. Inspired by activity-based heuristics of SAT solvers, we propose and evaluate a variable selection heuristic based on ds-nogoods. Experimental results show that this allows some problems to be solved more efficiently.
Original languageUnknown
Title of host publicationNONE
Pages10 pages
Publication statusPublished - 1 Jan 2012
EventInternational Workshop on the Cross-Fertilization Between CSP and SAT (CSPSAT 2012) -
Duration: 1 Jan 2012 → …

Conference

ConferenceInternational Workshop on the Cross-Fertilization Between CSP and SAT (CSPSAT 2012)
Period1/01/12 → …

Cite this