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: [email protected] [mailto:[email protected]] On Behalf Of Guido Tack Sent: Tuesday, March 27, 2012 12:35 AM To: Chuong Cc: [email protected] 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 [email protected] https://www.gecode.org/mailman/listinfo/gecode-users _______________________________________________ Gecode users mailing list [email protected] https://www.gecode.org/mailman/listinfo/gecode-users
