
Accession Number : AD0728021
Title : Integer Programming and Convex Analysis.
Descriptive Note : Research rept.,
Corporate Author : CARNEGIEMELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Personal Author(s) : Balas,Egon
Report Date : APR 1971
Pagination or Media Count : 93
Abstract : Convex analysis can be useful in integer programming as a means of generating information about the integer neighborhood of the linear programming optimum x, defined as the set of (integer) vertices of a unit cube K containing x. The first intersection cuts were based on information about the integer neighborhood within the cone defined by the problem constraints that are binding at x, while ignoring the nonbinding constraints (except for those that define facets of K). This paper uses properties of polar sets to generate cuts based on information about the feasible integer neighborhood, i.e., about all problem constraints intersecting K. Cuts of this type can be gradually tightened by using information that is normally generated by almost any integer programming method; therefore they can be suitably combined with any implicit enumeration or branch and boundtype procedure. The results are valid for general pure or mixed integer programs, but they are expected to be most helpful in the (pure or mixed) 01 case. A combination of this approach with the asymptotic theory of integer programming is discussed. (Author)
Descriptors : (*MATHEMATICAL PROGRAMMING, THEOREMS), LINEAR PROGRAMMING, CONVEX SETS, OPTIMIZATION, INEQUALITIES, ALGORITHMS
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE