|
Alps
2.0.2
|
Description here is a brief introduction to Abstract Library for Parallel tree Search (Alps). For theoretical details of parallel tree search see
A Library Hierarchy for Implementing Scalable Parallel Search Algorithms
ALPS: A Framework for Implementing Parallel Search Algorithms
Computational Experience with a Software Framework for Parallel Integer Programming
Documentation here can be considered as a condensed summary of all the work listed. It is also more focused in the implementation of the ideas presented in the listed publications.
Alps is designed to conduct parallel tree search. It is an abstract library for this purpose, i.e., it does not assume much (hence flexible) on the tree search problem of its user. Any tree search problem can be implemented as an application on top of the Alps, ie. DFS, BFS, Dijkstra's algorithm or Branch and Bound search for discrete optimization problems.
A basic unit of work in ALPS is an entire subtree. This means that each worker is capable of processing an entire subtree autonomously. Each broker is responsible for tracking a list of subtrees that it is responsible for. The hub broker dispenses new candidate nodes (leaves of one of the subtrees it is responsible for) to the workers (worker broker receives it) as needed and track their progress. When a worker receives a new node, it treats this node as the root of a subtree and begins processing that subtree, stopping only when the work is completed or the hub broker instructs it to stop. Periodically, the worker informs the hub broker of its progress.
A tree search can be abstracted as defining the following,
To define these, user need to inherit corresponding Alps classes and implement related virtual functions, given in the paranthesis. Once these are defined Alps has different strategies to cary the search related tasks, which node to process next, which node to branch, etc.
Alps comes with two examples, Abc and Knap. Abc is a branch and cut solver, Knap is a knapsack solver. Both of them are implemented on top of Alps, where Alps carries a classical branch and bound/cut type of search to find optimal solutions.
For parallel search to work, user should implement encode/decode virtual functions in the corresponding user types,
AlpsNodeDesc holds subproblem data specific to the node, tree node has other infromation related to tree search (index, depth, branching info). AlpsTreeNode::desc_ is of type AlpsNodeDesc and keeps the problem data of the node. This design is intended to keep problem data separated from the node data related to tree search. It is for convenience.
AlpsModel, AlpsTreeNode and AlpsSolution all have AlpsKnowledge as a base class. Instances of these classes are considered as knowledges generated during a search for the optimal solution and they are traded between different processors.
All AlpsModel, AlpsTreeNode, AlpsNodeDesc and AlpsSolution have virtual encode() and decode() funtions. Corresponding sub-classes of user app should implement these virtual functions. encode() function encodes the object into an AlpsEncoded object. decode() function decodes information from a given AlpsEncoded object. Alps knowledge brokers sends/receives these AlpsEncoded instances.
Each processor has an AlpsKnowledgeBroker instance responsible with coordinating search with other processors' brokers.
Each AlpsKnowledge instance has a pointer that points to its broker.
Knowledge broker should be able to follow created knowledges. In current design user apps can create knowledges in TreeNode::branch() functions. Do we want that?
What about a mechanism where user app requests broker to create a new AlpsKnowledge object and then fills the data. This way knowledge broker can keep an account of the knowledges created.
AlpsKnowledgeBroker::getBestNode returns the most promising node, i.e. best quality node. AlpsKnowledgeBroker::getBestQuality() returns to the quality of the best solution found (quality of incumbent solution). This should be fixed. Moreover AlpsKnowledgeBroker::getBestNode does a search to locate the best node, this is not necessary and should be fixed (just update the best node whenever new nodes are created).
1.8.17