Optimization Online


On the Number of Solutions Generated by the Dual Simplex Method

Tomonari Kitahara (kitahara.t.ab***at***m.titech.ac.jp)
Shinji Mizuno (mizuno.s.ab***at***m.titech.ac.jp)

Abstract: In this short paper, we give an upper bound for the number of different basic feasible solutions generated by the dual simplex method with the most negative pivoting rule for LP. The bound is comparable with the bound given by Kitahara and Mizuno (2010) for the primal simplex method. We apply the result to the maximum flow problem and get a strong polynomial bound.

Keywords: Dual simplex method, Linear programming, Basic feasible solutions, Maximum flow problem.

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: To appear in Operations Research Letters. Available online 11 January 2012.


Entry Submitted: 02/06/2011
Entry Accepted: 02/06/2011
Entry Last Modified: 02/15/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society