[gecode-users] Question: stop during a search

[Guido Tack]

On 27/03/2012, at 1:14 AM, Chuong wrote:

> Hi all,
> I have a question about stop during a search.
> Is is possible to stop during a search before fixing all variables?
> For example:
> I have 4 variables a, b, c, d with domain of [0,1].
> After fixing a=0, b=0, I can detect that I have solutions of every combinations 
> of c and d. 
> So it is not effective to branch in c and d (the propagation take more time 
> than counting combinations).
> Is it possible to stop the search at this point and change to a=0, b=1 
> (not a=0, b=0, c=0).

You can do this in different ways, it depends on how you can detect the situation.  The easiest solution is by simply adding constraints that remove the extra solutions.  This is basically static symmetry breaking.  E.g., you could add a constraint (a=00 && b==0) >> (c==0 && d==0), which removes all other solutions for c and d.
If you can't add those constraints statically, you have to write your own brancher that can detect this situation and fix the remaining variables accordingly (which is similar to "symmetry breaking during search").
Perhaps you'll get some ideas by looking into the symmetry breaking literature.

Cheers,
Guido