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

[TeXitoi]

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