Accession Number : AD0723194

Title :   Alternative Strategies for Using Intersection Cuts in Integer Programming.

Descriptive Note : Research rept.,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s) : Balas,Egon

Report Date : JUN 1970

Pagination or Media Count : 24

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)

Descriptors :   (*MATHEMATICAL PROGRAMMING, CONVEX SETS), LINEAR PROGRAMMING, NUMERICAL ANALYSIS, OPTIMIZATION, THEOREMS

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE