Skip to main content
SpringerLink
Log in

Cardinal: A Finite Sets Constraint Solver

  • Published:
Constraints Aims and scope Submit manuscript

Abstract

In this paper we present Cardinal, a general finite sets constraint solver just made publicly available in ECLiPSe Constraint System, suitable for combinatorial problem solving by exploiting inferences over sets cardinality. In fact, to deal with set variables and set constraints, existing set constraint solvers are not adequate to handle a number of problems, as they do not actively use important information about the cardinality of the sets, a key feature in such problems. Cardinal is formally presented as a set of rewriting rules on a constraint store and we illustrate its efficiency with experimental results. We show the importance of propagating constraints on sets cardinality, by comparing Cardinal with other solvers. Another contribution of this paper is on modelling: we focus essentially on digital circuits problems, for which we present new modelling approaches and prove that sets alone can be used to model these problems in a clean manner and solve them efficiently using Cardinal. Results on a set of diagnostic problems show that Cardinal obtains a speed up of about two orders of magnitude over Conjunto, a previous available set constraint solver, which uses a more limited amount of constraint propagation on cardinalities. Additionally, to further extend modelling capabilities and efficiency, we generalized Cardinal to actively consider constraints over set functions other than cardinality. The Cardinal version just released allows declaring union, minimum and maximum functions on set variables, and easily constraining those functions, letting Cardinal especial inferences efficiently take care of different problems. We describe such extensions and discuss its potentialities, which promise interesting research directions.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aiken, A. (1994). Set constraints: results, applications and future directions. In Borning, A., ed., In Proceedings of the 2nd International Workshop on Principles and Practice of Constraint Programming (PPCP’94), pages 326–335. Springer.

  2. Azevedo, F. (2003). Solving over multi-valued logics—application to digital circuits. Frontiers of artificial intelligence and applications, ISBN: 1 58603 304 2, IOS, vol 91, xviii + 204 pages.

  3. Azevedo, F., & Barahona, P. (1999). Benchmarks for differential diagnosis, at URL http://ssdi.di.fct.unl.pt/~fa/differential-diagnosis/benchmarks.html.

  4. Azevedo, F., & Barahona, P. (2000). Applications of an extended set constraint solver. In Proceedings of the 2000 ERCIM/CompulogNet Workshop on Constraints.

  5. Azevedo, F., & Barahona, P. (2000). Differentiating diagnostic theories through constraints over an eight-valued logic. In Horn, W., ed., Proceedings of the 14th European Conference on Artificial Intelligence (ECAI’2000), pages 73–77. IOS, Amsterdam.

  6. Azevedo, F., & Barahona, P. (2000). Digital circuits problems with set constraints. In John Lloyd et al., ed., Proceedings of the First International Conference on Computational Logic (CL’2000), pages 414–428. Springer.

  7. Beasley, J. E. (1990). OR-library: distributing test problems by electronic mail, at URL http://mscmga.ms.ic.ac.uk/jeb/orlib, originally described in J. Oper. Res. Soc. 41(11):1069–1072.

    Google Scholar 

  8. Benhamou, F. (1995). Interval constraint logic programming, in constraint programming: basics and trends. In Podelski, A. ed., LNCS 910. Springer, March.

  9. Birkhoff, G. (1967). Lattice theory. Colloquium Publications, American National Society, vol. 25.

  10. Caseau, Y., Josset, F.-X., & Laburthe, F. (1999). CLAIRE: combining sets, search and rules to better express algorithms. Proceedings of the 16th International Conference on Logic Programming (ICLP’99), pages 245–259.

  11. Charatonik, W., & Podelski, A. (1996). The independence property of a class of set constraints. In Freuder, E. C., ed., Proceedings of the 2nd International Conference on Principles and Practice of Constraint Programming (CP’96), pages 76–90. Springer.

  12. Cheeseman, P., Kanefsky, B., & Taylor, W. (1991). Where the really hard problems are. Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI-91), vol. 1, pages 331–337.

  13. Colbourn, C. J., & Dinitz, J. H., ed., Steiner triple systems. CRC Handbook of Combinatorial Designs. CRC, pages 14−15 and 70, Boca Raton, FL.

  14. Correia, M., Barahona, P., & Azevedo, F. (2005). CaSPER: A programming environment for development and integration of constraint solvers. In Azevedo et al. ed., Proceedings of the First International Workshop on Constraint Programming Beyond Finite Integer Domains (BeyondFD’05), pages 59–73, 2005.

  15. CPLEX (1988), in http://www.cplex.com.

  16. Devienne, P., Talbot, J. M., & Tison, S. (1997). Solving classes of set constraints with tree automata. In Smolka, G., ed., Proceedings of the 3rd International Conference on Principles and Practice of Constraint Programming (CP’97), pages 62–76. Springer.

  17. ECRC (1994). ECLiPSe (a) user manual, (b) extensions of the user manual. Technical Report, ECRC.

  18. Frühwirth, T. (1995). Constraint handling rules, in constraint programming: basics and trends. In Podelski, A., ed., LNCS 910. Springer.

  19. Gent, I. P., & Walsh, T. (1999). CSPLib: a benchmark library for constraints. Technical report APES-09-1999. Available at http://www-users.cs.york.ac.uk/~tw/csplib. A shorter version appears in Proceedings of the 5th International Conference on Principles and Practices of Constraint Programming (CP-99).

  20. Gervet, C. (1994). Conjunto: constraint logic programming with finite set domains. In Bruynooghe, M., ed., International Symposium on Logic Programming. Cambridge MA, MIT.

    Google Scholar 

  21. Gervet, C. (1997). Interval propagation to reason about sets: definition and implementation of a practical language. Constraints International Journal, vol. 1, no. 3, Kluwer, pages 191–244, March.

  22. Gierz, G., & Hoffman, K. H., et al. (1980). A compendium of continuous lattices. Springer.

  23. Graetzer, G. (1971). LATTICE THEORY: first concepts and distributive lattices. Freeman.

  24. Hawkins, P., Lagoon, V., & Stuckey, P. J. (2004). Set bounds and (split) set domain propagation using ROBDDs. In Proceedings of the 17th Australian Joint Conference on Artificial Intelligence, LNCS 3339, pages 706−717. Springer, Berlin Heidelberg New York.

    Google Scholar 

  25. Heintze, N., & Jaffar, J. (1994). Set constraints and set-based analysis. In Borning, A., ed., Proceedings of the 2nd International Workshop on Principles and Practice of Constraint Programming (PPCP’94), pages 281–298. Springer.

  26. ISCAS (1985). Special session on ATPG. In Proceedings of the IEEE Symposium on Circuits and Systems, pages 663–698, Kyoto, Japan, July.

  27. Lagoon, V., & Stuckey, P. J. (2004). Set domain propagation using ROBDDs. Proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming, LNCS 3258, pages 347−361. Springer, Berlin Heidelberg New York.

  28. Pacholski, L., & Podelski, A. (1997). Set constraints: a pearl in research on constraints. In Smolka, G., ed., Proceedings of the 3rd International Conference on Principles and Practice of Constraint Programming (CP’97), pages 2–5, Springer.

  29. Puget, J.-F. (1992). PECOS a high level constraint programming language. In Proceedings of Spicis 92.

  30. Sadler, A., & Gervet, C. (2004). Hybrid set domains to strengthen constraint propagation and reduce symmetries. Proceedings of Principles and Practice of Constraint Programming (CP 2004), vol. 3258.

  31. Silva, L. G., Silveira, L. M., & Marques-Silva, J. P. (1999). Algorithms for solving boolean satisfiability in combinational circuits. Proceedings of the IEEE/ACM Design and Test in Europe Conference (DATE).

  32. Zhou, N.-F. (2000). Programming constraint propagation in reactive rules. Proceedings of the 1st International Workshop on Rule-based Constraint Reasoning and Programming.

Download references

Author information

Authors and Affiliations

  1. Departamento de Informática, CENTRIA, FCT/UNL, Monte da Caparica, Portugal

    Francisco Azevedo

Authors
  1. Francisco Azevedo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Francisco Azevedo.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Azevedo, F. Cardinal: A Finite Sets Constraint Solver. Constraints 12, 93–129 (2007). https://doi.org/10.1007/s10601-006-9012-6

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10601-006-9012-6

Keywords

Search

Navigation