Cutting Planes for Relaxations of Integer Programs.
Abstract
The author gives a theoretical characterization of all valid cutting-planes, prior to any relaxation, by means of concepts of the subadditive theory introduced by Ellis Johnson. Attention is then focused on those aspects of this general approach which Balas has shown to yield cuts that are easily computed, usually, by second-order computations. Generalizations of results of Balas and Glover on conjunctive and disjunctive constraints, using concepts from propositional logic are obtained. The author determined the theoretical limits of these easily-computed cutting-planes, characterizing these classes of cutting-planes as containing the facets of many different kinds of relaxations of integer programs, including, in theory, the integer program itself. (Modified author abstract)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1974
- Accession Number
- AD0783059
Entities
People
- Robert G. Jeroslow
Organizations
- Carnegie Mellon University