Removing propagation redundant constraints in redundant modeling
Author
Choi, CW; Lee, JHM; Stuckey, PJDate
2007-01-01Source Title
ACM Transactions on Computational LogicPublisher
ASSOC COMPUTING MACHINERYUniversity of Melbourne Author/s
Stuckey, PeterAffiliation
Computer Science and Software EngineeringMetadata
Show full item recordDocument Type
Journal ArticleCitations
Choi, C. W., Lee, J. H. M. & Stuckey, P. J. (2007). Removing propagation redundant constraints in redundant modeling. ACM TRANSACTIONS ON COMPUTATIONAL LOGIC, 8 (4), https://doi.org/10.1145/1276920.1276925.Access Status
This item is currently not available from this repositoryAbstract
<jats:p>
A widely adopted approach to solving constraint satisfaction problems combines systematic tree search with various degrees of constraint propagation for pruning the search space. One common technique to improve the execution efficiency is to add redundant constraints, which are constraints logically implied by others in the problem model. However, some redundant constraints are
<jats:italic>propagation redundant</jats:italic>
and hence do not contribute additional propagation information to the constraint solver. Redundant constraints arise naturally in the process of redundant modeling where two models of the same problem are connected and combined through channeling constraints. In this paper, we give general theorems for proving propagation redundancy of one constraint with respect to channeling constraints and constraints in the other model. We illustrate, on problems from CSPlib (http://www.csplib.org), how detecting and removing propagation redundant constraints in redundant modeling can speed up search by several order of magnitudes.
</jats:p>
Keywords
Artificial Intelligence and Image ProcessingExport Reference in RIS Format
Endnote
- Click on "Export Reference in RIS Format" and choose "open with... Endnote".
Refworks
- Click on "Export Reference in RIS Format". Login to Refworks, go to References => Import References