Computer Science – Artificial Intelligence
Scientific paper
2011-06-29
Computer Science
Artificial Intelligence
7 pages, Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence (AAAI-11)
Scientific paper
Set and multiset variables in constraint programming have typically been represented using subset bounds. However, this is a weak representation that neglects potentially useful information about a set such as its cardinality. For set variables, the length-lex (LL) representation successfully provides information about the length (cardinality) and position in the lexicographic ordering. For multiset variables, where elements can be repeated, we consider richer representations that take into account additional information. We study eight different representations in which we maintain bounds according to one of the eight different orderings: length-(co)lex (LL/LC), variety-(co)lex (VL/VC), length-variety-(co)lex (LVL/LVC), and variety-length-(co)lex (VLL/VLC) orderings. These representations integrate together information about the cardinality, variety (number of distinct elements in the multiset), and position in some total ordering. Theoretical and empirical comparisons of expressiveness and compactness of the eight representations suggest that length-variety-(co)lex (LVL/LVC) and variety-length-(co)lex (VLL/VLC) usually give tighter bounds after constraint propagation. We implement the eight representations and evaluate them against the subset bounds representation with cardinality and variety reasoning. Results demonstrate that they offer significantly better pruning and runtime.
Law Yat-Chiu
Lee Jimmy Ho-Man
Walsh Toby
Woo May Hiu-Chun
No associations
LandOfFree
A Comparison of Lex Bounds for Multiset Variables in Constraint Programming does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Comparison of Lex Bounds for Multiset Variables in Constraint Programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Comparison of Lex Bounds for Multiset Variables in Constraint Programming will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-359139