The Principles of Cutting-Plane Theory: Part I.
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
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
- Operations Research