Accession Number : AD0705196

Title :   A Constraints Shifting Enumerative Algorithm for Integer Programming.

Descriptive Note : Technical rept.,

Corporate Author : PURDUE UNIV LAFAYETTE IND KRANNERT GRADUATE SCHOOL OF INDUSTRIAL ADMINISTRATION

Personal Author(s) : Nghiem,Ph. Tuan

Report Date : 22 APR 1970

Pagination or Media Count : 34

Abstract : Under consideration is a pure integer programming problem. In a wide class of enumerative algorithms integral solutions to the problem are sought for in the intersection of a number of hyperplanes orthogonal to an axis of coordinate. This paper describes an algorithm in which integral solutions are sought for in the intersection of a number of hyperplanes parallel to the delimiting faces of the polyhedral feasible set. A procedure is set up to implicitly enumerate all the possible combinations of intersecting hyperplanes. By an appropriate change of base when necessary, a subproblem defined by such a combination is transformed into a pure integer problem in independent variables. Duality properties of continuous linear programming are used to devise an efficient exploration pattern. (Author)

Descriptors :   (*MATHEMATICAL PROGRAMMING, ALGORITHMS), ITERATIONS

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE