The Principles of Cutting-Plane Theory: Part I.
Abstract
The paper develops a fundamental result, which reveals a construction through which all valid cutting-planes for integer programming, and other programming areas, are obtained by the use of subadditive functions in real space and their supremum directional derivatives at the origin. The fundamental result is simply a characterization theorem and does not reveal directly how to obtain cuts. The paper proceeds beyond this theorem, to develop many methods of constructing a wide variety of subadditive functions, often with special properties. When this latter work is completed, the paper shows how the general theory is adequate to account for all the well-known cutting-planes of the literature, and how the process of isolating the subadditive function 'behind' a known cutting-plane can lead to straightforward generalizations of this function, and from there on to new cutting-planes. (Modified author abstract)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1974
- Accession Number
- AD0779955
Entities
People
- Robert G. Jeroslow
Organizations
- Carnegie Mellon University