[gecode-users] Large distinct model

[Neill Clift]

Thank you very much for this. In my models using the domain propagation 
in distinct does seem to improve the run-time substantially so the extra 
work does pay off in my case.
I can see this option in the doc now I look for it!
Neill.

On 9/20/2015 3:58 PM, Guido Tack wrote:
> Hi,
>
> there are several different propagators for the distinct constraint in Gecode, and the default one is quite weak and won’t detect these cases. If you post distinct with ICL_DOM as the third argument you will see the behaviour you expect (but you’re right, 6M variables will be stretching it - the complexity of propagating distinct with ICL_DOM is quadratic).
>
> Cheers,
> Guido
>
>> On 21 Sep 2015, at 8:55 am, Neill Clift <neillclift at live.com> wrote:
>>
>> Hi,
>> I have been playing with gecode for a few days and having a lot of fun.
>> My overall goal is to solve a large problem that has close to 6 million values that must be distinct. So kind of like this:
>>
>> IntVarArray b(*this, 5784689, 0, 5784688);
>> distinct(*this, b);
>>
>> Notice that the b's are constrained to be essentially a permutation of 0...5784688.
>>
>> These b values are generated by sets of linear equations derived from a directed acyclic multi-graph.
>> I expect district is a killer. I don't have a hope of attacking this big problem I think. So I am playing with smaller problems. I see gecode searching spaces like this:
>> So 6 b's that are distinct values with a range of 0..5:
>>
>> b{[2..5], [1..4], [1..4], [1..4], [0..3], [0..3]} this should really be b{[5], [1..4], [1..4], [1..4], [0..3], [0..3]}. Maybe I am not using the right way to express what I want and the range and distinct aren't cooperating enough?
>> b{[2..4], [1..4], [1..4], [1..4], [0..3], [0..3]} no 5 at all so this should fail.
>>
>> More complex case:
>>
>> b{5, [3..4], [3..4], [2..4], [0..3], [0..3]} should be b{5, [3..4], [3..4], [2], [0..1], [0..1]}.
>> Computationally I guess it might be very expensive to discover these things. Even if you do discover these things I guess it might be it doesn't help that much.
>> Thanks.
>> Neill.
>>
>> _______________________________________________
>> Gecode users mailing list
>> users at gecode.org
>> https://www.gecode.org/mailman/listinfo/gecode-users