[gecode-users] Pruning search in optimisation problems

[Jorge Marques Pelizzoni]

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.