[gecode-users] braking symmetries in backtracking

[Mikael Zayenz Lagerkvist]

On Wed, Nov 11, 2009 at 9:08 AM, Alberto Delgado <trosky99 at gmail.com> wrote:
> > 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.
>
> it is kind similar indeed.  I skimmed  the source code of the example
> and if i understood correctly,  when the slab selected as val for an
> order is empty then a choice point with a single alternative is
> created,  avoiding the consideration of the remaining empty slabs as
> possible values for the order. But this is possible to do because the
> slabs are sorted by capacity (I assume),  and the empty slabs are
> always at the end (higher indexes).  Also, since the min value of the
> domain of the variables is the one selected by the heuristic, when an
> empty slab is reached all other slabs have been previously triedfor
> the order.

Just to clear up, the slabs in steel mill can be of different sizes,
but the size is not decided until all things have been packed into it.
Then for every packed size, the loss-array gives how much empty space
is available. This assumes that there is a free choice of the
slab-sizes to use, which I guess is not the case for you.


> That's what I'm doing,  i declared a new attribute in the Choice class
> that i extended in the brancher to keep the bins with the same
> available capacity. In the commit method i constrain the item to be
> different to all the bins  with same available capacity.
> I'm using an std vector to keep the bins,  do i need to have any
> considerations here about memory and where to allocate the vector?

This seems like it should work. All data in a Choice class should be
allocated from the normal heap, it needs to be able to outlive the
space it comes from.


> >When executing the commit-operation, you are
> > not guaranteed to have an equivalent state every time.
>
> Does this happen even if i keep the set of equivalent bins in the Choice object?

The current values of the variables can be different (either because
it is not at fix-point, or because there are non-monotonic
propagators), but it still represents the same subtree. I just meant
to warn you that you can''t compute any information from the variables
during commit.

Cheers,
Mikael
--
Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/