A CONSTRAINTS SHIFTING ENUMERATIVE ALGORITHM FOR INTEGER PROGRAMMING.

摘要

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)