Abstract
We propose an abstraction scheme for soft constraint problems and we study its main properties. Processing the abstracted version of a soft constraint problem can help us in many ways: for example, to find good approximations of the optimal solutions, or also to provide us with information that can make the subsequent search for the best solution easier. The results of this paper show that the proposed scheme is promising; thus they can be used as a stable formal base for any experimental work specific to a particular class of soft constraint problems.
Keywords
- Constraint Satisfaction
- Constraint Satisfaction Problem
- Soft Constraint
- Abstract Domain
- Concrete Problem
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
This is a preview of subscription content, log in via an institution.
Buying options
Tax calculation will be finalised at checkout
Purchases are for personal use only
Learn about institutional subscriptionsPreview
Unable to display preview. Download preview PDF.
References
G. Birkhoff and S. MacLane. A Survey of Modern Algebra. MacMillan, 1965.
S. Bistarelli, H. Fargier, U. Montanari, F. Rossi, T. Schiex, and G. Verfaillie. Semiring-based CSPs and valued CSPs: Basic properties and comparison. In Over-Constrained Systems. Springer-Verlag, LNCS 1106, 1996.
S. Bistarelli, U. Montanari, and F. Rossi. Constraint Solving over Semirings. In Proc. IJCAI95. Morgan Kaufman, 1995.
S. Bistarelli, U. Montanari, and F. Rossi. Semiring-based Constraint Solving and Optimization. Journal of the ACM, 44(2):201–236, March 1997.
P. Cousot and R. Cousot. Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Fourth ACM Symp. Principles of Programming Languages, pages 238–252, 1977.
P. Cousot and R. Cousot. Systematic design of program analyis. In Sixth ACM Symp. Principles of Programming Languages, pages 269–282, 1979.
S. de Givry, G. Verfaille, and T. Schiex. Bounding The Optimum of Constraint Optimization Problems. In G. Smolka, editor, Proc. CP97, pages 405–419. Springer-Verlag, LNCS 1330, 1997.
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.
Thomas Ellman. Synthesis of abstraction hierarchies for constraint satisfaction by clustering approximately equivalent objects. In Proceedings of International Conference on Machine Learning, pages 104–111, 1993.
H. Fargier and J. Lang. Uncertainty in constraint satisfaction problems: a probabilistic approach. In Proc. European Conference on Symbolic and Qualitative Approaches to Reasoning and Uncertainty (ECSQARU), pages 97–104. Springer-Verlag, LNCS 747, 1993.
E. C. Freuder. Eliminating interchangeable values in constraint satisfaction subproblems. In Proc. AAAI-91, 1991.
E. C. Freuder and D Sabin. Interchangeability supports abstraction and reformulation for constraint satisfaction. In Proceedings of Symposium on Abstraction, Reformulation and Approximation (SARA’95), 1995. http://www.cs.unh.edu/csprojects/csp/csp.html.
E. C. Freuder and R. J. Wallace. Partial constraint satisfaction. AI Journal, 58, 1992.
Y. Georget and P. Codognet. Compiling semiring-based constraints with clp(fd,s). In M. Maher and J-F. Puget, editors, Proc. CP98. Springer-Verlag, LNCS 1520, 1998.
F. Giunchiglia, A. Villafiorita, and T. Walsh. Theories of abstraction. AI Communication, 10(3–4):167–176, 1997.
F. Giunchiglia and T. Walsh. A theory of abstraction. Artificial Intelligence, 56(2–3):323–390, 1992.
A.K. Mackworth. Consistency in networks of relations. Artificial Intelligence, 8(1):99–118, 1977.
A.K. Mackworth. Constraint satisfaction. In Stuart C. Shapiro, editor, Encyclopedia of AI (second edition), volume 1, pages 285–293. John Wiley & Sons, 1992.
Zs. Ruttkay. Fuzzy constraint satisfaction. In Proc. 3rd IEEE International Conference on Fuzzy Systems, pages 1263–1268, 1994.
T. Schiex. Possibilistic constraint satisfaction problems, or “how to handle soft constraints?”. In Proc. 8th Conf. of Uncertainty in AI, pages 269–275, 1992.
T. Schiex, H. Fargier, and G. Verfaille. Valued Constraint Satisfaction Problems: Hard and Easy Problems. In Proc. IJCAI95, pages 631–637. Morgan Kaufmann, 1995.
R. Schrag and D. Miranker. An evaluation of domain reduction: Abstraction for unstructured csps. In Proceedings of the Symposium on Abstraction, Reformulation, and Approximation, pages 126–133, 1992. http://www.cs.utexas.edu/users/schrag/SARA.ps.
M. Wallace. Practical applications of constraint programming. Constraints: An International Journal, 1, 1996.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bistarelli, S., Codognet, P., Georget, Y., Rossi, F. (2000). Abstracting Soft Constraints. In: Apt, K.R., Monfroy, E., Kakas, A.C., Rossi, F. (eds) New Trends in Constraints. WC 1999. Lecture Notes in Computer Science(), vol 1865. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44654-0_6
Download citation
DOI: https://doi.org/10.1007/3-540-44654-0_6
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67885-4
Online ISBN: 978-3-540-44654-5
eBook Packages: Springer Book Archive