[gecode-users] edge-finder propagator

[Jan Kelbel]

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

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: jobshop.cpp
URL: <http://www.ps.uni-sb.de/pipermail/users/attachments/20080820/b6b77951/attachment.asc>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: edgeFinder.cpp
URL: <http://www.ps.uni-sb.de/pipermail/users/attachments/20080820/b6b77951/attachment.txt>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: edgeFinder.h
URL: <http://www.ps.uni-sb.de/pipermail/users/attachments/20080820/b6b77951/attachment-0001.asc>