[gecode-users] about the backtrack

[Juan Carlos]

Exactly! is large neighborhood search. And I get your idea is very clever.
thanks.

Juan Carlos.

On Wed, Jun 18, 2008 at 3:08 PM, Guido Tack <tack at ps.uni-sb.de> wrote:

> Juan Carlos wrote:
>
>  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.
>>
>
> That sounds a lot like large neighborhood search.  I'd try using a plain
> BAB search to find a solution, and then start a nested search, where you
> create a new space, assign some of the variables, and run some limited BAB
> (e.g. using a time limit).  Once you find a better solution there, you reuse
> that for the original, "master" BAB search. If you don't find a better
> solution within the time limit, just go on in the master search.
> To implement this, you'll probably have to implement your own search
> engines or at least modifiy ours, but it should be possible.
>
> Cheers,
>        Guido
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.ps.uni-sb.de/pipermail/users/attachments/20080618/d32716ee/attachment.htm>