[CHiPPS] Alps help

[Yan Xu]

Hi Nathan,

I can only provide very limited support for CHiPPS due to various reasons, but will try my best to answer your questions.

To my knowledge, the only other framework for parallel general tree search algorithms is the Parallel Implicit Graph Search Library (PIGSeL), which was developed by Peter Sanders. However, I don't know if you can get the code. There is a parallel branch-and-bound library called PEBBL by  Eskstein, Phillips and Hart. The code of PEBBL can be downloaded.

As to the first question, Alps relies on node numbers, msg received and sent to update search states and terminate search. When we wrote it, we didn't expected INT is not big enough. To fix it, may need use CoinBigIndex (long, or long long) defined in CoinFinite.hpp in CoinUtils/src. Because your problem produces many nodes, I don't know if parameter tuning will help. So, I suggest you try to change many of the counts to CoinBigIndex, and see if that will fix this.

As to the second question, it seems the solLimit is not implemented correctly in Alps. You may take a look at the implementation of NodeLimit in AlpsSubtree.c,

Alps shares subtrees instead of nodes during load balancing. Of course, a node can be a subtree. Maybe when choose a subtree to share, can skip those are pregnant.

Hope this helps,
Yan






From: nathan.kallus at gmail.com [mailto:nathan.kallus at gmail.com] On Behalf Of Nathan Kallus
Sent: Tuesday, May 03, 2011 1:25 AM
To: Yan Xu
Subject: Alps help

Hi Yan,

I'm not sure if you are still maintaining Alps, but I hope you can answer some of my questions about it. I've found Alps extremely useful. I haven't found any other generic parallel-ready tree search frameworks. Do any others exist that you know of? I would think such a framework very natural and common.

As to my questions, firstly, I am having issues where when I run on a case with a really huge tree Alps gets stuck, or at least I think it's stuck. It reports, for example, the line "Alps0096I Node 2147475765: left(4165 / 0), msg(s 496609241, r 496609241), inter 0, no sol, 6198 sec." again and again and again repeatedly with the only numbers changing being the wall clock and the send/recv count. The node number remains the same and as do the work quantities. Now, the node number is suspiciously close to MAX_INT so I'm guessing therein lies the problem. Before I go in and try and hack into the code the option for more nodes (since there aren't even that many nodes active at a time since I'm doing depth first), I was wondering if you either have an easy fix via parameters or some such or perhaps if you can help me patch the code and point me in the right directions.

Second, I was wondering if there are known issues with solLimit (I set it =1) when running in parallel. It seems that very often some other process will continue to work for quite a long time past the point that a solution was found (and Alps even reports that master requested to stop everything). I even tried to include a check at the beginning of process() that queries getKnowledgeBroker() and fathoms immediately if there is a solution but this didn't fix it. Got any suggestions?

Third, is there anyway to prevent nodes from being MPI_send'ed when they're pregnant after process() and before branch(). I have code that produces the offspring in process via a complicated procedure that checks feasibility and branches all in one (because quantities computed are necessary for both). It seems wasteful to encode these nodes when they're pregnant and they have to encode the information for their offspring's alpsnodedesc too.

Thanks for the help and thanks for making Alps. I'd really appreciate your input on this especially on my first problem as it is rendering my code completely useless since it was essentially written for these huge cases.

Cheers,

Nathan.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://list.coin-or.org/pipermail/chipps/attachments/20110504/9a48fa4b/attachment.html