The Intersection Cut - a New Cutting Plane for Integer Programming

摘要

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)