[gecode-users] about the backtrack

[Juan Carlos]

> Now I see, I was confused about how the backtrack works.
>
> The idea is a Local Search Method,  first find a basic solution, and then
> make little changes  till the best solution is found, here are the steps:
>
> 1)choose the best value for each variable (this value is selected by a
> function based on external information), once  all the variables had been
> assigned thats a basic solution.
> 2) Based on that solution , re-assign some variables in order to find a
> better solution in a fast way. The variables that are going to  be
> re-inserted are chosen by a function based on external information and the
> value  is chosen by the same function of step 1.
> 3) repeat 2 till no solution left.
>
> By external information I mean the information of the problem instance.
>
> Now I have some ideas about how to implement this local search but they are
> not clear yet. Any suggestions are welcome.
>
> Thank you.
>
> Juan Carlos
>
>
> On Wed, Jun 18, 2008 at 2:05 AM, Guido Tack <tack at ps.uni-sb.de> wrote:
>
>> Juan Carlos wrote:
>>
>>> In order to find the best solution of  a problem that I'm working on, I
>>> have to branch over an IntVarArray , so  I have created a custom branch with
>>> an heuristic. (like in the black hole or queens example).  And use the BAB
>>> engine.
>>>
>>> This  branching works fine, but it could be improved if the vars that
>>> should be unassingned after  a basic solution is found are selected in a
>>> different way. I mean like a custom backtrack with a function that selects
>>> the best var to be reassigned.
>>>
>>
>> Backtracking in Gecode is based on copying and recomputation, and
>> therefore does not "unassign" any variables.  When you backtrack, you
>> restore a previous state in the search tree (for example that of the parent
>> of the current search node), and then commit to another of its remaining
>> alternatives.  The only way to determine where search proceeds is therefore
>> in the branching.
>>
>> Maybe, if you explain in a little more detail how you would like the
>> search to behave, we can help you cast that idea into your custom branching.
>>
>> Cheers,
>>        Guido
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.ps.uni-sb.de/pipermail/users/attachments/20080618/2fff61e2/attachment.htm>