Propagation Redundancy for Permutation Channels
Lists
Only you see this
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},
}| Removing propagation redundant constraints in redundant modeling | arXiv · 2004 |
| Making Bound Consistency as Effective as Arc Consistency | IJCAI · 2009 |
| Channeling Constraints and Value Ordering in the QuasiGroup Completion Problem | IJCAI · 2003 |
| Combining Symmetry Breaking and Global Constraints | arXiv · 2009 |
| Dominance breaking constraints | Constraints An Int. J · 2015 |
| Finite Domain Bounds Consistency Revisited | arXiv · 2004 |