
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