Accession Number : AD0699534

Title :   THE INTERSECTION CUT - A NEW CUTTING PLANE FOR INTEGER PROGRAMMING.

Descriptive Note : Research rept.,

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

Personal Author(s) : Balas,Egon

Report Date : OCT 1969

Pagination or Media Count : 33

Abstract : A new cutting plane is proposed for integer programming, generated as follows. Let X be the feasible set, and x bar the optimal (noninteger) solution of the linear program associated with an integer program in n-space. A convex polytope X' is defined, such that X included in X', x bar is an optimal vertex of X', and X' has exactly n vertices adjacent to x bar (whether x bar is degenerate or not). Consider now the unit cube containing x bar, whose vertices are integer, and the hypersphere through the vertices of this cube. This hypersphere is intersected in n linearly independent points by the n halflines originating at x bar and containing the n vertices of X' adjecent to x bar. The hyperplane through these n points of intersection (of the halflines with the hypersphere) defines a valid cut (the intersection cut), which does not belong to the class of cuts introduced by Gomory. A simple formula is given for finding the equation of the hyperplane. A comparison of the intersection cut to one particular Gomory cut is given in geometric terms. Possible ways of strengthening the cut are discussed: 'integerization' of the pivot row, choice of the 'best' unit cube among those containing x bar. An algorithm is then proposed and a convergence proof is given. Extension of the new cut to the mixed integer case, a discussion of relations to other work and a numerical example conclude the paper. (Author)

Descriptors :   (*MATHEMATICAL PROGRAMMING, GEOMETRY), LINEAR PROGRAMMING, NUMERICAL ANALYSIS, CONVEX SETS, ALGORITHMS, THEOREMS

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE