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

[Holger Winnemoeller]

Mikael,

thank you for your answer! Your second mail was spot-on!

I've added "branch(*this, specialSelected, SET_VAL_MIN_INC);" as the last
line in CreateAndRequestCategory

and the code runs like a charm!

I should really try to get Gist working, as I have a feeling that it will
demystify what to me is currently branching Voodoo.

FYI, my system is Dell Intel Core Duo E8400 @ 3GHz with 4GB of RAM on
WindowsXP professional, running Gecode 3.2.0 (x86). It's interesting, though
maybe not surprising, that Gecode seems to run so much faster on your
system. Do you think it's related more to the version of Gecode, the
machine, or the OS? In any case, the correct answer is obviously not to
upgrade the hardware, but to insert the branching statement :-)

Cheers,
Holger.

On Wed, Dec 16, 2009 at 1:39 AM, Mikael Zayenz Lagerkvist
<zayenz at gmail.com>wrote:

> Hi,
>
> I thought a bit more about your model, and my suggestion would be for
> you to branch on the set of specialSelected set variables first,
> before branching on the resultSet. This will be much more efficient,
> since that will decide the values that should be included in resultSet
> directly.
>
> Cheers,
> Mikael
>
> On Wed, Dec 16, 2009 at 8:51 AM, Mikael Zayenz Lagerkvist
> <zayenz at gmail.com> wrote:
> > 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/<http://www.ict.kth.se/%7Ezayenz/>
> >
>
>
>
> --
> Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/<http://www.ict.kth.se/%7Ezayenz/>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20091216/755d371e/attachment.htm>