Abstract
Backbone variables have the same assignment in all solutions to a given constraint satisfaction problem; more generally, bias represents the proportion of solutions that assign a variable a particular value. Intuitively such constructs would seem important to efficient search, but their study to date has been from a mostly conceptual perspective, in terms of indicating problem hardness or motivating and interpreting heuristics. Here we summarize a two-phase project where we first measure the ability of both existing and novel probabilistic message-passing techniques to directly estimate bias and identify backbones for the Boolean Satisfiability (SAT) Problem. We confirm that methods like Belief Propagation and Survey Propagation–plus Expectation Maximization-based variants–do produce good estimates with distinctive properties. The second phase demonstrates the use of bias estimation within a modern SAT solver, exhibiting a correlation between accurate, stable, estimates and successful backtracking search. The same process also yields a family of search heuristics that can dramatically improve search efficiency for the hard random problems considered.
This article summarizes a more detailed description that is available as a technical report [1].
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
Hsu, E., Muise, C., Beck, J.C., McIlraith, S.: Applying probabilistic inference to heuristic search by estimating variable bias. Technical Report CSRG-577, University of Toronto (2008)
Braunstein, A., Mezard, M., Zecchina, R.: Survey propagation: An algorithm for satisfiability. Random Structures and Algorithms 27, 201–226 (2005)
Dechter, R., Kask, K., Mateescu, R.: Iterative join-graph propagation. In: Proc. of 18th Int’l Conference on Uncertainty in A.I (UAI 2002), Edmonton, Canada, pp. 128–136 (2002)
Hsu, E., Kitching, M., Bacchus, F., McIlraith, S.: Using EM to find likely assignments for solving CSP’s. In: Proc. of 22nd National Conference on Artificial Intelligence (AAAI 2007), Vancouver, Canada (2007)
Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., Troyansky, L.: Determining computational complexity from characteristic phase transitions. Nature 400(7), 133–137 (1999)
Kilby, P., Slaney, J., Thiébaux, S., Walsh, T.: Backbones and backdoors in satisfiability. In: Proc. of 20th National Conference on A.I (AAAI 2005), Pittsburgh, PA (2005)
Singer, J., Gent, I., Smaill, A.: Backbone fragility and the local search cost peak. Journal of Artificial Intelligence Research 12, 235–270 (2000)
Dubois, O., Dequen, G.: A backbone-search heuristic for efficient solving of hard 3-SAT formulae. In: Proc. of 17th International Joint Conference on Artificial Intelligence (IJCAI 2001), Seattle, WA (2001)
Zhang, W.: Configuration landscape analysis and backbone guided local search. Part I: Satisfiability and maximum satisfiability. Artificial Intelligence 158(1), 1–26 (2004)
Eén, N., Sörensson, N.: An extensible SAT-solver. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol. 2919, pp. 502–518. Springer, Heidelberg (2004)
Pearl, J.: Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, San Francisco (1988)
Kschischang, F.R., Frey, B.J., Loeliger, H.A.: Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory 47(2) (2001)
Dempster, A., Laird, N., Rubin, D.: Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society 39(1), 1–39 (1977)
Jordan, M., Ghahramani, Z., Jaakkola, T., Saul, L.: An introduction to variational methods for graphical models. In: Jordan, M. (ed.) Learning in Graphical Models. MIT Press, Cambridge (1998)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hsu, E.I., Muise, C.J., Beck, J.C., McIlraith, S.A. (2008). Probabilistically Estimating Backbones and Variable Bias: Experimental Overview. In: Stuckey, P.J. (eds) Principles and Practice of Constraint Programming. CP 2008. Lecture Notes in Computer Science, vol 5202. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85958-1_52
Download citation
DOI: https://doi.org/10.1007/978-3-540-85958-1_52
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85957-4
Online ISBN: 978-3-540-85958-1
eBook Packages: Computer ScienceComputer Science (R0)