The Convex Hull in Convex Separable Integer Programming.
Abstract
It remains impractical to solve most large scale integer programming problems exactly. Approximate techniques which have been proposed are often some variant of rounding the solution to the associated continuous version of the problem. Unfortunately, for problems with many small variables, such a procedure may produce very poor, often infeasible results. For the convex separable case, the procedure presented here rather finds exact solutions to an associated problem where the constraints have been modified slightly. This procedure of 'approximating the constraints' is especially interesting if the constraints have been only estimated in the first place, as the modified solution is very efficient in the sense that it lies on the convex hull of all possible optimal solutions when the constraint vector is treated as a free parameter. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1971
- Accession Number
- AD0726314
Entities
People
- Claude G. Henin
- Thomas E. Norton
Organizations
- Carnegie Mellon University