Abstract
This paper describes two ways to transform propositional clauses into mathematical constraints, and gives an overview of mathematical optimization approaches to inference. The first transformation, which translates constraints into linear inequalities, has been applied to cost-based abduction in the past and showed good performance. The second one, which produces nonlinear equalities, is commonly used in other representations, such as SAT. We clarify their differences and advantages, and show the radical performance transition of linear inequalities. We are mainly targeting at cost-based hypothetical reasoning (or abduction), but through preprocessing, the discussion has generality.
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.
References
Poole, D.: A methodology for using a default and abductive reasoning system. International Journal of Intelligent Systems 5 (1990) 521–548
Kakas, A., Kowalski, R., Toni, F.: The role of abduction in logic programming. In: Handbook of Logic in Artificial Intelligence and Logic Programming. Oxford University Press (1995)
Charniak, E., Shimony, S.E.: Cost-based abduction and MAP explanation. Artificial Intelligence 66 (1994) 345–374
Santos, Jr., E.: A linear constraint satisfaction approach to cost-based abduction. Artificial Intelligence 65 (1994) 1–27
Eiter, T., Gottlob, G.: The complexity of logic-based abduction. Journal of the Association for Computing Machinary 42 (1995) 3–42
Prendinger, H., Ishizuka, M.: Qualifying the expressivity / efficiency tradeoff: Reformation-based diagnosis. In: Proceedings 16th National Conference on Artificial Intelligence (AAAI-99). (1999) 416–421
Ohsawa, Y., Ishizuka, M.: Networked bubble propagation: A polynomial-time hypothetical reasoning method for computing near-optimal solutions. Artificial Intelligence 91 (1997) 131–154
Ishizuka, M., Matsuo, Y.: SL method for computing a near-optimal solution using linear and non-linear programming in cost-based hypothetical reasoning. In: Proceedings 5th Pacific Rim Conference on Artificial Intelligence (PRICAI-98). (1998) 611–625
Selman, B., Levesque, H., McAllester, D.: A new method for solving hard satisfiability problems. In: Proceedings 9th National Conference on Artificial Intelligence (AAAI-92). (1992) 440–446
Gu, J.: Local search for satisfiability (SAT) problem. IEEE Transactions on Systems, Man, and Cybernetics 23 (1993) 1108–1129
Selman, B., Kautz, H., Cohen, B.: Noise strategies for improving local search. In: Proceedings 11th National Conference on Artificial Intelligence (AAAI-94). (1994) 337–343
Frank, J.: Learning short-term weights for GSAT. In: Proceedings 15th International Joint Conference on Artificial Intelligence (IJCAI-97). (1997) 384–391
Wu, Z., Wah, B.W.: An efficient global-search strategy in discrete Lagrangian methods for solving hard satisfiability problems. In: Proceedings 17th National Conference on Artificial Intelligence (AAAI-2000). (2000) 310–315
Levy, A.Y., Fikes, R.E., Sagiv, Y.: Speeding up inferences using relevance reasoning: a formalism and algorithms. Artificial Intelligence 97 (1997) 83–136
Davis, M., Putnam, H.: A computing procedure for quantification theory. Journal of the Association for Computing Machinary 7 (1960) 201–215
Selman, B., Kautz, H., McAllester, D.: Ten challenges in propositional reasoning and search. In: Proceedings 15th International Joint Conference on Artificial Intelligence (IJCAI-97). (1997) 50–54
Mitchell, D., Levesque, H.: Some pitfalls for experimenters with random SAT. Artificial Intelligence 81 (1996) 111–125
Gu, J.: Global optimization for satisfiability problem. IEEE Transactions on Knowledge and Data Engineering 6 (1994) 361–381
Nemhauser, G.L., Kan, A.H.G.R., Todd, M.J., eds.: Optimization: Handbooks in Operations Research and Management Science, Volume 1. North-Holland, Amsterdam (1989)
Shang, Y., Wah, B.W.: A discrete Lagrangian-based global-search method for solving satisfiability problems. Journal of Global Optimization 12 (1998)
Schuurmans, D., Southey, F., Holte, R.C.: The exponentiated subgradient algorithm for heuristic boolean programming. In: Proceedings 17th International Joint Conference on Artificial Intelligence (IJCAI-01). (2001) 334–341
Hammer, P., Simeone, B.: Quadratic functions of binary variables. In: Combinatorial Optimization, Lecture Notes in Mathematics. Volume 1403. (1989)
Selman, B., Mitchell, D., Levesque, H.: Generating hard satisfiability problems. Artificial Intelligence 81 (1996) 17–29
Gomes, C., Selman, B., Crato, N.: Heavy-tailed phenomena in satisfiability and constraint satisfaction problems. Journal of Automated Reasoning 24 (2000) 67–100
Gomes, C.: Structure, duality, and randomization: Common theme in AI and OR. In: Proceedings 17th National Conference on Artificial Intelligence (AAAI-2000). (2000) 1152–1158
Hooker, J.N.: Logic, optimization, and constraint programming. (INFORMS journal on Computing) To appear.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Matsuo, Y., Ishizuka, M. (2002). Two Transformations of Clauses into Constraints and Their Properties for Cost-Based Hypothetical Reasoning. In: Ishizuka, M., Sattar, A. (eds) PRICAI 2002: Trends in Artificial Intelligence. PRICAI 2002. Lecture Notes in Computer Science(), vol 2417. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45683-X_15
Download citation
DOI: https://doi.org/10.1007/3-540-45683-X_15
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44038-3
Online ISBN: 978-3-540-45683-4
eBook Packages: Springer Book Archive