Accession Number : ADA190428

Title :   Eliminating Columns in the Simplex Method for Linear Programming.

Descriptive Note : Technical rept.,

Corporate Author : STANFORD UNIV CA SYSTEMS OPTIMIZATION LAB

Personal Author(s) : Ye, Yinyu

PDF Url : ADA190428

Report Date : Nov 1987

Pagination or Media Count : 15

Abstract : This document proposes a column-eliminating and a lower bound updating techniques for the simplex method for linear programming. A pricing criterion is developed for checking whether or not a dual hyperplane corresponding to a column intersects a simplex containing all of the optimal dual feasible solutions. If the dual hyperplane has no intersection with this simplex, we can eliminate the corresponding column from the constraints. As the simplex method iterates, the working constraint matrix eventually eliminates all columns except those that are in at least one optimal basis. Keywords: Algorithms; Ellipsoid; Karmarkar method.

Descriptors :   *SIMPLEX METHOD, ALGORITHMS, ELLIPSOIDS, LINEAR PROGRAMMING, ITERATIONS, OPTIMIZATION

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE