Intersection Cuts—A New Type of Cutting Planes for Integer Programming

This paper proposes a new class of cutting planes for integer programming. A typical member of the class is generated as follows. Let X be the feasible set, and x̄ the optimal (noninteger) solution to the linear program associated with an integer program in n -space. Consider a unit hypercube containing x̄ , whose vertices are integer, and the hypersphere circumscribing the cube. This hypersphere is intersected in n independent points by the n halflines originating at x̄ and containing the n edges of X adjacent to x̄ (if x̄ is degenerate, X is replaced by X ′ ⊃ X having exactly n edges adjacent to x̄ ). The hyperplane through these n points of intersection defines a valid cut, the (spherical) intersection cut. The paper gives a simple formula for finding the equation of the hyperplane, discusses some ways of strengthening the cut, proposes an algorithm, and gives a finiteness proof. A straightforward extension of these geometric ideas yields an analogous (cylindrical) intersection cut for the mixed-integer case. A discussion of relations to other work (Young, Gomory) is followed by the introduction of some additional intersection cuts obtained from hypersurfaces other than the sphere or the cylinder. The message of this paper lies, not so much in the particular cuts that it proposes, as in the basically new approach to integer programming that these cuts typify. This approach is geometrically motivated and uses the “local” properties (in the integer-programming sense) of the feasible set.