THE INTERSECTION CUT - A NEW CUTTING PLANE FOR INTEGER PROGRAMMING.
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
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
- Operations Research