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