Propagation Redundancy for Permutation Channels

Chiu Wo Choi, Jimmy Ho-Man Lee, Peter J. Stuckey

Abstract

Finding a good model of a constraint satisfaction problem (CSP) is a challenging task. A modeller must specify a set of constraints that capture the definitions of the problem, and the model should also have strong propagation. In other words, the model should be able to quickly reduce the domains of the variables of the problem, and the implementation of these propagators should be efficient, and the search space should not be too large. A problem can be modelled differently from two viewpoints using two different sets of variables. In redundant modelling [Cheng et al., 1999], we connect the two different models with channelling constraints, which relates valuations in the two different models stronger propagation behaviour can be observed. However, the additional variables and constraints impose extra computation overhead may outweigh the gain of reduction in search space. In this paper we consider redundant models connected by permutation channels, which commonly arise when the underlying problem is some form of assignment problem. Since each model is complete and only admits the solutions of the problem, each model is logically redundant with respect to the other model plus the permutation channel. In order to keep the benefits of redundant modelling without paying all the costs, We give a theorem which allows us to determine when we can eliminate constraints in the mutually redundant models that do not give extra propagation. Due to space limitations, we state the theorem without proof.
BibTeX
@inproceedings{choi2003propagation,
  author = {Chiu Wo Choi and Jimmy Ho-Man Lee and Peter J. Stuckey},
  title = {{Propagation Redundancy for Permutation Channels}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2003},
}
Figure