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: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf > Of Jan Kelbel > Sent: Wednesday, August 20, 2008 3:15 PM > To: [EMAIL PROTECTED] > 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 > > _______________________________________________ Gecode users mailing list [EMAIL PROTECTED] https://www.gecode.org/mailman/listinfo/gecode-users
