Accession Number : AD0783059
Title : Cutting Planes for Relaxations of Integer Programs.
Descriptive Note : Technical rept.,
Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Personal Author(s) : Jeroslow,R. G.
Report Date : JUN 1974
Pagination or Media Count : 101
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)
Descriptors : *Integer programming, *Nonlinear programming, Boolean algebra, Set theory, Inequalities, Mathematical logic, Topology, Theorems, Algorithms
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE