Alternative Strategies for Using Intersection Cuts in Integer Programming.
Abstract
In a previous paper the author introduced a new cutting plane for integer programming, generated from the intersection of n halflines originating at the linear programming optimum (x bar), with the hypersphere S circumscribing a unit hypercube K containing (x bar) and having integer vertices. In this paper the author uses the hypersphere S as a starting point for generating a convex domain C larger than the one defined by S, and such that the boundary of C contains only the feasible integer points of S, while the infeasible ones are contained in the interior of C. This is achieved by generating a family of 'maximal convex extensions' Ci of the solid hypersphere S(+) defined by S, one for each problem constraint and for each face of K. The union of these extended hyperspheres Ci is nonconvex. The main result of the paper is that the convex hull C of this nonconvex set is a convex polytope whose interior contains no feasible vertex of K. Hence C can be used to generate intersection cuts that are obviously stronger than the ones considered earlier. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1970
- Accession Number
- AD0723194
Entities
People
- Egon Balas
Organizations
- Carnegie Mellon University