Abstract
It has recently been shown, for the Constraint Satisfaction Problem (CSP), that the state associated with a node of the search tree built by a backtracking algorithm can be exploited, using a transposition table, to prevent the exploration of similar nodes. This technique is commonly used in game search algorithms, heuristic search or planning. Its application is made possible in CSP by computing a partial state – a set of meaningful variables and their associated domains – preserving relevant information. We go further in this paper by providing two new powerful operators dedicated to the extraction of inconsistent partial states. The first one eliminates any variable whose current domain can be deduced from the partial state, and the second one extracts the variables involved in the inconsistency proof of the subtree rooted by the current node. Interestingly, we show these two operators can be safely combined, and that the pruning capabilities of the recorded partial states can be improved by a dominance detection approach (using lazy data structures).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Baker, R.R., Dikker, F., Tempelman, F., Wognum, P.M.: Diagnosing and solving over-determined constraint satisfaction problems. In: Proceedings of IJCAI 1993, pp. 276–281 (1993)
Bessière, C.: Arc-consistency in dynamic constraint satisfaction problems. In: Proceedings of AAAI 1991, pp. 221–226 (1991)
Boussemart, F., Hemery, F., Lecoutre, C., Sais, L.: Boosting systematic search by weighting constraints. In: Proceedings of ECAI 2004, pp. 146–150 (2004)
Boutaleb, K., Jégou, P., Terrioux, C.: (no)good recording and robdds for solving structured (v)csps. In: Proceedings of ICTAI 2006, pp. 297–304 (2006)
de Siqueira, J.L., Puget, J.F.: Explanation-based generalisation of failures. In: Proceedings of ECAI 1988, pp. 339–344 (1988)
Debruyne, R., Bessiere, C.: Domain filtering consistencies. Journal of Artificial Intelligence Research 14, 205–230 (2001)
Dechter, R., Frost, D.: Backjump-based backtracking for constraint satisfaction problems. Artificial Intelligence 136, 147–188 (2002)
Eén, N., Sorensson, N.: An extensible sat-solver. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol. 2919. Springer, Heidelberg (2004)
Fahle, T., Schamberger, S., Sellman, M.: Symmetry breaking. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 93–107. Springer, Heidelberg (2001)
Focacci, F., Milano, M.: Global cut framework for removing symmetries. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 77–92. Springer, Heidelberg (2001)
Frost, D., Dechter, R.: Dead-end driven learning. In: Proceedings of AAAI 1994, pp. 294–300 (1994)
Ginsberg, M.: Dynamic backtracking. Artificial Intelligence 1, 25–46 (1993)
Hemery, F., Lecoutre, C., Sais, L., Boussemart, F.: Extracting MUCs from constraint networks. In: Proceedings of ECAI 2006, pp. 113–117 (2006)
Junker, U.: QuickXplain: preferred explanations and relaxations for over-constrained problems. In: Proceedings of AAAI 2004, pp. 167–172 (2004)
Katsirelos, G., Bacchus, F.: Generalized nogoods in CSPs. In: Proceedings of AAAI 2005, pp. 390–396 (2005)
Lecoutre, C., Sais, L., Tabary, S., Vidal, V.: Recording and minimizing nogoods from restarts. Journal on Satisfiability, Boolean Modeling and Computation (JSAT) 1, 147–167 (2007)
Lecoutre, C., Sais, L., Tabary, S., Vidal, V.: Transposition Tables for Constraint Satisfaction. In: Proceedings of AAAI 2007, pp. 243–248 (2007)
Moskewicz, M.W., Madigan, C.F., Zhao, Y., Zhang, L., Malik, S.: Chaff: Engineering an Efficient SAT Solver. In: Proceedings of DAC 2001, pp. 530–535 (2001)
Prosser, P.: Hybrid algorithms for the constraint satisfaction problems. Computational Intelligence 9(3), 268–299 (1993)
Puget, J.F.: Symmetry breaking revisited. Constraints 10(1), 23–46 (2005)
Sellmann, M., Van Hentenryck, P.: Structural symmetry breaking. In: Proceedings of IJCAI 2005, pp. 298–303 (2005)
Zhang, L., Madigan, C.F., Moskewicz, M.W., Malik, S.: Efficient conflict driven learning in a Boolean satisfiability solver. In: Proceedings of ICCAD 2001, pp. 279–285 (2001)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lecoutre, C., Sais, L., Tabary, S., Vidal, V. (2007). Exploiting Past and Future: Pruning by Inconsistent Partial State Dominance. In: Bessière, C. (eds) Principles and Practice of Constraint Programming – CP 2007. CP 2007. Lecture Notes in Computer Science, vol 4741. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74970-7_33
Download citation
DOI: https://doi.org/10.1007/978-3-540-74970-7_33
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74969-1
Online ISBN: 978-3-540-74970-7
eBook Packages: Computer ScienceComputer Science (R0)