[gecode-users] Question: stop during a search

[Christian Schulte]

Actually there is one other approach: Just branch on a and b but not c and d
(by posting an appropriate brancher). Then when you give this to a search
engine you, say e1, you would get a space, say s1, from e1 where only a and
b are assigned. Then, you could post a new branching in s1 where you branch
on c and d. Then you could use a search engine on s1 to give you a solution
where also c and d are assigned. Then, you could request a solution from e1
again where the next assignment for a and b is produced.

Best
Christian

--
Christian Schulte, www.ict.kth.se/~cschulte/


-----Original Message-----
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Guido Tack
Sent: Tuesday, March 27, 2012 12:35 AM
To: Chuong
Cc: users at gecode.org
Subject: Re: [gecode-users] Question: stop during a search

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
_______________________________________________
Gecode users mailing list
users at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users