Accession Number : AD0728021

Title :   Integer Programming and Convex Analysis.

Descriptive Note : Research rept.,

Corporate Author : CARNEGIE-MELLON 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 non-binding 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 bound-type 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) 0-1 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