Abstract
In this paper we generalize to soft constraints the approximation techniques usually used for local consistency in classical constraint satisfaction and programming. The theoretical results show that this is indeed possible without loosing the fundamental properties of such techniques, and the experimental results (on partial arc-consistency) show that this work can help develop more efficient implementations for logic-based languages working with soft constraints.
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
A. Aggoun and N. Beldiceanu. Overview of the CHIP Compiler System. Constraint Logic Programming: Selected Research, A. Colmerauer and F. Benhamou (Eds.). MIT Press, 1993.
Krysztof R. Apt. The essence of Constraint Propagation. CWI Quarterly vol.11(2 & 3), pp. 215–248, 1998.
C. Bessière. Arc-consistency and Arc-consistency again. Artificial Intelligence, 65(1), 1994.
S. Bistarelli, U. Montanari and F. Rossi. Constraint Solving over Semirings. Proceedings of IJCAI’95, Morgan Kaufman, 1995.
S. Bistarelli, U. Montanari and F. Rossi. Semiring-based Constraint Solving and Optimization. Journal of ACM, vol. 44,no. 2, March 1997.
S. Bistarelli, U. Montanari and F. Rossi. Semiring-based Constraint Logic Programming. Proceedings of IJCAI’97, Morgan Kaufman, 1997.
P. Codognet and D. Diaz. Compiling Constraints in clp(FD). Journal of Logic Programming, vol. 27,no. 3, 1996.
P. Cousot. Asynchronous Iterative Methods for Solving a Fixed Point System of Monotone Equations in a Complete Lattice. Université Scientique et Médicale et Institut National Polytechnique de Grenoble, RR 88, Septembre 1977.
D. Dubois, H. Fargier and H. Prade. The calculus of fuzzy restrictions as a basis for flexible constraint satisfaction. Proc. IEEE International Conference on Fuzzy Systems, IEEE, pp. 1131–1136, 1993.
Y. Georget. Extensions de la Programmation par Contraintes. Ph.D. thesis, Ecole Polytecnique, Paris, to be defended in September 1999.
Y. Georget and P. Codognet. Compiling Semiring-based Constraints with clp(FD,S). Proceedings of CP’98, Springer, 1998.
Y. Georget and P. Codognet. Encoding Global Constraints in Semiring-based Constraint Solving. Proceedings of ICTAI’98, IEEE, 1998.
A. K. Mackworth. Consistency in Networks of Relations. Artificial Intelligence 8 (1977), pp 99–118.
J-F. Puget. A C++ implementation of CLP. Proceedings of SPICIS 94, November 1994.
P. Van Hentenryck. Constraint Satisfaction in Logic Programming. MIT Press, 1989.
P. Van Hentenryck, Y. Deville and C-M. Teng. A generic arc-consistency algorithm and its specializations. Artificial Intelligence 57 (1992), pp 291–321.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bistarelli, S., Codognet, P., Georget, Y., Rossi, F. (1999). Labeling and Partial Local Consistency for Soft Constraint Programming. In: Pontelli, E., Santos Costa, V. (eds) Practical Aspects of Declarative Languages. PADL 2000. Lecture Notes in Computer Science, vol 1753. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46584-7_16
Download citation
DOI: https://doi.org/10.1007/3-540-46584-7_16
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66992-0
Online ISBN: 978-3-540-46584-3
eBook Packages: Springer Book Archive