TitleSpecializing Russian doll search
Publication TypeConference Paper
Year of Publication2001
AuthorsSánchez M, Meseguer P
EditorWalsh T
Conference NameLecture notes in computer science
Volume2239
PublisherSpringer
Pagination464-478
Abstract

Russian Doll Search (RDS) is a clever procedure to solve overconstrainedproblems. RDS solves a sequence of nested subproblems, where two consecutivesubproblems differ in one variable only. We present the Specialized RDS(SRDS) algorithm, which solves the current subproblem for each value ofthe new variable with respect to the previous subproblem. The SRDS lowerbound is superior to the RDS lower bound, which allows for a higher levelof value pruning, although more work per node is required. Experimentalresults on random and real problems show that this extra work is oftenbeneficial, providing substantial savings in the global computationaleffort.