Hi, I just tried your problem, and on my computer (Athlon 64 3500+, Ubuntu Linux, gcc 4.2, debug-build of Gecode 3.2.2) both versions of your program produce a lot of solutions in a short time. What kind of system do you use?
The one with shuffled values is not as fast in the beginning, but that is probably due to weak propagation in combination with a branching heuristic that tries values not in either set. Cheers, Mikael PS. I would recommend that you use the Driver infrastructure for your experiments so that you can easily add various limits (max number of solutions/failures/time) and run the program in Gist. Using Gist is very good for understanding the behaviour of a Gecode model. Printing the search statistics for a completed search is also good when comparing model varieties. 2009/12/16 Holger Winnemoeller <[email protected]> > *QUESTION: How can I solve the following problem for anything but toy > examples?* > > Say, I have the following sets: > > All : {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20} > subA: {0,1,2,3,4} > subB: {5,6,7,8,9} > > If I ask for a subset of "All" which contains 4 elements, of which 2 > elements are from "subA" and 2 elements are from "subB", I get a variety of > results, such as > {0,1,5,6} > {0,1,5,7} > ... > {3,4,8,9} > ... > > etc. > > This works perfectly fine. > > Now, for cases where subA, and subB are not strictly sequential (i.e. > sorted but non-consecutive numbers) > > subA: {4,8,14,16,17} > subB: {0,3,5,10,12} > > The system quickly runs out of steam (maybe not for the toy example here, > but for |All| = 100, |subA| = |subB| = 20, asking for 10 items -- see > attached code). Gecode just keeps computing and never seems to find a > solution. > > Given that the sub-sets are disjoint a solution should really be trivial in > any case (take 50% of one subset and 50% of the other). However, I don't > want to make the assumption that they are disjoint. > > I have attached some demo code for what I am talking about, so you can > experiment with it. > > Thanks for your help! > > Holger. > > _______________________________________________ > Gecode users mailing list > [email protected] > https://www.gecode.org/mailman/listinfo/gecode-users > > -- Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/
_______________________________________________ Gecode users mailing list [email protected] https://www.gecode.org/mailman/listinfo/gecode-users
