
Accession Number : AD0716264
Title : Intersection Cuts from Maximal Convex Extensions of the Ball and the Octahedron.
Descriptive Note : Research rept.,
Corporate Author : CARNEGIEMELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Personal Author(s) : Balas,Egon
Report Date : AUG 1970
Pagination or Media Count : 88
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)
Descriptors : (*CONVEX SETS, *LINEAR PROGRAMMING), MATRICES(MATHEMATICS), SPHERES, TRANSFORMATIONS(MATHEMATICS), OPTIMIZATION, THEORY
Subject Categories : Theoretical Mathematics
Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE