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.

• Tagged
• XML
• BibTex