Abstract
Although best known for his work in symbolic logic, George Boole made seminal contributions in the logic of probabilities. He solved the probabilistic inference problem with a projection method, leading to the insight that inference (as well as optimization) is essentially a projection problem. This unifying perspective has applications in constraint programming, because consistency maintenance is likewise a form of inference that can be conceived as projection. Viewing consistency in this light suggests a concept of J-consistency, which is achieved by projection onto a subset J of variables. We show how this projection problem can be solved for the satisfiability problem by logic-based Benders decomposition. We also solve it for among, sequence, regular, and all-different constraints. Maintaining J-consistency for global constraints can be more effective than maintaining traditional domain and bounds consistency when propagating through a richer structure than a domain store, such as a relaxed decision diagram. This paper is written in recognition of Boole’s 200th birthday.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Andersen, H.R., Hadžić, T., Hooker, J.N., & Tiedemann, P. (2007). A constraint store based on multivalued decision diagrams. In C. Bessiere (Ed.), Principles and practice of constraint programming (CP 2007). Lecture Notes in Computer Science, (Vol. 4741 pp. 118–132). Springer.
Appa, G., Magos, D., & Mourtos, I. (2004). Linear programming relaxations of multiple all-different predicates. In J.C. Régin, & M. Rueher (Eds.), CPAIOR 2004 Proceedings. Lecture Notes in Computer Science, (Vol. 3011 pp. 364–369). Springer.
Appa, G., Magos, D., & Mourtos, I. (2004). On the system of two all-different predicates. Information Processing Letters, 94, 99–105.
Beame, P., Kautz, H., & Sabharwal, A. (2003). Understanding the power of clause learning. In International Joint Conference on Artificial Intelligence (IJCAI 2003).
Beldiceanu, N., & Contejean, E. (1994). Introducing global constraints in CHIP. Mathematical and Computer Modelling, 12, 97–123.
Benders, J.F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4, 238–252.
Bergman, D., Cire, A., Sabharwal, A., Samulowitz, H., Sarswat, V., & van Hoeve, W.J. (2014). Parallel combinatorial optimization with decision diagrams. In CPAIOR 2012 Proceedings. LNCS, (Vol. 8451 pp. 351–367). Springer.
Bergman, D., Cire, A.A., van Hoeve, W.J., & Hooker, J.N. Discrete optimization with binary decision diagrams. INFORMS Journal on Computing (to appear).
Bergman, D., van Hoeve, W.J., & Hooker, J.N. (2011). Manipulating MDD relaxations for combinatorial optimization. In T. Achterberg, & J.S. Beck (Eds.), CPAIOR 2011 Proceedings. Lecture Notes in Computer Science, (Vol. 6697 pp. 20–35). Springer.
Bergman, D., & Hooker, J.N. (2012). Graph coloring facets from all-different systems. In N. Jussien, & T. Petit (Eds.), CPAIOR Proceedings (pp. 50–65). Springer.
Bergman, D., & Hooker, J. (2014). Graph coloring inequalities for all-different systems. Constraints, 19, 404–433.
Boole, G. (1854). An investigation of the laws of thought, on which are founded the mathematical theories of logic and Probabilities. London: Walton and Maberly.
Boole, G. (1952). Studies in logic and probability (ed. by R. Rhees). La Salle: Open Court Publishing Company.
Ciré, A.A., & van Hoeve, W.J. (2012). MDD propagation for disjunctive scheduling. In Proceedings of the international conference on automated planning and scheduling (ICAPS) (pp. 11–19). AAAI Press.
Cire, A.A., & van Hoeve, W.J. (2013). Multivalued decision diagrams for sequencing problems. Operations Research, 61, 1411–1428.
Fourier, L.B.J. (1827). Analyse des travaux de l’Académie Royale des Sciences, pendant l’anneé 1824, partie mathématique (report of 1824 transactions of the Royal Academy of Sciences, containing Fourier’s work on linear inequalities). Histoire de l’Académie Royale des Sciences de l’Institut de France 7, xlvii–iv.
Freuder, E.C. (1982). A sufficient condition for backtrack-free search. Communications of the ACM, 29, 24–32.
Gebser, M., Kaufmann, B., & Schaub, T. (2009). Solution enumeration for projected boolean search problems. In W.J. van Hoeve, & J.N. Hooker (Eds.), CPAIOR 2009 Proceedings. Lecture Notes in Computer Science, (Vol. 5547 pp. 71–86). New York: Springer.
Genç-Kaya, L., & Hooker, J.N. (2013). The Hamiltonian circuit polytope. Manuscript, Carnegie Mellon University.
Hailperin, T. (1976). Boole’s logic and probability, studies in logic and the foundations of mathematics Vol. 85. North-Holland, Amsterdam.
Hansen, P., & Perron, S. (2008). Merging the local and global approaches to probabilistic satisfiability. International Journal of Approximate Reasoning, 47, 125–140.
Hoda, S., van Hoeve, W.J., & Hooker, J.N. (2010). A systematic approach to MDD-based constraint programming. In Proceedings of the 16th international conference on principles and practices of constraint programming. Lecture notes in computer science. Springer.
van Hoeve, W.J., Pesant, G., Rousseau, L.M., & Sabharwal, A. (2006). Revisiting the sequence constraint. In F. Benhamou (Ed.), Principles and practice of constraint programming (CP 2006). Lecture notes in computer science, (Vol. 4204 pp. 620–634). Springer.
Hooker, J.N. (1988). Generalized resolution and cutting planes. Annals of Operations Research, 12, 217–239.
Hooker, J.N. (1988). A mathematical programming model for probabilistic logic. Working paper 05-88-89, Graduate School of Industrial Administration, Carnegie Mellon University.
Hooker, J.N. (1992). Generalized resolution for 0-1 linear inequalities. Annals of Mathematics and Artificial Intelligence, 6, 271–286.
Hooker, J.N. (1992). Logical inference and polyhedral projection. In Computer Science Logic Conference (CSL 1991). Lecture Notes in Computer Science, (Vol. 626 pp. 184–200). Springer.
Hooker, J.N. (2007). Planning and scheduling by logic-based Benders decomposition. Operations Research, 55, 588–602.
Hooker, J.N. (2012). Integrated Methods for Optimization, 2nd edn. Springer.
Hooker, J.N., & Ottosson, G. (2003). Logic-based Benders decomposition. Mathematical Programming, 96, 33–60.
Hooker, J.N., & Yan, H. (1995). Logic circuit verification by Benders decomposition. In V. Saraswat, & P.V. Hentenryck (Eds.), Principles and practice of constraint programming: The Newport Papers (pp. 267–288). Cambridge: MIT Press.
Huynh, T., Lassez, C., & Lassez, J.L. (1992). Practical issues on the projection of polyhedral sets. Annals of Mathematics and Artificial Intelligence, 6, 295–315.
Jaumard, B., Hansen, P., & Aragão, M.P. (1991). Column generation methods for probabilistic logic. INFORMS Journal on Computing, 3, 135–148.
Kavvadias, D., & Papadimitriou, C.H. (1990). A linear prorgamming approach to reasoning about probabilities. Annals of Mathematics and Artificial Intelligence, 1, 189–206.
Klinov, P., & Parsia, B. (2011). A hybrid method for probabilistic satisfiability. In N. Bjørner, & V. Sofronie-Stokkermans (Eds.), 23rd International Conference on Automated Deduction (CADE 2011). Lecture Notes in AI, (Vol. 6803 pp. 354–368). Springer.
Klinov, P., & Parsia, B. (2013). Pronto: A practical probabilistic description logic reasoner. In F. Bobillo, P.C.G. Costa, C. d’Amato, N. Fanizzi, K.B. Laskey, K.J. Laskey, T. Lukasiewicz, M. Nickles, & M. Pool (Eds.), Uncertainty reasoning for the Semantic Web II (URSW 2008–2010) LNAI, (Vol. 7123 pp. 59–79). Springer.
Magos, D., & Mourtos, I. (2011). On the facial structure of the alldifferent system. SIAM Journal on Discrete Mathematics, 130–158.
Magos, D., Mourtos, I., & Appa, G. (2012). A polyhedral approach to the alldifferent system. Mathematical Programming, 132, 209–260.
Maher, M.J., Narodytska, N., Quimper, C.G., & Walsh, T. (2008). Flow-based propagators for the SEQUENCE and related global constraints. In P.J. Stuckey (Ed.), Principles and Practice of Constraint Programming (CP 2008). Lecture Notes in Computer Science, (Vol. 5202 pp. 159–174). Springer.
Martin, R.K. (1999). Large scale linear and integer optimization: A unified approach. New York: Springer.
Motzkin, T.S. (1983). Beiträge zur Theorie der linearen Ungleichungen. Ph.D. thesis, University of Basel (1936), English translation: Contributions to the theory of linear inequalities, RAND Corporation Translation 22, Santa Monica, CA (1952), reprinted in D. Cantor, B. Gordon and B. Rothschild, eds., Theodore S. Motzkin: Selected Papers, Birkhäuser, Boston, 1–80.
Nilsson, N.J. (1986). Probabilistic logic. Artificial Intelligence, 28, 71–87.
Pesant, G. (2004). A regular language membership constraint for finite sequences of variables. In M. Wallace (Ed.), Principles and practice of constraint programming (CP 2004). Lecture Notes in Computer Science, (Vol. 3258 pp. 482–495). Springer.
Quine, W.V. (1952). The problem of simplifying truth functions. American Mathematical Monthly, 59, 521–531.
Quine, W.V. (1955). A way to simplify truth functions. American Mathematical Monthly, 62, 627–631.
Régin, J.C., & Puget, J.F. (1997). A filtering algorithm for global sequencing constraints. In G. Smolka (Ed.), Principles and practice of constraint programming (CP 1997). Lecture Notes in Computer Science, (Vol. 3011 pp. 32–46). Springer.
Williams, H.P. (1987). Linear and integer programming applied to the propositional calculus. International Journal of Systems Research and Information Science, 2, 81–100.
Williams, H.P., & Hooker, J.N. (2014). Integer programming as projection. Working paper LSEOR 13.143, London School of Economics.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Hooker, J.N. Projection, consistency, and George Boole. Constraints 21, 59–76 (2016). https://doi.org/10.1007/s10601-015-9201-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10601-015-9201-2