[gecode-users] about the backtrack

[Christian Schulte]

That’s explained in the documentation. Look for stop objects.

 

Christian

 

--

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

 

From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Mauricio Toro
Sent: Thursday, June 19, 2008 7:59 AM
To: gecode list
Subject: [gecode-users] about the backtrack

 


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/e7ecec95/attachment.htm>