Accession Number : AD0716264

Title :   Intersection Cuts from Maximal Convex Extensions of the Ball and the Octahedron.

Descriptive Note : Research rept.,

Corporate Author : CARNEGIE-MELLON 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