A PSEUDO PRIMAL-DUAL INTEGER PROGRAMMING ALGORITHM.

Abstract

The Pseudo Primal-Dual Algorithm solves the pure integer programming problem in two stages, systemmatically violating and restoring dual feasibility while maintaining an all-integer matrix. The algorithm is related to the Gomory All-Integer Algorithm and the Young Primal Integer Programming Algorithm, differing from the former in the dual feasible stage by the choice of cuts and pivot variable, and from the latter in the dual infeasible stage by the use of a more rigid (and faster) rule for restoring dual feasibility. The net advance in the objective function value produced by the algorithm between two consecutive stages of dual infeasibility is shown to be at least as great as that produced by pivoting with the dual simplex method. Example problems are given that illustrate basic features and variations of the method. (Author)

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1966
Accession Number
AD0644557

Entities

People

  • Fred Glover

Organizations

  • Carnegie Institute of Technology

Tags

DTIC Thesaurus Topics

  • Algorithms
  • California
  • Computer Programming
  • Cooperation
  • Evolutionary Algorithms
  • Heuristic Methods
  • Integer Programming
  • Mathematics
  • Simplex Method

Readers

  • Approximation Theory.
  • Linear Algebra
  • Systems Analysis and Design