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 language | Unknown |
---|---|
Title of host publication | NONE |
Pages | 9 pages |
Publication status | Published - 1 Jan 2012 |
Event | Nogood Learning and Constraint Programming Workshop (NGL) - Duration: 1 Jan 2012 → … |
Conference
Conference | Nogood Learning and Constraint Programming Workshop (NGL) |
---|---|
Period | 1/01/12 → … |