[gecode-users] edge-finder propagator

[Jan Kelbel]

Hi Christian,

thank you for the reply. I forgot to mention that we are implementing 
disjunctive edge-finder. From the paper of Mercier and Van Hentenryck, I 
figured out that cumulative edge-finder of Nuijten is incomplete. But 
thank you, this information will be useful later when we would like to 
implement the cumulative version.

I tried to run the program with the "-c-d 1" options, the results remain 
the same, only number of propagations, failures, clones etc changed.

Then, I did not mean that Gecode is buggy. We just do not know where the 
bug is.

I will send you more info about the allocation bug later.

Cheers
Jan

Christian Schulte napsal(a):
> Hi Jan,
> 
> before I actually start, there is another paper you might want to read for
> edge-finding:
> 	Edge Finding for Cumulative Scheduling
> 	Luc Mercier, Pascal Van Hentenryck
> 	http://joc.journal.informs.org/cgi/content/abstract/20/1/143
> 
> What might be the case, is that your edge finder is non-monotonic (that is,
> when run on variables with larger domain it does more pruning as if run on
> variables with tighter domain). You can try what happens if you switch off
> recomputation (as you are inheriting from the example class, just give -c-d
> 1 on the command line).
> 
> Then, that this is a bug in Gecode is very very very unlikely. Gecode does
> not support non-monotonic propagators (well, it will in 3.0, we just added
> that). Even Gecode 2.2.0 (which will be out next week, it is ready and just
> needs packaging) will have a silent fix (not mentioned in the changelog) to
> support non-monotonic propagators. If you want, you can check 2.2.0 out of
> the repository.
> 
> Then, I cannot reproduce the allocation bug... You could send me a log of
> what you did exactly and what happens? As said, I am using MSVC 2008 myself
> and cannot reproduce it.
> 
> Cheers
> Christian
> 
> --
> Christian Schulte, www.ict.kth.se/~cschulte/
> 
> 
> -----Original Message-----
> From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
> Of Jan Kelbel
> Sent: Wednesday, August 20, 2008 3:15 PM
> To: users at gecode.org
> Subject: [gecode-users] edge-finder propagator
> 
> Hi,
> 
> we are trying to implement edge-finder propagator. The algorithm is
> implemented according to the book Baptiste,Le Pape, Nuijten (2001)
> Constraint-Based Scheduling.
> We also took some Gecode coding inspiration from the cumulatives propagator.
> 
> The problem we have, is that for FT6 job-shop benchmark (we did not try more
> benchmarks yet), the edge-finder combined with BAB branching founds a
> solution that has Cmax>OptimalCmax, but is marked as an optimum, since BAB
> founds no better solution.
> However, when a constraint Cmax < 57 is added (optimum for FT6 is 55), see
> line 96 of jobshop.cpp, then a solution with correct Cmax is found.
> We do not know if the bug is in the edge-finder algoritm (not much likely),
> in the Gecode stuff of the propagator code, or in the Gecode itself.
> 
> Maybe someone who already implemented some edge-finder variation could help
> us.
> 
> The code of the whole program is attached (about 300 lines of code). The
> problem object Jobshop is inherited from the object Example, ie. it is
> necessary to include "examples/support.hh" and to link it with "example.o"
> and "options.o" from examples/support directory of the Gecode distribution.
> We use Gecode 2.1.1 binary distribution, Visual C++ 2008 and Windows XP.
> 
> There are some TODOs we know about, but we think that are not the source of
> the problem:
> * some methods of the propagator should be inlined
> * vector used for sorting tasks should not be created each time
> propagate() method is called - instead it should be created in propagator
> constructor
> * improve input function to be able to compute jobshops with different
> number of jobs and tasks (n != m)
> 
> 
> 
> I also obtained the same memory allocation problem, that was already
> reported by Nick Hindle on July 21st
> http://www.gecode.org/gecode-users/2008-July/002344.html
> The problematic code is in file jobshop.cpp line 115:
>    os << S[i] << ", ";  //raises memory allocation exception
>    os << S[i].val() << ", ";  //this works
> 
> 
> Thanks,  Jan
> 
>