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