Optimization with mode-directed preferences

ABSTRACT

Traditional constraint programming specifies an optimization problem by using a set of constraints and minimizing (or maximizing) objective functions. Unfortunately, general optimization problems may involve compound objectives whose optima are difficult to be represented by a simple minimization (or maximization). Even worse, for many applications, especially those defined over structural domains, it is difficult to specify any objective functions. In this paper we presents a declarative method for specifying generalized optimization problems based on comparison and selection among alternative solutions. The method introduces a formal predicate mode declaration for designating certain predicates as optimization predicates, and uses preference rules for stating the criteria for determining their optimal solutions. We illustrate their uses with two representative examples: one is matrix-chain multiplication from dynamic programming, and the other is ambiguity resolution for recursively-defined grammars. This paper also addresses how to extend a tabled Prolog system with preferences. The execution of logic programs with preferences is achieved in two steps. First, an automatic transformation is applied to embed the preferences into the problem specification to form an executable program. Second, the new program is then evaluated using tabled resolution, while the mode declaration provides a selection mechanism among the alternative solutions. We show that the transformation scheme preserves the semantics for each optimization predicate. Experimental results are shown to indicate that preferences provide a declarative approach without sacrificing efficiency.

REFERENCES

• 1: Applied Logic Systems, Inc. http://www.als.com
• 2: A. Brown, S. Mantha, and T. Wakayama: Preference Logics: Towards a Unified Approach to Non-Monotonicity in Deductive Reasoning. Annals of Mathematics and Artificial Intelligence, 10:233--280, 1994.
• 3: Weidong Chen , David S. Warren, Tabled evaluation with delaying for general logic programs, Journal of the ACM (JACM), v.43 n.1, p.20-74, Jan. 1996 [doi>10.1145/227595.227597]
• 4: Baoqiu Cui , Terrance Swift, Preference logic grammars: fixed point semantics and application to data standardization, Artificial Intelligence, v.138 n.1-2, p.117-147, June 2002 [doi>10.1016/S0004-3702(02)00185-6]
• 5: M. H. Van Emden , R. A. Kowalski, The Semantics of Predicate Logic as a Programming Language, Journal of the ACM (JACM), v.23 n.4, p.733-742, Oct. 1976 [doi>10.1145/321978.321991]
• 6: François Fages, On the Semantics of Optimization Predicates in CLP Languages, Proceedings of the 13th Conference on Foundations of Software Technology and Theoretical Computer Science, p.193-204, December 15-17, 1993
• 7: Sumit Ganguly , Sergio Greco , Carlo Zaniolo, Minimum and maximum predicates in logic programming, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.154-163, May 29-31, 1991, Denver, Colorado, United States [doi>10.1145/113413.113427]
• 8: K. Govindarajan, B. Jayaraman, and S. Mantha: Preference Logic Programming. In Proceedings of International Conference on Logic Programming (ICLP), pages 731--745, 1995.
• 9: Kannan Govindarajan , Bharat Jayaraman , Surya Mantha, Optimization and relaxation in constraint logic languages, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.91-103, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237735]
• 10: Hai-Feng Guo , Gopal Gupta, A Simple Scheme for Implementing Tabled Logic Programming Systems Based on Dynamic Reordering of Alternatives, Proceedings of the 17th International Conference on Logic Programming, p.181-196, November 26-December 01, 2001
• 11: Hai-Feng Guo and Gopal Gupta: Simplifying Dynamic Programming via Tabling. Practical Aspects of Declarative Languages (PADL), pages 163--177, 2004.
• 12: Hai-Feng Guo , Bharat Jayaraman, Mode-directed preferences for logic programs, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico [doi>10.1145/1066677.1066997]
• 13: J. Hintikka: Knowledge and Belief. Cornell University Press: Ithaca, NY, 1962.
• 14: J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• 15: J. Jaffar and M. J. Maher: Constraint Logic Programming: A Survey. Journal of Logic Programming, Vol. 19/20: pages 503--581, 1994.
• 16: Bharat Jayaraman, Kannan Govindarajan, and Surya Mantha: Preference Logic Grammars. Computer Languages, 24(3): pages 179--196, 1998.
• 17: M.J. Maher and Peter J. Stuckey: Expanding Query power in Constraint Logic Programming Languages. Proceedings of NACLP, 1989.
• 18: Kim Marriott and Peter J. Stuckey: Programming with Constraints: An Introduction. The MIT Press, 1998.
• 19: D. S. Parker, Partial order programming (extended abstract), Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.260-266, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75300]
• 20: F.C.N. Pereira and D.H.D. Warren: Definite Clause Grammars for Language Analysis - A Survey of the Formalism and a Comparison with Augmented Transition Networks. Artificial Intelligence, 13:231--278, 1980.
• 21: Ricardo Rocha , Fernando M. A. Silva , Vítor Santos Costa, On a Tabling Engine That Can Exploit Or-Parallelism, Proceedings of the 17th International Conference on Logic Programming, p.43-58, November 26-December 01, 2001
• 22: XSB system. http://xsb.sourceforge.net
• 23: M. Wilson and A. Borning: Hierarchical Constraint Logic Programming Journal of Logic Programming, 16:277--318, 1993.
• 24: G.H. von Wright: The Logic of Preference. University of Edinburgh Press, 1963.
• 25: Neng-Fa Zhou, Y. Shen, L. Yuan, and J. You: Implementation of a Linear Tabling Mechanism. Journal of Functional and Logic Programming, 2001(10), 2001.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Syntax

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.6 Logic Programming
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics

General Terms:
Languages

Keywords:
mode, preference logic programming, tabled prolog