Achieving Domain Consistency and Counting Solutions for Dispersion Constraints
针对约束编程中表达变量平衡的分散约束，提出了高效的域一致性过滤算法，并扩展至解计数以支持基于计数的搜索，在基准问题上验证了效果。
Many combinatorial problems require that their solutions achieve a certain balance of given features. For this important aspect of modeling, the spread and deviation constraints have been proposed in Constraint Programming to express balance among a set of variables by constraining their mean and overall deviation from the mean. To our knowledge, the only practical filtering algorithms known for these constraints achieve bounds consistency. In this paper we improve that filtering by presenting an efficient domain consistency algorithm that applies to both constraints. We also extend it to count solutions so that it can be used in counting-based search, a generic and effective family of branching heuristics that free the user from having to write problem-specific search heuristics. We provide a time complexity analysis of our contributions and empirically evaluate them on benchmark problems.