Cutting Planes for Relaxations of Integer Programs.
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
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
- Operations Research