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

Egon Balas

Operations Research, 1971, vol. 19, issue 1, 19-39

Abstract: 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.

Date: 1971
References: Add references at CitEc
Citations: View citations in EconPapers (31)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.19.1.19 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:19:y:1971:i:1:p:19-39

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().