Accession Number : AD0779955
Title : The Principles of Cutting-Plane Theory: Part I.
Descriptive Note : Research rept.,
Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Personal Author(s) : Jeroslow,R. G.
Report Date : MAR 1974
Pagination or Media Count : 101
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)
Descriptors : *Integer programming, *Nonlinear programming, Convex sets, Inequalities, Algorithms, Theorems
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE