Strong Inverse Consistencies for Non-Binary CSPs

Domain filtering local consistencies, such as inverse consistencies, that only delete values and do not add new constraints are particularly useful in constraint programming. Although many such consistencies for binary constraints have been proposed and evaluated, the situation with non-binary constraints is quite different. Only very recently have domain filtering consistencies stronger than GAC started to attract interest. Following this line of research, we define a number of strong inverse consistencies for non-binary constraints and compare their pruning power. We show that three of these consistencies are equivalent to maxRPC in binary CSPs while another is equivalent to PIC. We also describe a generic algorithm for inverse consistencies in non-binary CSPs and show how it can be instantiated to enforce some of the proposed consistencies. Finally, we make a preliminary empirical study that demonstrates the potential of strong inverse consistencies.