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):

Report Date:

1970-04-22

Pagination or Media Count:

34.0

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

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE