Intersection Cuts from Disjunctive Constraints.
Abstract
Intersection or convexity cuts can be viewed as being implied by a disjunction. Replacing the disjunction by more complex logical conditions leads to a more general class of cutting planes, which subsumes most of the earlier cuts proposed for integer and nonconvex programming, while improving some of them; and which also includes a variety of new cuts with several desirable features. For one thing, these cuts are computationally cheap. For another, they have coefficients with different signs, and are therefore less likely than the earlier cuts to produce degeneracy when used in a dual algorithm. The authors' approach can take full advantage of certain frequently occurring types of problem structure, and produce relatively inexpensive, yet powerful cuts for a variety of combinatorial and other nonconvex problems. (Modified author abstract)
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1974
- Accession Number
- AD0778283
Entities
People
- Egon Balas
Organizations
- Carnegie Mellon University