Next: Parallelizing BCP Up: The Cut Management Module Previous: Maintaining and Scanning the Contents
For several reasons, it may be desirable to have multiple cut pools. When there are multiple cut pools, each pool is initially assigned to a particular node in the search tree. After being assigned to that node, the pool services requests for cuts from that node and all of its descendants until such time as one of its descendants gets assigned to another cut pool. After that, it continues to serve all the descendants of its assigned node that are not assigned to other cut pools.
Initially, the first cut pool is assigned to the root node. All other cut pools are unassigned. During execution, when a new node is sent to be processed, the tree manager must determine which cut pool the node should be serviced by. The default is to use the same cut pool as its parent. However, if there is currently an idle cut pool process (either it has never been assigned to any node or all the descendants of its assigned node have been processed or reassigned), then that cut pool is assigned to this new node. All the cuts currently in the cut pool of its parent node are copied to the new pool to initialize it, after which the two pools operate independently on their respective subtrees. When generating cuts, the NP module sends the new cuts to the cut pool assigned to service the node during whose processing the cuts were generated.
The primary motivation behind the idea of multiple cut pools is two-fold. First, we want simply to limit the size of each pool as much as possible. By limiting the number of nodes that a cut pool has to service, the number of cuts in the pool will be similarly limited. This not only allows cut storage to spread over multiple processors, and hence increases the available memory, but at the same time, the efficiency with which the cut pool can be scanned for violated cuts is also increased. A secondary reason for maintaining multiple cut pools is that it allows us to limit the scanning of cuts to only those that were generated in the same subtree as the current search node. As described above, this helps focus the search and should increase the efficiency and effectiveness of the search. This idea also allows us to generate locally valid cuts, such as the classical Gomory cuts (see [28]).