Cited By
View all- Correas JMartn SSenz-Prez F(2018)Enhancing set constraint solvers with bound consistencyExpert Systems with Applications: An International Journal10.1016/j.eswa.2017.09.05692:C(485-494)Online publication date: 1-Feb-2018
Integrating Finite Domain and Set Constraints into a Set-based Constraint Language
Pages 227 - 252
Abstract
This paper summarizes a constraint solving technique that is used to reason effectively in the scope of a set-based constraint language that supersedes existing finite domain languages. The first part of this paper motivates the presented work and introduces the constraint language, namely the language of Hereditarily Finite Sets (HFS). Then, the proposed constraint solver is detailed in terms of a set of rewrite rules that exploit finite domain reasoning within the HFS language. The proposed solution improves previous work on CLP (SET) [11] by integrating intervals into the constraint system and by providing a new layered architecture for the solver that supports more effective constraint solving strategies. On the other hand, the proposed approach provides enhanced expressivity and flexibility of domain representation than those usually found in existing finite domain constraint solvers.
References
[1]
APT, K.R. (2003) Principles of Consraint Programming. Cmbridge University Press.
[2]
ARNI, N., GRECO, S., AND SACCÀ, D. (1996) Matching of Bounded Set Terms in the Logic Language LDL++. J. of Logic Programming, 27(1): 73-87.
[3]
AZEVEDO, F. (2007) Cardinal: A Finite Sets Constraint Solver. Constraints, 12(37): 93-129.
[4]
BERGENTI, F., PANEGAI, E., AND ROSSI, G. (2006) A Master-Slave Architecture to Integrate Sets and Finite Domains in Java. Presented at CILC'06 - Convegno Italiano di Logica Computazionale, Bari.
[5]
BOUQUET, F., LEGEARD, B., AND PEUREUX, F. (2002) CLPS-B - a constraint solver for B. In Tools and Algorithms for the Construction and Analysis of Systems, Vol. 2280 of LNCS, Springer Verlag, 188-204.
[6]
CODOGNET, P., AND DIAZ, D. (1996) Compiling constraints in CLP(FD). Journal of Logic Programming, 27(3): 185-226.
[7]
CUCCHIARA, R., GAVANELLI, M., LAMMA, E., MELLO, P., MILANO, M., PICCARDI, M. (online) Extending the CSP Model to Cope With Partial Information. Available at: http://lia.deis.unibo.it/Research/Areas/icsp
[8]
DAL PALÙ, A., DOVIER, A., PONTELLI, E., AND ROSSI, G. (2003) Integrating Finite Domain Constraints and CLP with Sets. In D. Miller, ed., Fifth ACM-SIGPLAN International Conference on Principles and Practice of Declarative Programming, ACM Press, 219-229.
[9]
DAL PALÙ, A., DOVIER, A., PONTELLI, E., AND ROSSI, G. (2006) Constraint Logic Programming Language for Effective Programming with Sets and Finite Domains. Research Report "Quaderno del Dipartimento di Matematica", 437, Università di Parma.
[10]
DOVIER, A., OMODEO, E. G., PONTELLI, E., AND ROSSI, G. (1996) {log}: A Language for Programming in Logic with Finite Sets. Journal of Logic Programming, 28(1): 1-44.
[11]
DOVIER, A., PIAZZA, C., PONTELLI, E., AND ROSSI, G. (2000) Sets and Constraint Logic Programming. ACM Transactions on Programming Languages and Systems, 22(5): 861-931.
[12]
DOVIER, A., PONTELLI, E., AND ROSSI, G. (2006) Set unification. Theory and Practice of Logic Programming, 6: 645-701.
[13]
FLENER, P., HNICH, B., AND KIZILTAN, Z. (2001) Compiling high-level type constructor in constraint programming. In I.V. Ramakrishnan ed., Practical Aspects of Declarative Languages, Vol. 1990 of LNCS, Springer Verlag, pp. 229-244.
[14]
FLENER, P., PEARSON, J., AND AGREN. M. (2004) Introducing ESRA, a relational language for modeling combinatorial problems. In M. Bruynooghe ed., LOPSTR'03: Revised Selected Papers, pp. 214-232, Springer-Verlag.
[15]
FOURER, R., GAY, D., AND KERNIGHAN, B.W. (1993) AMPL: a modeling language for mathematical programming. The Scientific Press.
[16]
FRÜHWIRTH, T. (1998) Theory and practice of constraint handling rules. J. of Logic Programming, 37(1-3): 95-138.
[17]
GAVANELLI M., LAMMA E., MELLO P., AND MILANO, M. (2005) Dealing with incomplete knowledge on CLP(FD) variable domains. ACM Transactions on Programming Languages and Systems, 27(2): 236-263.
[18]
GERVET, C. (1997) Interval Propagation to Reason about Sets: Definition and Implementation of a Practical Language. Constraints, 1(3): 191-244.
[19]
GERVET, C. (2006) Constraints over Structured Domains. In Rossi, F. van Beek, P., and Walsh, T. (Eds.), Handbook of Constraint Programming, Elsevier.
[20]
GRECO S. (1996) Optimal Unification of Bound Simple Set Terms. In Proc. of Conf. on Information and Knowledge Management, 326-336, ACM Press.
[21]
HOFSTEDT, P. (2000) Cooperating Constraint Solvers. In Dechter, R. (Ed.), International Conference on Principle and Practice of Constraint Programming, Vol. 1894 of LNCS, Springer Verlag, 520-524.
[22]
IC PARC (2003) The ECLiPSe Constraint Logic Programming System. London. www.icparc.ic.ac.uk/ eclipse/.
[23]
LECONTE, M. (1996) A bounds-based reduction scheme for constraints of difference. In Proceedings of the Constraint-96 International Workshop on Constraint-Based Reasoning, pp. 19-28.
[24]
NORBERG, M. (2006) Writing a compiler for the finite domain CSP modeling language ESRA. Master's Thesis, Department of Information Technology, Uppsala University.
[25]
PANDINI, D. (2008) Progettazione e realizzazione in Java di un risolutore di vincoli su domini finiti. Tesi di Laurea, Dipartimento di Matematica, Università degli Studi di Parma.
[26]
ROSSI, G. (2005) The {log} Constraint Logic Programming Language. prmat.math.unipr.it/~gianfr/ setlog.Home.html.
[27]
ROSSI, G., PANEGAI, E., AND POLEO, E. (2007) JSetL: A Java Library for Supporting Declarative Programming in Java. Software-Practice & Experience, 37: 115-149.
[28]
VAN ROY, P. (ED.) (2005) Multiparadigm Programming in Mozart/Oz. Lecture Notes in Computer Science 3389 Springer 2005, ISBN 3-540-25079-4.
[29]
SWEDISH INSTITUTE OF COMPUTER SCIENCE. The SICStus Prolog Home Page. www.sics.se.
[30]
VAN HENTENRYCK, P., MICHEL, L., AND DEVILLE, Y. (1997) Numerica: a modeling language for global optimization. MIT Press.
[31]
WIELEMAKER, J. (2004) SWI-Prolog Reference Manual (Version 5.4). University of Amsterdam.
[32]
ZHOU, N-F. (2005) B-Prolog User's Manual (Version 6.8). Afany Software.
- Integrating Finite Domain and Set Constraints into a Set-based Constraint Language
Recommendations
Integrating Finite Domain and Set Constraints into a Set-based Constraint Language
Advances in Computational Logic (CIL C08)This paper summarizes a constraint solving technique that is used to reason effectively in the scope of a set-based constraint language that supersedes existing finite domain languages. The first part of this paper motivates the presented work and ...
Enhancing set constraint solvers with bound consistency
New set constraints to enhance constraint solvers.Finite domain and set domain solvers cooperate.Reduced search space and improved performance of constraint solvers.A prototype implementation is developed.Relevant improvement with respect to the Eclipse ...
Solving Hierarchical Constraints over Finite Domains with Local Search
Many real world problems have requirements and constraints which conflict with each other. One approach for dealing with such over-constrained problems is with constraint hierarchies. In the constraint hierarchy framework, constraints are classified into ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
IOS Press
Netherlands
Publication History
Published: 01 August 2009
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 03 Jan 2025
Other Metrics
Citations
Cited By
View all- Correas JMartn SSenz-Prez F(2018)Enhancing set constraint solvers with bound consistencyExpert Systems with Applications: An International Journal10.1016/j.eswa.2017.09.05692:C(485-494)Online publication date: 1-Feb-2018