Convexity Cuts and Cut Search

Fred Glover
Additional contact information
Fred Glover: University of Colorado, Boulder, Colorado

Operations Research, 1973, vol. 21, issue 1, 123-134

Abstract: 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.

Date: 1973
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.21.1.123 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:21:y:1973:i:1:p:123-134

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().