TY - CHAP
T1 - Value ordering for finding all solutions
T2 - 17th International Conference on Principles and Practice of Constraint Programming, CP 2011
AU - Mehta, Deepak
AU - O'Sullivan, Barry
AU - Quesada, Luis
PY - 2011
Y1 - 2011
N2 - We consider the impact of value ordering heuristics on the search effort required to find all solutions, or proving none exist, to a constraint satisfaction problem in k-way branching search. We show that when the variable ordering heuristic is adaptive, the order in which the values are assigned to variables can make a significant difference in all measures of search effort. We study in depth an open issue regarding the relative merit of traditional value heuristics, and their complements, when searching for all solutions. We also introduce a lazy version of k-way branching and study the effect of value orderings on finding all solutions when it is used. This paper motivates a new and fruitful line of research in the study of value ordering heuristics for proving unsatisfiability.
AB - We consider the impact of value ordering heuristics on the search effort required to find all solutions, or proving none exist, to a constraint satisfaction problem in k-way branching search. We show that when the variable ordering heuristic is adaptive, the order in which the values are assigned to variables can make a significant difference in all measures of search effort. We study in depth an open issue regarding the relative merit of traditional value heuristics, and their complements, when searching for all solutions. We also introduce a lazy version of k-way branching and study the effect of value orderings on finding all solutions when it is used. This paper motivates a new and fruitful line of research in the study of value ordering heuristics for proving unsatisfiability.
UR - https://www.scopus.com/pages/publications/80053031329
U2 - 10.1007/978-3-642-23786-7_46
DO - 10.1007/978-3-642-23786-7_46
M3 - Chapter
AN - SCOPUS:80053031329
SN - 9783642237850
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 606
EP - 620
BT - Principles and Practice of Constraint Programming, CP 2011 - 17th International Conference, Proceedings
Y2 - 12 September 2011 through 16 September 2011
ER -