[gecode-users] Value branching heuristics

[boysen at itu.dk]

Hi,

Thank you for the reply.

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

Ok. I assume the way I can easily get the index of the variable that is
being branched on is because the heuristic also acts as a variable
heuristic, and hence knows which variable is being branched on. Is this
correct?

If this is the case, then what we want to do is to implement the
Minimum-Remaining-Value (also known as fail-first. See the section on
variable ordering:
http://ktiml.mff.cuni.cz/~bartak/constraints/ordering.html) heuristic as
the variable ordering (possibly using some way to break ties) and then use
the custom value selection heuristic afterwards. Is this the way to go
about it?

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

The heuristic I am referring to is the one Bartak calls "succeed first" in
the section on value ordering:
http://ktiml.mff.cuni.cz/~bartak/constraints/ordering.html. Is the
information for that heuristic missing in the solver?

Kind regards
Morten Boysen


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