The Convex Hull in Convex Separable Integer Programming.
CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP
Pagination or Media Count:
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
- Operations Research