[gecode-users] Value branching heuristics

[Christian Schulte]

Hi,

yes, that information is not available in the solver. That is not a
shortcoming of the solver, though. This information is only available for
specialized solvers fully based on extensional representations used during
propagation. Modern solvers such as Gecode use intensional propagators to
accomodate for global constraints.

What I did not really understand: why do you not use the predefined
branchings (posted with branch)? Unless you also want to do something for
value selection they should be enough.

Christian

--
Christian Schulte, www.ict.kth.se/~cschulte/


-----Original Message-----
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of boysen at itu.dk
Sent: Tuesday, December 09, 2008 1:58 PM
To: users at gecode.org
Subject: Re: [gecode-users] Value branching heuristics

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



_______________________________________________
Gecode users mailing list
users at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users