Accession Number : AD0726314

Title :   The Convex Hull in Convex Separable Integer Programming.

Descriptive Note : Research rept.,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s) : Henin,Claude G. ; Norton,Thomas E.

Report Date : APR 1971

Pagination or Media Count : 22

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)

Descriptors :   (*LINEAR PROGRAMMING, CONVEX SETS), APPROXIMATION(MATHEMATICS), NUMERICAL ANALYSIS, THEOREMS, OPTIMIZATION

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE