Multiset variable representations and constraint propagation

DOI10.1007/S10601-012-9138-7MaRDI QIDQ481702zbMATH OpenOpenAlexFDO

Authors M. H. C. Woo, Yat Chiu Law, J. H. M. Lee, Toby Walsh

Publication date 12 December 2014

Published in Constraints (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10601-012-9138-7

constraint satisfaction multiset variables

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Combinatorial optimization (90C27)

Review text

The authors study representations of multiset variables from a formal perspective, the consistency and propagation of constraints involving multiset variables. They identify a number of different representations for multiset variables and compare them in terms of effectiveness and efficiency. They propose inference rules to enforce bounds consistency for the representations as well as to exploit the variety (i.e., the number of distinct elements) of a multiset in order to improve the modeling expressiveness and to further enhance constraint propagation. Also, they derive a number of inference rules involving the varieties of multiset variables and show how the traditional components of multiset variables (such as cardinalities) interact with the variables to achieve stronger constraint propagation. Finally, they demonstrate how to apply the rules to perform variety reasoning on some common multiset constraints. Experimental results show that performing variety reasoning on top of cardinality reasoning can effectively reduce the search space and achieve better runtime in solving multiset CSPs.

Recommendations

Cites work

Cited in

(8)

Describes a project that uses

Uses Software

This page was built for publication: Multiset variable representations and constraint propagation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q481702)