Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-27T14:53:55.716Z Has data issue: false hasContentIssue false
  • English
  • Français

Complex optimization in answer set programming

Published online by Cambridge University Press:  06 July 2011

MARTIN GEBSER ,
ROLAND KAMINSKI  and
TORSTEN SCHAUB
MARTIN GEBSER
Affiliation:
Institut für Informatik, Universität Potsdam, Germany
ROLAND KAMINSKI
Affiliation:
Institut für Informatik, Universität Potsdam, Germany
TORSTEN SCHAUB
Affiliation:
Institut für Informatik, Universität Potsdam, Germany
Get access Rights & Permissions [Opens in a new window]

Abstract

Preference handling and optimization are indispensable means for addressing nontrivial applications in Answer Set Programming (ASP). However, their implementation becomes difficult whenever they bring about a significant increase in computational complexity. As a consequence, existing ASP systems do not offer complex optimization capacities, supporting, for instance, inclusion-based minimization or Pareto efficiency. Rather, such complex criteria are typically addressed by resorting to dedicated modeling techniques, like saturation. Unlike the ease of common ASP modeling, however, these techniques are rather involved and hardly usable by ASP laymen. We address this problem by developing a general implementation technique by means of meta-prpogramming, thus reusing existing ASP systems to capture various forms of qualitative preferences among answer sets. In this way, complex preferences and optimization capacities become readily available for ASP applications.

Keywords

Answer Set ProgrammingPreference HandlingComplex optimizationMeta-Programming
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 11 , Special Issue 4-5: 27th International Conference on Logic Programming , July 2011 , pp. 821 - 839
Copyright
Copyright © Cambridge University Press 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Baral, C. 2003. Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press.CrossRefGoogle Scholar
Brewka, G. 2004. Answer sets: From constraint programming towards qualitative optimization. In Proceedings of the Seventh International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'04), Lifschitz, V. and Niemelä, I., Eds. Lecture Notes in Artificial Intelligence, vol. 2923. Springer-Verlag, 34–46.Google Scholar
Brewka, G., Niemelä, I. and Syrjänen, T. 2004. Logic programs with ordered disjunction. Computational Intelligence 20 (2), 335–357.CrossRefGoogle Scholar
Brewka, G., Niemelä, I. and Truszczynski, M. 2003. Answer set optimization. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI'03), Gottlob, G. and Walsh, T., Eds. Morgan Kaufmann Publishers, 867–872.Google Scholar
Chevaleyre, Y., Endriss, U., Lang, J. and Maudet, N. 2007. A short introduction to computational social choice. In Proceedings of the Thirty-third Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'07), van Leeuwen, J., Italiano, G., van der Hoek, W., Meinel, C., Sack, H. and Plasil, F., Eds. Lecture Notes in Computer Science, vol. 4362. Springer-Verlag, 51–69.Google Scholar
Delgrande, J., Schaub, T. and Tompits, H. 2003. A framework for compiling preferences in logic programs. Theory and Practice of Logic Programming 3 (2), 129–187.CrossRefGoogle Scholar
Drescher, C., Gebser, M., Grote, T., Kaufmann, B., König, A., Ostrowski, M. and Schaub, T. 2008. Conflict-driven disjunctive answer set solving. In Proceedings of the Eleventh International Conference on Principles of Knowledge Representation and Reasoning (KR'08), Brewka, G. and Lang, J., Eds. AAAI, 422–432.Google Scholar
Dung, P. 1995. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. Artificial Intelligence 77 (2), 321–357.CrossRefGoogle Scholar
Eiter, T., Faber, W., Leone, N. and Pfeifer, G. 2003. Computing preferred answer sets by meta-interpretation in answer set programming. Theory and Practice of Logic Programming 3 (4–5), 463–498.CrossRefGoogle Scholar
Eiter, T. and Gottlob, G. 1995. On the computational cost of disjunctive logic programming: Propositional case. Annals of Mathematics and Artificial Intelligence 15 (3–4), 289–323.CrossRefGoogle Scholar
Eiter, T. and Polleres, A. 2006. Towards automated integration of guess and check programs in answer set programming: A meta-interpreter and applications. Theory and Practice of Logic Programming 6 (1–2), 23–60.CrossRefGoogle Scholar
Faber, W. and Woltran, S. 2009. Manifold answer-set programs for meta-reasoning. In Proceedings of the Tenth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'09), Erdem, E., Lin, F. and Schaub, T., Eds. Lecture Notes in Artificial Intelligence, vol. 5753. Springer-Verlag, 115–128.CrossRefGoogle Scholar
Fages, F. 1994. Consistency of Clark's completion and the existence of stable models. Journal of Methods of Logic in Computer Science 1, 51–60.Google Scholar
Ferraris, P. 2005. Answer sets for propositional theories. In Proceedings of the Eighth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'05), Baral, C., Greco, G., Leone, N. and Terracina, G., Eds. Lecture Notes in Artificial Intelligence, vol. 3662. Springer-Verlag, 119–131.CrossRefGoogle Scholar
Garey, M. and Johnson, D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. Freeman and Co.Google Scholar
Gebser, M., Guziolowski, C., Ivanchev, M., Schaub, T., Siegel, A., Thiele, S. and Veber, P. 2010. Repair and prediction (under inconsistency) in large biological networks with answer set programming. In Proceedings of the Twelfth International Conference on Principles of Knowledge Representation and Reasoning (KR'10), Lin, F. and Sattler, U., Eds. AAAI, 497–507.Google Scholar
Gebser, M., Kaminski, R., Kaufmann, B., Ostrowski, M., Schaub, T., and Thiele, S. 2010. A User's guide to gringo, clasp, clingo, and iclingo [online]. Accessed 9 June 2011. URL: http://potassco.sourceforge.net.Google Scholar
Gebser, M., Kaminski, R. and Schaub, T. 2011. Complex optimization in answer set programming: Extended version. Available at (metasp). (This is an extended version of the paper at hand.)CrossRefGoogle Scholar
Gebser, M., Kaufmann, B., Neumann, A. and Schaub, T. 2007. Conflict-driven answer set solving. In Proceedings of the Twentieth International Joint Conference on Artificial Intelligence (IJCAI'07), Veloso, M., Ed. AAAI/The MIT, 386–392.Google Scholar
Gelfond, M. and Lifschitz, V. 1991. Classical negation in logic programs and disjunctive databases. New Generation Computing 9, 365–385.CrossRefGoogle Scholar
Gries, M. 2004. Methods for evaluating and covering the design space during early design development. Integration 38 (2), 131–183.CrossRefGoogle Scholar
Janhunen, T. and Oikarinen, E. 2004. Capturing parallel circumscription with disjunctive logic programs. In Proceedings of the Ninth European Conference on Logics in Artificial Intelligence (JELIA'04), Alferes, J. and Leite, J., Eds. Lecture Notes in Computer Science, vol. 3229. Springer-Verlag, 134–146.Google Scholar
Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S. and Scarcello, F. 2006. The DLV system for knowledge representation and reasoning. ACM Transactions on Computational Logic 7 (3), 499–562.CrossRefGoogle Scholar
Lifschitz, V. 1985. Computing circumscription. In Proceedings of the Ninth International Joint Conference on Artificial Intelligence (IJCAI'85), Joshi, A., Ed. Morgan Kaufmann Publishers, 121–127.Google Scholar
Liu, G. and You, J. 2010. Level mapping induced loop formulas for weight constraint and aggregate logic programs. Fundamenta Informaticae 101 (3), 237–255.CrossRefGoogle Scholar
Lloyd, J. 1987. Foundations of Logic Programming, 2nd ed. Symbolic Computation. Springer-Verlag.CrossRefGoogle Scholar
McCarthy, J. 1980. Circumscription—A form of nonmonotonic reasoning. Artificial Intelligence 13 (1–2), 27–39.CrossRefGoogle Scholar
metasp. http://www.cs.uni-potsdam.de/wv/metasp.Google Scholar
Oetsch, J., Pührer, J., and Tompits, H. 2010. Catching the ouroboros: On debugging non-ground answer-set programs. Theory and Practice of Logic Programming. Twenty-sixth International Conference on Logic Programming (ICLP'10) Special Issue 10 (4–6), 513–529.Google Scholar
Oikarinen, E. and Janhunen, T. 2008. Implementing prioritized circumscription by computing disjunctive stable models. In Proceedings of the Thirteenth International Conference on Artificial Intelligence: Methodology, Systems, and Applications (AIMSA'08), Dochev, D., Pistore, M. and Traverso, P., Eds. Lecture Notes in Artificial Intelligence, vol. 5253. Springer-Verlag, 167–180.Google Scholar
Reiter, R. 1987. A theory of diagnosis from first principles. Artificial Intelligence 32 (1), 57–96.CrossRefGoogle Scholar
Sakama, C. and Inoue, K. 2000. Prioritized logic programming and its application to commonsense reasoning. Artificial Intelligence 123 (1–2), 185–222.CrossRefGoogle Scholar
Simons, P., Niemelä, I. and Soininen, T. 2002. Extending and implementing the stable model semantics. Artificial Intelligence 138 (1–2), 181–234.CrossRefGoogle Scholar
Syrjänen, T. Lparse 1.0 user's manual [online]. Accessed 9 June 2011. URL: http://www.tcs.hut.fi/Software/smodels/lparse.ps.gz.Google Scholar