摘要翻译：
在约束规划中，集合和多集合变量通常用子集界表示。然而，这是一种弱表示，忽略了关于集合的潜在有用信息，如它的基数。对于集合变量，lengt-lex(LL)表示成功地提供了关于长度（基数）和词典排序中位置的信息。对于元素可以重复的多集变量，我们考虑考虑附加信息的更丰富的表示。我们研究了八种不同的表示，在这些表示中，我们根据八种不同的顺序之一来保持界限：长度-（co）lex(LL/LC)、多样性-（co）lex(VL/VC)、长度-多样性-（co）lex（LVL/LVC）和多样性-长度-（co）lex（VLL/VLC）顺序。这些表示将关于基数、多样性（多集中不同元素的数量）和位置的信息集成在一起，以某种总的顺序。通过对八种表征的表达性和紧凑性的理论和经验比较，发现长度-多样性-（co）lex（LVL/LVC）和多样性-长度-（co）lex（VLL/VLC）在约束传播后通常给出更紧的界限。我们实现了这八种表示，并用基数和多样性推理对子集界表示进行了评估。结果表明，它们提供了明显更好的剪枝和运行时间。
---
英文标题：
《A Comparison of Lex Bounds for Multiset Variables in Constraint
  Programming》
---
作者：
Yat-Chiu Law and Jimmy Ho-Man Lee and May Hiu-Chun Woo and Toby Walsh
---
最新提交年份：
2011
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--

---
英文摘要：
  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.
---
PDF链接：
https://arxiv.org/pdf/1106.5890