Accession Number : AD0778283

Title :   Intersection Cuts from Disjunctive Constraints.

Descriptive Note : Research rept.,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s) : Balas,Egon

Report Date : FEB 1974

Pagination or Media Count : 54

Abstract : Intersection or convexity cuts can be viewed as being implied by a disjunction. Replacing the disjunction by more complex logical conditions leads to a more general class of cutting planes, which subsumes most of the earlier cuts proposed for integer and nonconvex programming, while improving some of them; and which also includes a variety of new cuts with several desirable features. For one thing, these cuts are computationally cheap. For another, they have coefficients with different signs, and are therefore less likely than the earlier cuts to produce degeneracy when used in a dual algorithm. The authors' approach can take full advantage of certain frequently occurring types of problem structure, and produce relatively inexpensive, yet powerful cuts for a variety of combinatorial and other nonconvex problems. (Modified author abstract)

Descriptors :   *Linear programming, Inequalities, Convex sets, Combinatorial analysis, Theorems, Quadratic programming

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE