[gecode-users] Value branching heuristics

[Mikael Zayenz Lagerkvist]

Hi,

I would suggest that you implement your own branching the same way
some of the examples do it. You will need to implement some kind of
variable selection yourself, but this is easy to do. While it is
possible to implement a new value selection heuristic for
ViewValBranch (and thus to reuse the variable selection part), the
interfaces are not geared towards custom branchings. In particular,
ViewValBranch will not give you the index of the variable the
selection is to be made for.

I'm not sure what kind of least constraining value heuristic you are
referring to in part three of your question. There is no such generic
value selection heuristic in Gecode, since the information needed is
not readily available in any propagator based constraint programming
system. There might be some custom way for your specific problem to
make such a heuristic though.

Hope this helps,
Mikael

On Mon, Dec 8, 2008 at 11:41 PM, Morten Boysen <boysen at itu.dk> wrote:
> 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
>
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>



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