[gecode-users] Large Neighbourhood Search - Destroying the solution

[Christian Schulte]

Hi Joan,

 

Your decision is absolutely right: the idea to remove (or undo) parts of a
solution is not feasible (this is a very difficult problem as would have to
undo all propagation, search, etc). Starting from scratch is the right idea.

 

There you have two possibilities: either you re-create the model completely
or you try to keep one master copy of your model and then creates clones
from it (I guess you have read how to implement search in Gecode). The
latter one is more efficient. You can also mix both approaches in that you
keep part of your model that is common to all searches in LNS as a master
space and for each new try you create a clone of the master space and then
add those constraints to it (by some member function you can implement) that
are specific to the current try.

 

Does this make sense?

Christian

 

 

--

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

 

From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Joan Sala Reixach
Sent: Thursday, June 14, 2012 2:01 PM
To: users at gecode.org
Subject: [gecode-users] Large Neighbourhood Search - Destroying the solution

 

Hello,

I've been trying to implement this LNS engine. The idea is that once a
solution is found, some part of this solution is destroyed to be re-inserted
in some different way. I don't really understand how this can be done
though. Currently I build a completely new model constraining the variables
that are not destroyed to take the values they had in the previous solution.
Is there some better way to "unassign" a variable though?

Many thanks,
Joan 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20120614/022c9e10/attachment.html>