[gecode-users] braking symmetries in backtracking

[Alberto Delgado]

Hi all,

I have a modeling/implementation question that maybe somebody  has
faced before,  or that gecode developers could help me answer.  I'm
trying to implement a symmetry-breaking strategy that works when the
search engine backtracks.  I have a set of items that need to be
allocated in a set of bins (bin-packing problem) and I branch over the
items to find for each item a possible bin where it can be allocated.

When it is no possible to allocate an item in a selected bin (the
search engine backtracks), i'd like to avoid trying  to allocate the
item in bins with the same available capacity as the bin that has just
been discarded,  since i already know it won't be possible.  This
should be as simple as identifying the bins with the same available
capacity as the bin selected by the branching,  and posting rel
constraints to remove these bins from the domain of the item. I
thought about doing this in the commit method,  and instead of just
posting one constraint to remove the bin that couldn't allocate the
item being considered,  also remove the bins with the same available
capacity.
The problem is that if i follow this approach i think i'll screw up
recomputation ,  and that's just if i'm able to get the information i
need to the commit method.

Do you guys have any suggestions on how to implement this in gecode?
any hints are welcome.


Best,

Alberto