[gecode-users] Managing memory footprint for large problems

[Zaremby, David]

I work with Ashis and I have been playing with a few experiments. What I am seeing is that the memory is constantly climbing at every node as I traverse down the left hand side despite very high computation parameters int c_d=1000000, int a_d=1000000).  I have posted the stack trace for the code to maybe give some insight. I see the clone method being called for each node which seems odd since I believe it should only be doing choice, status, and commits. I have reverted back from our custom brancher to a simple built in of branch(*this, resources, INT_VAR_MIN_MIN, INT_VAL_MIN). If I had to venture a guess from exploring the code, it is because the workingspace is never being initialized and thus it keeps trying to initialize it for the first time. The memory growth seems to scale with the number of propagators. If I reduce my scheduling constraints but leave my number of choice the same I get a smaller memory footprint for each clone. The same behavior happens for the default c_d and a_d values.

	AutomatedScheduler++.exe!Scheduler::Scheduler(bool share=true, Scheduler & s={...})  Line 65	C++
 	AutomatedScheduler++.exe!Scheduler::copy(bool share=true)  Line 79 + 0x37 bytes	C++
 	GecodeKernel-3-3-1-d-x86.dll!Gecode::Space::_clone(bool share=true)  Line 470 + 0x18 bytes	C++
 	GecodeGist-3-3-1-d-x86.dll!Gecode::Space::clone(bool share=true, Gecode::CloneStatistics & __formal={...})  Line 2369	C++
>	GecodeGist-3-3-1-d-x86.dll!Gecode::Gist::SpaceNode::recompute(Gecode::Gist::BestNode * curBest=0x1dde3558, int c_d=1000000, int a_d=1000000)  Line 87 + 0x14 bytes	C++
 	GecodeGist-3-3-1-d-x86.dll!Gecode::Gist::SpaceNode::acquireSpace(Gecode::Gist::BestNode * curBest=0x1dde3558, int c_d=1000000, int a_d=1000000)  Line 173 + 0x14 bytes	C++
 	GecodeGist-3-3-1-d-x86.dll!Gecode::Gist::SpaceNode::getNumberOfChildNodes(Gecode::Support::BlockAllocator<Gecode::Gist::VisualNode,10000> & na={...}, Gecode::Gist::BestNode * curBest=0x1dde3558, Gecode::Gist::Statistics & stats={...}, int c_d=1000000, int a_d=1000000)  Line 291	C++
 	GecodeGist-3-3-1-d-x86.dll!Gecode::Gist::TreeCanvas::inspectCurrentNode(bool fix=true, int inspectorNo=-1)  Line 605 + 0x34 bytes	C++
 	GecodeGist-3-3-1-d-x86.dll!Gecode::Gist::TreeCanvas::mouseDoubleClickEvent(QMouseEvent * event=0x017bd100)  Line 1129	C++


David Zaremby
Senior Software Engineer
LSS / Strategic Products
 
Lockheed Martin Simulation, Training & Support
12506 Lake Underhill Road, MP-823
Orlando, FL 32825
-----Original Message-----
From: Maity, Ashis K 
Sent: Monday, April 12, 2010 8:48 AM
To: Zaremby, David
Subject: FW: [gecode-users] Stopping Gecode Engine gracefully

FYI!

-----Original Message-----
From: Guido Tack [mailto:tack at gecode.org] 
Sent: Saturday, April 10, 2010 5:41 AM
To: Maity, Ashis K
Subject: Re: [gecode-users] Stopping Gecode Engine gracefully

Hi Ashis,

would you mind posting your message to the mailing list?  I think this might interest others, too.  Anyway, here's my answer.

Maity, Ashis K wrote:
> Yes, that was also my understanding in terms of setting c_d and a_d. I was not clear in my write up. I mean to say that I am setting higher c_d so that it can use less memory and not run out of memory. But one thing you made clear is that even if I do not set a_d it will default to 2. I probably missed seeing that in documentation. I was hoping the default behavior of a_d will be like setting it higher than c_d (that is a_d is not used).

The defaults are independent of each other (i.e. c_d is always 8 and a_d is always 2).  We tried to come up with something more automatic, but it's not clear how that's supposed to work.

> In any event, yes my problem runs out of memory with default c_d and a_d. And it does run out with other combination of c_d and a_d as well (say c_d = 20000 and a_d = 10000 or c_d = 200 and a_d = 100). Strange thing is even with varied c_d & a_d combination, my memory consumption graph rises almost similar way (as observed from Windows Task Manager). To give you some background, I am working on Scheduler problems that contain hundreds of tasks with large start domains and have many choices on resource. Previously I was using Mozart/Oz, but recently transferred my code to Gecode hoping it will help my memory problem. It appeared to do so when it ran a problem with 600 tasks rather quickly. But when I try to run a problem with 1000 tasks, it crashes within a couple of minutes saying "heap memory is exhausted". It may be that my memory problem is exhausting before it comes to choices and that's why c_d and a_d value are not making much of a difference! Can you please comment on!
>  this?


You could try running your problem in Gist and double-click the root node (that will create exactly one instance of your problem and not perform any search).
If that exhausts the memory, it's clearly a problem in the model itself.  Actually, if that doesn't exhaust the memory, then setting c_d/a_d very high should definitely at least change the memory behavior, because with a very high c_d/a_d, the required memory is pretty much exactly twice the memory of the root node.

If it turns out to be a problem in the root node already, there's several things one could try.  First of all, you should check how many variables you create.  If it's quadratic in the problem size (e.g. one Boolean for every pair of tasks could be typical for scheduling problems), that would explain the difference between 600 and 1000 tasks - I'm also working on scheduling problems right now and I've run into similar issues.  Being very careful not to create too many temporary variables is very important in this case.
Then, it's sometimes possible to replace a set of propagators with one custom propagator.  That can help a lot if there's a large number (say, quadratically many) of these propagators.
Finally, reformulating the problem might help, or trying to solve a relaxation (e.g. aggregating several tasks into bigger meta-tasks to make the problem smaller), but that's of course very problem-specific and sometimes simply impossible.

Cheers,
	Guido

-- 
Guido Tack, http://people.cs.kuleuven.be/~guido.tack/