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 <trosk...@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 > us...@gecode.org > https://www.gecode.org/mailman/listinfo/gecode-users > -- Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/
_______________________________________________ Gecode users mailing list us...@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users
