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

[Mikael Zayenz Lagerkvist]

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/
>



-- 
Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/