Decomposition of the NVALUE constraint

Details Decomposition of the NVALUE constraint Decomposition of the NVALUE constraint

2010-07-05

arxiv.org/abs/1007.0603v1

Computer Science

Artificial Intelligence

To appear in the Proceedings of the 16th International Conference on Principles and Practice of Constraint Programming 2010 (C

Scientific paper

We study decompositions of the global NVALUE constraint. Our main contribution is theoretical: we show that there are propagators for global constraints like NVALUE which decomposition can simulate with the same time complexity but with a much greater space complexity. This suggests that the benefit of a global propagator may often not be in saving time but in saving space. Our other theoretical contribution is to show for the first time that range consistency can be enforced on NVALUE with the same worst-case time complexity as bound consistency. Finally, the decompositions we study are readily encoded as linear inequalities. We are therefore able to use them in integer linear programs.

Affiliated with

Also associated with

No associations

Rating

Decomposition of the NVALUE constraint 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 Decomposition of the NVALUE constraint, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decomposition of the NVALUE constraint will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-594156