[gecode-users] edge-finder propagator -- problem solved

[Jan Kelbel]

Dear Christian,

yes, I am considering to contribute to Gecode. However, I do not know, 
when the propagator will be ready.

Cheers
Jan

Christian Schulte napsal(a):
> Dear Jan,
> 
> What I meant to ask but forgot: do you consider contributing your edge-finder to Gecode?
> 
> Cheers
> Christian
> 
> PS: No luck so-far with the IDE madness. The problem is not UNICODE, though...
> 
> PPS: I am always relieved if a problem solves "itself" (from our perspective), so that we are not to blame ;-)
> 
> -----Original Message-----
> From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf Of Jan Kelbel
> Sent: Tuesday, August 26, 2008 5:26 PM
> To: Filip Konvička; users at gecode.org
> Subject: Re: [gecode-users] edge-finder propagator -- problem solved
> 
> Hi,
> 
> finally, I found out the bug in our edge-finder propagator code -- in
> the propagation algorithm, that we previously checked more than once.
> In file EdgeFinder.cpp, line 68, there should be:
>         if((( tasks[i].start.min() + P + tasks[i].processingTime )) >
>            tasks[k].start.max() + tasks[k].processingTime ){ //line 21
> instead of
>         if((( tasks[i].start.min() + P + tasks[i].processingTime )) >
>            tasks[k].start.max() ){ //line 21
> 
> i.e. "+ tasks[k].processingTime" was missing.
> For now, it computes Cmax of FT6 jobshop benchmark correctly, so we need
> to make more testing.
> 
> I forgot to mention, the edge-finder propagator I posted here only finds
> activities that should be first (so it is only half of the edge-finder).
> 
> Thanks for all your comments,
> Jan
> 
> Filip Konvička napsal(a):
>> Hi Jan,
>>
>>> The implementation of the O(n^2) edge-finder of [Baptiste,Le Pape,
>>> Nuijten] seemed to us easier to implement than the O(n log n) algorithm
>>> of Vilim, which uses binary trees.
>>> So we chose the O(n^2), as it was the first propagator we were implementing.
>>>
>>> Maybe we should try to implement that O(n log n) version.
>> The binary trees are easy - implement them using vectors: compute the
>> next larger power of two (N), make a vector of N*2-1 items, the tree
>> leaves start at index N-1, parent node of node I is (I-1)/2.
>>
>> In fact, efficient computation of the next power of two is what I can
>> share with you because it is already part of the FloatVar implementation
>> I posted earlier today: it is in float/float/bi/prop_linear.icc, look
>> for "namespace __Utils".
>>
>> Theta-lambda trees are usable not just for propagators, but also for
>> branchings (you can easily compute firsts/lasts using theta-lambda trees).
>>
>> Hope this helps,
>> Filip
>>
>>
>> _______________________________________________
>> Gecode users mailing list
>> users at gecode.org
>> https://www.gecode.org/mailman/listinfo/gecode-users
> 
> 
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>