[gecode-users] Porting attributed variables

[Maria Garcia de la Banda]

Guido Tack wrote:

> Do you want to do the extra pruning in the branching?  E.g., collect  
> some attributes for particular variables, and then perform the  
> branching based on these attributes?  This reminds me of branchings  
> for scheduling, where propagators determine precedences between  
> activities, and the branching uses this precedence information to  
> order activities.  Is that a similar scenario?

What we are considering is a restricted kind of symmetry breaking during
search (i.e., at each search node after a failed assignment we try to
prune extra values based on the known symmetries). While some symetries
are easy to break efficiently, others require (for efficiency) direct
access from the variable to a data structure that indicates in which
variables symmetries it appears (kind of reverse indexing). We could
always lookup every element of the data structure to find where the
variable appears, but that is too slow.

> With reflection you can only get information about the variable  
> domain, but you can't add extra information. 

Aha. So that is off.

> But you can simply  
> introduce an additional data structure that collects the attributes,  
> and that is shared between the branching and whoever is responsible  
> for maintaining the attributes (e.g. some propagators).

The datastructure must be maintained through the entire search, mmmh,
actually, this is not true, it only needs to be maintained down in the
search tree , all other branches are kind of independent of siblings.

> You'd only have to make sure that a) the data structure is copied  
> properly, and b) that the branching is still compatible with  
> recomputation.  For a), you could abuse a SharedArray and always set  
> the bool share flag to false during update.  For b), you have to  
> record at each branching step which prunings your branching does, and  
> encode them in the BranchingDesc, so that later recomputation steps  
> can perform the exact same prunings again.
> 
> That's just the overall idea, if you need more concrete hints how to  
> implement this, just ask. 

So, I could use a Shared structure (like the array) to keep track of the
info of all variables not yet labeled. Could I somehow maintain pointers
to where exactly each variable appears in the structure? (mmh, I think I
am mixing paradigms).

Cheers, Maria