Eliminating Columns in the Simplex Method for Linear Programming.

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1987
Accession Number
ADA190428

Entities

People

  • Yinyu Ye

Organizations

  • Stanford University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Programming
  • Determinants (Mathematics)
  • Ellipsoids
  • Evolutionary Algorithms
  • Iterations
  • Linear Programming
  • Military Research
  • Operations Research
  • Optimization
  • Simplex Method
  • United States
  • United States Government

Fields of Study

  • Mathematics

Readers

  • Operations Research