On the number of solutions generated by the dual simplex method

On the number of solutions generated by the dual simplex method

0.00 Avg rating0 Votes
Article ID: iaor20123344
Volume: 40
Issue: 3
Start Page Number: 172
End Page Number: 174
Publication Date: May 2012
Journal: Operations Research Letters
Authors: ,
Keywords: duality, simplex algorithm
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 Dantzig’s rule for LP. The bound is comparable with the bound given by Kitahara and Mizuno (in press) for the primal simplex method. We apply the result to the maximum flow problem and get a strong polynomial bound.

Reviews

Required fields are marked *. Your email address will not be published.