Accession Number : AD0644557

Title :   A PSEUDO PRIMAL-DUAL INTEGER PROGRAMMING ALGORITHM.

Descriptive Note : Research rept.,

Corporate Author : CARNEGIE INST OF TECH PITTSBURGH PA MANAGEMENT SCIENCES RESEARCH GROUP

Personal Author(s) : Glover,Fred

Report Date : DEC 1966

Pagination or Media Count : 32

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)

Descriptors :   (*ALGORITHMS, *LINEAR PROGRAMMING), SIMPLEX METHOD, MATRICES(MATHEMATICS), OPTIMIZATION

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE