
Accession Number : AD0699534
Title : THE INTERSECTION CUT  A NEW CUTTING PLANE FOR INTEGER PROGRAMMING.
Descriptive Note : Research rept.,
Corporate Author : CARNEGIEMELLON 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 nspace. 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