[gecode-users] about the backtrack

[Mauricio Toro]

Hello Juan Carlos, Guido and all,
Can you give some information about how to run the BAB search with a time
limit?
I am interesting in that too.

Thanks,

Mauricio

2008/6/18 Juan Carlos <carlvall at gmail.com>:

> 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
>>
>>
>
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>
>


-- 
Mauricio Toro Bermudez
Estudiante de Ingeniería de Sistemas
Pontificia Universidad Javeriana, Colombia

Stagiare à l'Ircam
1, place Igor-Stravinsky 75004 Paris,
France de 2008 à 2009



-- 
Mauricio Toro Bermudez
Estudiante de Ingeniería de Sistemas
Pontificia Universidad Javeriana, Colombia

Stagiare à l'Ircam
1, place Igor-Stravinsky 75004 Paris,
France de 2008 à 2009
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.ps.uni-sb.de/pipermail/users/attachments/20080619/737c003b/attachment.htm>