TitleOpportunistic Specialization in Russian Doll Search
Publication TypeConference Paper
Year of Publication2002
AuthorsMeseguer P, Sánchez M, Verfaillie G
EditorVan Hentenryck P
Conference NameLecture Notes in Computer Science

Russian Doll Search (RDS) is a clever procedure to solve overconstrained problems. RDS solves a sequence of nested subproblems, each including one more variable than the previous, until the whole problems is solved. Specialized RDS (SRDS) solves each subproblem for every value of the new variable. SRDS lower bound is better than RDS lower bound, causing a higher efficiency. A natural extension is Full Specialized RDS (FSRDS) which solves each subproblem for every value of every variable. Although FSRDS lower bound is better than the SRDS one, the extra work performed by FSRDS renders it inefficient. However, much of the useless work can be avoided. With this aim, we present Opportunistic Specialization in RDS (OSRDS), an algorithm that lies between SRDS and FSRDS. In addition to specialize the values of one variable, OSRDS specializes some values of other variables that look promising to increase the lower bound in the current distribution of inconsistency counts. Experimental results on random and real problems show the benefits of this approach.