Inter-block Backtracking: Exploiting the Structure in Continuous CSPs

摘要

This paper details a technique, called inter-block backtracking (IBB), which improves interval solving of decomposed systems with non-linear equations over the reals. This technique, introduced in 1998 by Bliek et al., handles a system of equations previously decomposed into a set of (small) k x k sub-systems, called blocks. All solutions are obtained by combining the solutions computed in the different blocks. The approach seems particularly suitable for improving interval solving techniques. In this paper, we analyze into detail the different variants of IBB which differ in their backtracking and filtering strategies. We also introduce IBB-GBJ, a new variant based on Dechter's graph-based backjumping. An extensive comparison on a sample of eight CSPs allows us to better understand the behavior of IBB. It shows that the variants IBB-BT+ and IBB-GBJ are good compromises between simplicity and performance. Moreover, it clearly shows that limiting the scope of the filtering to the blocks is very useful. For all the tested instances, IBB gains several orders of magnitude as compared to a global solving.