[gecode-users] edge-finder propagator

[Christian Schulte]

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