DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click
HERE to register or log in.
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
Report Date:
1974-03-01
Pagination or Media Count:
101.0
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
Distribution Statement:
APPROVED FOR PUBLIC RELEASE