Adding Flexibility to Russian Doll Search
Margarita Razgon, Gregory M. Provan · 2008
The weighted constraint satisfaction problem (WCSP) is a popular formalism for encoding instances of hard optimization problems. The common approach to solving WCSP is branch-and-bound (BB), whose efficiency strongly depends on the method of computing a lower bound (LB) associated with the current node of the search tree. Two of the most important approaches for computing LB include (1) using local inconsistency counts, such as maintaining directed arc-consistency (MDAC), and (2) Russian Doll search (RDS). In this paper we present two BB-based algorithms. The first algorithm extends RDS. The second algorithm combines RDS and MDAC in an adaptive manner. We empirically demonstrate that the WCSP solver combining the above two algorithms outperforms both RDS and MDAC, over all the problem domains and instances we studied. To the best of our knowledge this is the first attempt to combine these two methodologies of computing LB for a BB-based algorithm.