Malcolm Ryan wrote: > understand it, the usual approach is to iteratively find a solution > with X = x1, then add the constraint X < x1 and repeat until no more > solutions can be found. Is this correct?
Yes, this is one usual way, even though there variations thereof and simply other methods. For example, you may simply take X as the first variable for distribution, starting from lower values. > It occurs to me that each iteration only makes the problem more > constrained, so assignments which failed in one iteration will > continue to fail in all subsequent iterations. Is there any standard > way to make use of this information to prune the search? Well, what you say is correct and there are systems (Mozart - www.mozart-oz.org - which heavily influenced gecode) which do exactly that. I am pretty sure gecode applies similar concepts, which are organized around the basic notion of spaces (class Space). Suppose you have a stage in solving you think is "reusable". Any such stage of a CSP will be realized as a Space instance encapsulating all current basic constraints and propagators. So what is usually done is: instead of injecting a new distribution constraint directly into the reusable Space S, what is usually done is (i) create a clone S' of S (that's what Space::clone is for) and (ii) inject the new constraints into S' (or S) and save S (or S') for later. I am sure Gecode's optimization primitives incorporate these ideas to avoid recomputation. However, cloning may be an expensive operation, so a controlled amount of recomputation is sometimes desirable. Cheers, Jorge. _______________________________________________ Gecode users mailing list [EMAIL PROTECTED] https://www.gecode.org/mailman/listinfo/gecode-users
