next up previous external Back to SYMPHONY Home Page
Next: The Cut Generator Process Up: Parallelizing Branch and Cut Previous: The Master Process

The Cut Pool Process

The concept of a cut pool was first suggested by Padberg and Rinaldi [19], and is based on the observation that in branch and cut, the valid inequalities (also called cuts since they ``cut off'' part of the current polyhedron) which are generated while processing a particular node in the search tree are also generally valid and potentially useful at other nodes. Since generating these cuts is usually a relatively expensive operation, the cut pool maintains a list of the ``best'' or ``strongest'' cuts found in the tree so far for use in processing future subproblems. Hence, the cut pool functions as an auxiliary cut generator. More explicitly, here are the functions of the cut pool process:

Functions Performed by the Cut Pool Process



Ted Ralphs
Thu Jun 8 14:31:17 CDT 2000