[gecode-users] about the backtrack

[Guido Tack]

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