Convexity Cuts and Cut Search

This note focuses on two new and related cut strategies for integer programming: the “convexity-cut” and “cut-search” strategies. The fundamental notions underlying the convexity-cut approach are due to Richard D. Young and Egon Balas, whose “hypercylindrical” and “intersection” cuts provide the conceptual starting points for the slightly more general framework developed here. We indicate the utility of our framework (and hence the importance of the original Young and Balas ideas) by specifying a variety of new cuts that can be obtained from it. The second new strategy, cut search, shares with the convexity-cut strategy the notion of generating a cut by passing a hyper-plane through the terminal endpoints of edges extended from the vertex of a cone. However, whereas the convexity-cut approach determines the extensions of these edges by reference to a convex set that contains the vertex of the cone in its interior, the cut-search approach determines these extensions by reference to associations between certain “proxy” sets of points (e.g., collections of hyperplanes) and “candidate solutions” to the integer program. The cut-search approach typically involves more work than the convexity-cut approach, but offers the chance to identify feasible solutions in the process, and can sometimes also yield somewhat stronger cuts than the convexity cuts.