[gecode-users] Memory problem using Gecode for local search

[Guido Tack]

Hi,
have you verified (e.g. using Gist) that your search tree actually has that shape?  If yes, could you post a short self-contained example code that shows this behavior?

Cheers,
Guido


On 6 Nov 2011, at 12:58, TeXitoi wrote:

> Hi!
> 
> I'm trying to use Gecode 3.7.1 to do local search.  My decision
> variables are in a IntVarArray machine_m.
> 
> I do about that :
> 
>  /* constraints... */
>  IntArgs sol_l(machine_m.size());
>  /* creating sol_l with sol_l[i] = ...; */
>  count(*this, machine_m, sol_l, IRT_EQ, machine_m.size() - 1);
>  branch(*this, machine_m, INT_VAR_RND, INT_VAL_MIN);
> 
> if I am correct, the tree will be totally balanced on the right,
> e.g. choice(0) will always be a solution, and choice(1) will be the
> rest of the solutions. I use INT_VAL_MIN to limit the fragmentation of
> my decision variables.
> 
> I enumerate the different solutions about like that:
> 
>  Search::Options options_l;
>  options_l.c_d = 1;
>  options_l.clone = false;
>  DFS<GecodeSpace> search_l(pSpace_l, options_l);
>  GecodeSpace *pSpace_l = 0;
>  while ((pSol_l = search_l.next()) != 0) {
>      /* working with pSol_l */
>      delete pSol_l;
>  }
> 
> I use c_d = 1 because my tree have this special shape that make
> choice(0) always be a solution.  I thought that the search tree will
> be memory efficient because only 2 Gecode::Space must be stored at the
> same time because of the shape of the search tree, but I can see that
> it takes a lot of memory on big instances (even if I comment
> c_d=...).  I can see on "top" the memory growing about linearly with
> time.
> 
> It seems that I do not have any memory problem in my program because
> if I use Search::MemoryStop(256 * 1024 * 1024) and let my local search
> running all the night, my program is only growing between about 30MB
> and 270MB.
> 
> Why do I have this behavior? What did I do wrong? How to solve my
> problem (enumerating every solutions that have only 1 variable
> different from a given solution in constant memory)?
> 
> Thanks in advance.
> 
> -- 
> Guillaume Pinot                               http://www.texitoi.eu
> 
> « Il semble que la perfection soit atteinte non quand il n'y a plus
> rien à ajouter, mais quand il n'y a plus rien à retrancher. »
>                      -- Antoine de Saint-Exupéry, Terre des hommes
> 
> ()  ASCII ribbon campaign      -- Against HTML e-mail
> /\  http://www.asciiribbon.org -- Against proprietary attachments
> 
> 
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users