Back to SYMPHONY Home Page
The cut pool's primary job is to receive a fractional solution from an LP process and return cuts from the pool that are violated by it. The cuts are stored along with two pieces of information--the level of the tree on which the cut was generated, known simply as the level of the cut, and the number of times it has been checked for violation since the last time it was actually found to be violated, known as the number of touches. The number of touches a cut has is used as a simplistic measure of its effectiveness. Since the pool can get quite large, the user can choose to scan only cuts whose number of touches is below a specified threshold and/or cuts that were generated on a level at or above the current one in the tree. The idea behind this second criteria is to try to avoid checking cuts that were not generated ``nearby'' in the tree, as they are less likely to be effective. Any cut that was generated at a level in the tree that is below the level of the current node must have been generated in a different part of the tree. This is admittedly a naive method. All duplicate cuts, as well as all cuts whose number of touches has exceeded a pre-specified threshold are periodically purged from the pool to keep it as small as possible.