×

Projection, consistency, and George Boole. (English) Zbl 1396.03041

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

MSC:

03B48 Probability and inductive logic
60A05 Axioms; other general questions in probability

Software:

Pronto
PDFBibTeX XMLCite
Full Text: DOI

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. · Zbl 1094.90573
[3] Appa, G., Magos, D., & Mourtos, I. (2004). On the system of two all-different predicates. Information Processing Letters, 94, 99-105. · Zbl 1182.68141 · doi:10.1016/j.ipl.2005.01.009
[4] Beame, P., Kautz, H., & Sabharwal, A. (2003). Understanding the power of clause learning. In International Joint Conference on Artificial Intelligence (IJCAI 2003). · Zbl 1080.68651
[5] Beldiceanu, N., & Contejean, E. (1994). Introducing global constraints in CHIP. Mathematical and Computer Modelling, 12, 97-123. · Zbl 0816.68048 · doi:10.1016/0895-7177(94)90127-9
[6] Benders, J.F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische Mathematik, 4, 238-252. · Zbl 0109.38302 · doi:10.1007/BF01386316
[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. · Zbl 1407.68446
[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). · Zbl 1338.90260
[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. · Zbl 1302.90166
[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. · Zbl 0816.68048
[11] Bergman, D., & Hooker, J. (2014). Graph coloring inequalities for all-different systems. Constraints, 19, 404-433. · Zbl 1316.90056 · doi:10.1007/s10601-014-9164-8
[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. · Zbl 1205.03003 · doi:10.5962/bhl.title.29413
[13] Boole, G. (1952). Studies in logic and probability (ed. by R. Rhees). La Salle: Open Court Publishing Company. · Zbl 0049.00802
[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. · Zbl 0068.24209
[15] Cire, A.A., & van Hoeve, W.J. (2013). Multivalued decision diagrams for sequencing problems. Operations Research, 61, 1411-1428. · Zbl 1291.90091 · doi:10.1287/opre.2013.1221
[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. · Zbl 0955.68503
[17] Freuder, E.C. (1982). A sufficient condition for backtrack-free search. Communications of the ACM, 29, 24-32. · Zbl 0477.68063
[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. · Zbl 1241.68100
[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. · Zbl 0352.02002
[21] Hansen, P., & Perron, S. (2008). Merging the local and global approaches to probabilistic satisfiability. International Journal of Approximate Reasoning, 47, 125-140. · Zbl 1343.68220 · doi:10.1016/j.ijar.2007.03.001
[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. · Zbl 0955.68503
[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. · Zbl 1160.68573
[24] Hooker, J.N. (1988). Generalized resolution and cutting planes. Annals of Operations Research, 12, 217-239. · doi:10.1007/BF02186368
[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. · Zbl 1316.90056
[26] Hooker, J.N. (1992). Generalized resolution for 0-1 linear inequalities. Annals of Mathematics and Artificial Intelligence, 6, 271-286. · Zbl 0955.68503 · doi:10.1007/BF01531033
[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. · Zbl 0819.68105
[28] Hooker, J.N. (2007). Planning and scheduling by logic-based Benders decomposition. Operations Research, 55, 588-602. · Zbl 1167.90512 · doi:10.1287/opre.1060.0371
[29] Hooker, J.N. (2012). Integrated Methods for Optimization, 2nd edn. Springer. · Zbl 1263.90002
[30] Hooker, J.N., & Ottosson, G. (2003). Logic-based Benders decomposition. Mathematical Programming, 96, 33-60. · Zbl 1023.90082
[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. · Zbl 0875.68821 · doi:10.1007/BF01535523
[33] Jaumard, B., Hansen, P., & Aragão, M.P. (1991). Column generation methods for probabilistic logic. INFORMS Journal on Computing, 3, 135-148. · Zbl 0800.68864 · doi:10.1287/ijoc.3.2.135
[34] Kavvadias, D., & Papadimitriou, C.H. (1990). A linear prorgamming approach to reasoning about probabilities. Annals of Mathematics and Artificial Intelligence, 1, 189-206. · Zbl 0878.68034 · doi:10.1007/BF01531078
[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. · Zbl 1341.68191
[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. · Zbl 1229.90099
[38] Magos, D., Mourtos, I., & Appa, G. (2012). A polyhedral approach to the alldifferent system. Mathematical Programming, 132, 209-260. · Zbl 1257.90055 · doi:10.1007/s10107-010-0390-6
[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. · Zbl 1023.90082
[40] Martin, R.K. (1999). Large scale linear and integer optimization: A unified approach. New York: Springer. · Zbl 1053.90001 · doi:10.1007/978-1-4615-4975-8
[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. · Zbl 0589.03007
[42] Nilsson, N.J. (1986). Probabilistic logic. Artificial Intelligence, 28, 71-87. · Zbl 0589.03007 · doi:10.1016/0004-3702(86)90031-7
[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. · Zbl 1152.68573
[44] Quine, W.V. (1952). The problem of simplifying truth functions. American Mathematical Monthly, 59, 521-531. · Zbl 0048.24503 · doi:10.2307/2308219
[45] Quine, W.V. (1955). A way to simplify truth functions. American Mathematical Monthly, 62, 627-631. · Zbl 0068.24209 · doi:10.2307/2307285
[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.
[48] Williams, H.P., & Hooker, J.N. (2014). Integer programming as projection. Working paper LSEOR 13.143, London School of Economics.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.