[gecode-users] Porting attributed variables

[Guido Tack]

Maria Garcia de la Banda wrote:

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

I see.  So you will need a special search engine anyway, and the  
search has to have access to the variables.  I think the key to the  
implementation will be to identify variables with their indexes in an  
array, so that you can just use additional arrays for storing the  
attributes.  If the attributes are just needed down one branch, a  
global array will do.  If not, the array must be inside the space and  
copied.

> So, I could use a Shared structure (like the array) to keep track of  
> the
> info of all variables not yet labeled.

Yes. I'd just use an array of info data structures, and it only  
contains actual data at the indexes of the unassigned variables.

> Could I somehow maintain pointers
> to where exactly each variable appears in the structure? (mmh, I  
> think I
> am mixing paradigms).

Is it an info field per variable, and the info should again contain  
pointers to other variables?  I think identifying variables with their  
array indexes should make all of this simple.

Cheers,
	Guido