Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Soft constraints are a generalization of classical constraints, where constraints and/or partial assignments are associated to preference or importance levels, and constraints are combined according to combinators which express the desired optimization criteria. Constraint Handling Rules (CHRs) constitute a high-level natural formalism to specify constraint solvers and propagation algorithms. In this paper we present a framework to design and specify soft constraint solvers by using CHRs. In this way, we extend the range of applicability of CHRs to soft constraints rather than just classical ones, and we provide a straightforward implementation for soft constraint solvers.

REFERENCES

• 1: S. Bistarelli. Soft Constraints Solving and programming: a general framework. PhD thesis, Dipartimento di Informatica, Universitä di Pisa, Italy, mar 2001. TD-2/01.
• 2: Stefano Bistarelli , Ugo Montanari , Francesca Rossi, Semiring-based constraint satisfaction and optimization, Journal of the ACM (JACM), v.44 n.2, p.201-236, March 1997 [doi>10.1145/256303.256306]
• 3: A. Borning, M. Maher, A. Martindale, and. M. Wilson. Constraint hierarchies and logic programming. In Proc. 6th International Conference on Logic Programming, pages 149-164. MIT Press, 1989.
• 4: M. Carlsson and J. Widen. SICStus Prolog User's Manual. on-line version at http://www.sics.se/sicstus/. Technical report, Swedish Institute of Computer Science (SICS), 1999.
• 5: P. Codognet and D. Diaz. Compiling constraints in clp(fd). The Journal of Logic Programming, 27(3), 1996.
• 6: D. Dubois, H. Fargier, and H. Prade. The calculus of fuzzy restrictions as a basis for flexible constraint satisfaction. In Proc. IEEE International Conference on Fuzzy Systems, pages 1131-1136. IEEE, 1993.
• 7: Eugene C. Freuder , Richard J. Wallace, Partial constraint satisfaction, Artificial Intelligence, v.58 n.1-3, p.21-70, Dec. 1992 [doi>10.1016/0004-3702(92)90004-H]
• 8: T. Frühwirth. Theory and practice of constraint handling rules. Journal of Logic Programming - Special Issue on Constraint Logic Programming, 37(1-3):95-138, oct-dec 1998.
• 9: Yan Georget , Philippe Codognet, Compiling Semiring-Based Constraints with clp (FD, S), Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming, p.205-219, October 26-30, 1998
• 10: K. Marriott and P. Stuckey. Programming with Constraints. MIT Press, 1998.
• 11: Vijay A. Saraswat, Concurrent constraint programming, MIT Press, Cambridge, MA, 1993
• 12: E. P. K. Tsang. Foundations of Constraint Satisfaction. Academic Press, 1993.
• 13: Pascal Van Hentenryck, Constraint satisfaction in logic programming, MIT Press, Cambridge, MA, 1989
• 14: Pascal Van Hentenryck , Laurent Perron , Jean-François Puget, Search and strategies in OPL, ACM Transactions on Computational Logic (TOCL), v.1 n.2, p.285-320, Oct. 2000 [doi>10.1145/359496.359529]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Constrained optimization

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms, Design, Experimentation, Performance, Theory

Keywords:
constraint programming, constraint reasoning algorithms