Structuring Techniques for Constraint Satisfaction Problems

Abstract

We present a structuring method for discrete constraint satisfaction problems (CSPs). It takes advantage of interchangeabilities to represent sets of equivalent values by meta-values and thus obtain more compact representations. Strongly related variables are clustered into meta-variables to create occurrences of interchangeabilities. By iterative application, a CSP can be transformed into an hierarchy of equivalent CSPs, where each problem is significantly simpler than the original one. This structure is particularly advantageous when a large set of possible solutions must be inspected. 1 Introduction We consider binary CSPs defined by P = (X; D;C;R), where X = fX 1 ; : : : ; Xng is a set of variables, D = fD 1 ; : : : ; Dng a set of finite domains associated with the variables, C = fC 1 ; : : : ; Cm g a set of constraints, and R =fR ij ` D i \\Theta D j for C ij applicable to X i and X j g a set of relations that define the value combinations allowed by the constraints. Solving s...