Cardinal
Cardinal: a finite sets constraint solver. 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 software is also peer reviewed by journal TOMS.
This software is also peer reviewed by journal TOMS.
Keywords for this software
References in zbMATH (referenced in 10 articles , 1 standard article )
Showing results 1 to 10 of 10.
Sorted by year (- Cristiá, Maximiliano; Rossi, Gianfranco: Solving quantifier-free first-order constraints over finite sets and binary relations (2020)
- Cristiá, Maximiliano; Rossi, Gianfranco: A decision procedure for sets, binary relations and partial functions (2016)
- Law, Y. C.; Lee, J. H. M.; Walsh, T.; Woo, M. H. C.: Multiset variable representations and constraint propagation (2013)
- Benchimol, Pascal; van Hoeve, Willem-Jan; Régin, Jean-Charles; Rousseau, Louis-Martin; Rueher, Michel: Improved filtering for weighted circuit constraints (2012)
- Gange, G.; Stuckey, P. J.; Lagoon, V.: Fast set bounds propagation using a BDD-SAT hybrid (2010)
- Bergenti, Federico; Dal Palù, Alessandro; Rossi, Gianfranco: Integrating finite domain and set constraints into a set-based constraint language (2009)
- Viegas, Ruben Duarte; Azevedo, Francisco: Lazy constraint imposing for improving the path constraint (2009)
- Deville, Yves; Dooms, Grégoire; Zampelli, Stéphane: Combining two structured domains for modeling various graph matching problems (2008)
- Azevedo, Francisco: An attempt to dynamically break symmetries in the social golfers problem (2007)
- Azevedo, Francisco: Cardinal: a finite sets constraint solver (2007)