A New Steepest Edge Approximation for the Simplex Method for Linear Programming

Artur Świętanowski

Abstract

The purpose of this paper is to present a new steepest edge (SE) approximation scheme for the simplex method. The major advantages are its simplicity of recurrences and implementation, low computational overhead (compared to both the exact SE method and the DEVEX approximation scheme), and surprisingly good performance. The paper contains a brief account of the exact SE algorithm, the new recurrences developed in the same framework and some discussion on the possible reasons for the method's apparent success. Finally, numerical experiments are presented to assess the practical value of the method. The results are very promising.
Author Artur Świętanowski IAiIS
Artur Świętanowski,,
- The Institute of Control and Computation Engineering
Journal seriesComputational Optimization and Applications, ISSN 0926-6003, 1573-2894
Issue year1998
Vol10
No3
Pages271-281
Keywords in EnglishConvex and Discrete Geometry, Operation Research/Decision Theory, Operations Research, Mathematical Programming, optimization, Simplex method, Statistics, general, steepest edge pricing
DOIDOI:10.1023/A:1018317206484
URL http://link.springer.com/article/10.1023/A%3A1018317206484
Score (nominal)0
Citation count*6 (2013-01-30)
Cite
Share Share



* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back