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:

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

Descriptors:

• *Integer programming
• *Nonlinear programming
• Convex sets
• Inequalities
• Algorithms
• Theorems

Subject Categories:

• Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE