search

coin-or / CHiPPS-ALPS

This is the Abstract Library for Parallel Search (ALPS), the abstract base layer of the COIN-OR High Performance Parallel Search framework.
Eclipse Public License 1.0
9 stars 8 forks source link

Avoid searching the pool for finding the best node, while we know the… #4

Closed SaTahernejad closed 5 years ago

SaTahernejad commented 5 years ago

… best node is node[0](just for AlpsSearchTypeBestFirst, AlpsSearchTypeBreadthFirst and AlpsSearchTypeHybrid)

aykutbulut commented 5 years ago

Hi Sahar,

Thanks for the PRs. I feel like there is more room to improve.

  1. In AlpsNodePool, nodes are stored in a priority queue and we should never iterate over the nodes stored in any of the search strategies.
  2. AlpsNodePool inherits AlpsKnowledgePool and I think more of the implementations can move to the AlpsKnowledgePool. Moreover, I feel like getting a template pool class might work better instead of having pool classes for subtree, node and solution separately. Then, we can use something like

AlpsKnowlegePool sol_pool; AlpsKnowlegePool subtree_pool;

I think these are worth considering while we are on it.

Aykut

tkralphs commented 5 years ago

It's true that the nodes should always be stored in a priority queue with a prioritization that means we don't need to iterate to find the best. That is sort of the whole point of the design---the search strategy should be the priority scheme of the queue, by definition. Is there any search strategy currently implemented for which this is not the case? Looks like best estimate was left out of the if statement. I guess the difficulty with that one is that the prioritization might change dynamically, aftter the nodes are added to the queue.

And yes, the original idea was that all knowledge pool should be implemented in the same way, but I think that ideal was discarded somewhere along the way because of practical considerations. We could think about trying to fix that, but I'm not sure how easy it would be.