[gecode-users] Value branching heuristics

[Morten Boysen]

Christian Schulte skrev:
> 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.

Ok. If I understand it correctly, this means that it is not possible to 
break ties in the case of equal size domains. So the variable heuristic 
will simply select the variable with the smallest domain, and in case of 
a tie, choose a random one (or the first, or ...).

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

What we want to do is to implement the heuristic mentioned by Peter 
Tiedemann in his PhD thesis (page 78, "Improving support from 
solution"). So after a variable has been chosen, the value heuristic 
should simply choose the first unsupported variable in that domain. If 
all values in the domain have support, we choose a random value (or the 
first, or ...).

Kind regards
Morten Boysen

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