Achieving Domain Consistency and Counting Solutions for Dispersion Constraints
INFORMS Journal on Computing · 2015 · Volume 27 · Issue 4
Abstract
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.
Keywords
combinatorial optimization, constraint programming, balance, spread constraint, deviation constraint, filtering algorithms, branching heuristics, counting-based search
Enable JavaScript for citation tools and additional paper interactions.