A comparison of lex bounds for multiset variables in constraint programming
Refereed conference paper presented and published in conference proceedings


全文

其它資訊
摘要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. Copyright © 2011, Association for the Advancement of Artificial Intelligence. All rights reserved.
著者Law Y.C., Lee J.H.M., Woo M.H.C., Walsh T.
會議名稱25th AAAI Conference on Artificial Intelligence and the 23rd Innovative Applications of Artificial Intelligence Conference, AAAI-11 / IAAI-11
會議開始日07.08.2011
會議完結日11.08.2011
會議地點San Francisco, CA
會議國家/地區美國
出版年份2011
月份11
日期2
卷號1
頁次61 - 67
國際標準書號9781577355083
語言英式英語

上次更新時間 2020-01-06 於 23:46