[gecode-users] edge-finder propagator -- problem solved
Jan Kelbel
kelbelj at fel.cvut.cz
Tue Aug 26 17:26:29 CEST 2008
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
More information about the gecode-users
mailing list