A Constraints Shifting Enumerative Algorithm for Integer Programming.

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)

Document Details

Document Type
Technical Report
Publication Date
Apr 22, 1970
Accession Number
AD0705196

Entities

People

  • Ph. Tuan Nghiem

Organizations

  • Purdue University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Computer Programming
  • Evolutionary Algorithms
  • Heuristic Methods
  • Integer Programming
  • Integrals
  • Interdisciplinary Science
  • Linear Programming
  • Mathematical Programming
  • Mathematics
  • Operations Research

Fields of Study

  • Mathematics

Readers

  • Control Systems Engineering.
  • Operations Research