
Accession Number : AD0723194
Title : Alternative Strategies for Using Intersection Cuts in Integer Programming.
Descriptive Note : Research rept.,
Corporate Author : CARNEGIEMELLON 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