Inter-block Backtracking: Exploiting the Structure in Continuous CSPs Export

@incollection{neveu03, abstract = {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 × 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. Keywords: intervals, decomposition, backtracking, solving sparse systems.}, author = {Neveu, Bertrand and Jermann, Christophe and Trombettoni, Gilles}, citeulike-article-id = {5467220}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/11425076_2}, citeulike-linkout-1 = {http://www.springerlink.com/content/h4v140ebhtb2j8cv}, doi = {10.1007/11425076_2}, journal = {Global Optimization and Constraint Satisfaction}, pages = {15--30}, posted-at = {2009-08-18 15:01:04}, priority = {2}, title = {Inter-block Backtracking: Exploiting the Structure in Continuous CSPs}, url = {http://dx.doi.org/10.1007/11425076_2}, year = {2005} }

TY - CHAP ID - neveu03 L3 - citeulike-article-id:5467220 N2 - 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 × 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. Keywords: intervals, decomposition, backtracking, solving sparse systems. JF - Global Optimization and Constraint Satisfaction EP - 30 TI - Inter-block Backtracking: Exploiting the Structure in Continuous CSPs SP - 15 AU - Neveu, Bertrand AU - Jermann, Christophe AU - Trombettoni, Gilles PY - 2005/// UR - http://dx.doi.org/10.1007/11425076_2 ER -