[gecode-users] Value branching heuristics

[Morten Boysen]

Hi

I have to program a value selection heuristic for a configurator that is 
being implemented on top of the FlatZincGecode space. This means that 
all variables are in an IntVarArray and in a BoolVarArray. What we need 
to do is simply to choose the a value to branch on that has not been 
verified as valid. Therefore, we have the following requirements:

1) We need to know the index of the specific value we are branching on, 
when the heuristic is invoked. This is needed, because the index is used 
as a key into a map that contains the valid domains computed so far.

2) We have no need to create any branching for variables (so we do not 
need to modify the standard variable ordering).

3) It would be nice if the heuristic van easily be integrated with the 
standard least-constraining-value heuristic, so the heuristic first 
tries the least-constraining-value of the values that have not been 
verified as valid, and if all values have always been verified as valid, 
the heuristic should simply work as the standard 
least-constraining-value heuristic.

I have seen two examples on how to implement this: The first method is 
to inherit from Gecode::Branching and implement a heuristic (Question: 
If we use this, do we also have to implement a variable selection 
heuristics?). The second method is to use the Gecode::ViewValBranching 
class. Given the requirements above, what would you recommend as the way 
to implement the heuristic?

Kind regards
Morten Boysen