Skip to main content
Log in

Projection, consistency, and George Boole

  • Published:
Constraints Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. 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.

  2. 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.

  3. Appa, G., Magos, D., & Mourtos, I. (2004). On the system of two all-different predicates. Information Processing Letters, 94, 99–105.

    Article  MathSciNet  Google Scholar 

  4. Beame, P., Kautz, H., & Sabharwal, A. (2003). Understanding the power of clause learning. In International Joint Conference on Artificial Intelligence (IJCAI 2003).

  5. Beldiceanu, N., & Contejean, E. (1994). Introducing global constraints in CHIP. Mathematical and Computer Modelling, 12, 97–123.

    Article  Google Scholar 

  6. Benders, J.F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4, 238–252.

    Article  MATH  MathSciNet  Google Scholar 

  7. 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.

  8. Bergman, D., Cire, A.A., van Hoeve, W.J., & Hooker, J.N. Discrete optimization with binary decision diagrams. INFORMS Journal on Computing (to appear).

  9. 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.

  10. 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.

  11. Bergman, D., & Hooker, J. (2014). Graph coloring inequalities for all-different systems. Constraints, 19, 404–433.

    Article  MathSciNet  Google Scholar 

  12. 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.

    Book  Google Scholar 

  13. Boole, G. (1952). Studies in logic and probability (ed. by R. Rhees). La Salle: Open Court Publishing Company.

    Google Scholar 

  14. 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.

  15. Cire, A.A., & van Hoeve, W.J. (2013). Multivalued decision diagrams for sequencing problems. Operations Research, 61, 1411–1428.

    Article  MATH  MathSciNet  Google Scholar 

  16. 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.

  17. Freuder, E.C. (1982). A sufficient condition for backtrack-free search. Communications of the ACM, 29, 24–32.

    MATH  MathSciNet  Google Scholar 

  18. 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.

  19. Genç-Kaya, L., & Hooker, J.N. (2013). The Hamiltonian circuit polytope. Manuscript, Carnegie Mellon University.

  20. Hailperin, T. (1976). Boole’s logic and probability, studies in logic and the foundations of mathematics Vol. 85. North-Holland, Amsterdam.

  21. Hansen, P., & Perron, S. (2008). Merging the local and global approaches to probabilistic satisfiability. International Journal of Approximate Reasoning, 47, 125–140.

    Article  MATH  MathSciNet  Google Scholar 

  22. 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.

  23. 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.

  24. Hooker, J.N. (1988). Generalized resolution and cutting planes. Annals of Operations Research, 12, 217–239.

    Article  MathSciNet  Google Scholar 

  25. Hooker, J.N. (1988). A mathematical programming model for probabilistic logic. Working paper 05-88-89, Graduate School of Industrial Administration, Carnegie Mellon University.

  26. Hooker, J.N. (1992). Generalized resolution for 0-1 linear inequalities. Annals of Mathematics and Artificial Intelligence, 6, 271–286.

    Article  MATH  MathSciNet  Google Scholar 

  27. 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.

  28. Hooker, J.N. (2007). Planning and scheduling by logic-based Benders decomposition. Operations Research, 55, 588–602.

    Article  MATH  MathSciNet  Google Scholar 

  29. Hooker, J.N. (2012). Integrated Methods for Optimization, 2nd edn. Springer.

  30. Hooker, J.N., & Ottosson, G. (2003). Logic-based Benders decomposition. Mathematical Programming, 96, 33–60.

    MATH  MathSciNet  Google Scholar 

  31. 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.

  32. 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.

    Article  MATH  MathSciNet  Google Scholar 

  33. Jaumard, B., Hansen, P., & Aragão, M.P. (1991). Column generation methods for probabilistic logic. INFORMS Journal on Computing, 3, 135–148.

    Article  MATH  Google Scholar 

  34. Kavvadias, D., & Papadimitriou, C.H. (1990). A linear prorgamming approach to reasoning about probabilities. Annals of Mathematics and Artificial Intelligence, 1, 189–206.

    Article  MATH  Google Scholar 

  35. 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.

  36. 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.

  37. Magos, D., & Mourtos, I. (2011). On the facial structure of the alldifferent system. SIAM Journal on Discrete Mathematics, 130–158.

  38. Magos, D., Mourtos, I., & Appa, G. (2012). A polyhedral approach to the alldifferent system. Mathematical Programming, 132, 209–260.

    Article  MATH  MathSciNet  Google Scholar 

  39. 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.

  40. Martin, R.K. (1999). Large scale linear and integer optimization: A unified approach. New York: Springer.

    Book  MATH  Google Scholar 

  41. 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.

  42. Nilsson, N.J. (1986). Probabilistic logic. Artificial Intelligence, 28, 71–87.

    Article  MATH  MathSciNet  Google Scholar 

  43. 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.

  44. Quine, W.V. (1952). The problem of simplifying truth functions. American Mathematical Monthly, 59, 521–531.

    Article  MATH  MathSciNet  Google Scholar 

  45. Quine, W.V. (1955). A way to simplify truth functions. American Mathematical Monthly, 62, 627–631.

    Article  MATH  MathSciNet  Google Scholar 

  46. 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.

  47. Williams, H.P. (1987). Linear and integer programming applied to the propositional calculus. International Journal of Systems Research and Information Science, 2, 81–100.

    Google Scholar 

  48. Williams, H.P., & Hooker, J.N. (2014). Integer programming as projection. Working paper LSEOR 13.143, London School of Economics.

Download references

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to J. N. Hooker.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10601-015-9201-2

Keywords

Navigation