[gecode-users] braking symmetries in backtracking

[Alberto Delgado]

Hi Mikael,

Thanks for your answer.

> 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.

My case is a little bit more complicated,  i think,  since i can't
guarantee that all possible bins have been tried before for a item,
and that just the ones with the same available capacity as the one the
heuristic is currently considering are the ones left.


> 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.

The symmetry i described is dynamic since the available capacity of the bins
change all the time.  I don't think a PRECEDENCE constraint can be applied
here and I want to see if i can do something else first without
starting to consider
GE-trees.

>
> 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).

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?

>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?

Best,

Alberto