Reflections on generating (disjunctive) cuts

Abstract

We consider the problem of constructing generic supporting hyperplanes to be used within a (branch and) bound-and-cut algorithm. We review some of the properties that these hyperplanes should enjoy. It is generally admitted that they should cut a parasitic point generated during the process. We argue that the advantages of restricting supports to cuts might be over-balanced by their drawbacks. Said otherwise, the cutting paradigm entails the reverse polar, which may not have definite advantages over the ordinary polar (associated with supports). In fact, we believe that moderate attention should be paid to the current relaxed solution, which plays only a temporary role in the process. We propose approaches to constructing supports, in such a way that the cutting property comes out as a by-product. In particular, squeezing the objective function is most desirable; but cuts merely based on the objective function, being parallel to each other all along the iterations, are generally recognized as inefficient. We propose a mechanism to revive the idea.

Keywords

• 52A41
• 90C11