Integer Programming and Convex Analysis.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1971
- Accession Number
- AD0728021
Entities
People
- Egon Balas
Organizations
- Carnegie Mellon University