[gecode-users] Set constraints working for sequential data, but not non-sequential data. Ideas?

[Mikael Zayenz Lagerkvist]

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 <holger.winnemoeller at gmail.com>

> *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
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>
>


-- 
Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20091216/48ffd7f6/attachment-0001.htm>