Removing propagation redundant constraints in redundant modeling
Publication in refereed journal


Times Cited
Web of Science5WOS source URL (as at 06/07/2020) Click here for the latest count
Altmetrics Information
.

Other information
AbstractA 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 propagation redundant 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.
All Author(s) ListChoi CW, Lee JHM, Stuckey PJ
Journal nameACM Transactions on Computational Logic
Detailed descriptionArticle 23.
Year2007
Month1
Day1
Volume Number8
Issue Number4
PublisherASSOC COMPUTING MACHINERY
ISSN1529-3785
eISSN1557-945X
LanguagesEnglish-United Kingdom
Keywordsconstraint propagation; performance; redundant constraints; redundant modeling; theory
Web of Science Subject CategoriesComputer Science; Computer Science, Theory & Methods; COMPUTER SCIENCE, THEORY & METHODS; Logic; LOGIC; Science & Technology - Other Topics

Last updated on 2020-07-07 at 01:47