Intersection Cuts from Maximal Convex Extensions of the Ball and the Octahedron.
Abstract
Intersection cuts represent a new type of cutting planes for integer programming. Given an integer program, the basic idea of these cuts is to intersect the boundary of some convex set circumscribing the unit cube that contains a basic feasible, but noninteger, solution x bar to the associated linear program, with the n halflines originating at x bar and defined by the problem constraints that are tight for x bar. The n intersection points then define a valid cut. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1970
- Accession Number
- AD0716264
Entities
People
- Egon Balas
Organizations
- Carnegie Mellon University