The Cut Management Module

The concept of a cut pool was first suggested by Padberg and Rinaldi [29], and is based on the observation that in BCP, the inequalities 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 manager functions as an auxiliary cut generator. More explicitly, here are the functions of the cut pool module:

• Receive cuts generated by other modules and store them.
• Receive an LP solution and return a set of cuts which this solution violates.
• Periodically purge ``ineffective'' and duplicate cuts to control its size.