[gecode-users] braking symmetries in backtracking

[Mikael Zayenz Lagerkvist]

Hi,

This sounds like the situation in Steel Mill Slab design. There, any slab
that has not had anything allocated to it yet is considered symmetrical.
That is, there is an interchangeable values symmetry on the identities of
the slabs. There are several ways to handle this kind of symmetry. Which
approach is the best depends on your problem, and on the heuristic you use
for search.

The example in Gecode for Steel Mill uses the technique from "The Steel Mill
Slab Design Problem Revisited", Van Hentenryck and Michel, CPAIOR 2008 to
break the symmetry in the Brancher. Another possibility is to add
constraints that break the symmetry explicitly. For an example on how to do
this, see for example "Breaking Value Symmetry", Walsh, AAAI-2008.

With regards to your proposed solution, you would need to record all the
information that you need to redo the decision in the Choice object (e.g.,
the set of symmetrical bins). When executing the commit-operation, you are
not guaranteed to have an equivalent state every time.

Hope this helps,
Mikael

On Tue, Nov 10, 2009 at 12:05 PM, Alberto Delgado <trosky99 at gmail.com>wrote:

> 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
>
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>



-- 
Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.ps.uni-sb.de/pipermail/users/attachments/20091110/82e911a5/attachment.htm>