Removing Propagation Redundant Constraints in Redundant Modeling

Details Removing Propagation Redundant Constraints in Redundant Modeling Removing Propagation Redundant Constraints in Redundant Modeling

2004-12-07

arxiv.org/abs/cs/0412026v1

Computer Science

Logic in Computer Science

30 pages, submitted to ACM Transactions on Computational Logic (TOCL)

Scientific paper

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 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 significantly speed up constraint solving.

Affiliated with

Also associated with

No associations

Rating

Removing Propagation Redundant Constraints in Redundant Modeling does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Removing Propagation Redundant Constraints in Redundant Modeling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Removing Propagation Redundant Constraints in Redundant Modeling will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-76829