AN UPPER BOUND FOR THE NUMBER OF DIFFERENT SOLUTIONS GENERATED BY THE PRIMAL SIMPLEX METHOD WITH ANY SELECTION RULE OF ENTERING VARIABLES
Tomonari Kitahara () and
Shinji Mizuno ()
Additional contact information
Tomonari Kitahara: Department of Industrial Engineering and Management, Tokyo Institute of Technology, 2-12-1-W9-62, Oo-Okayama, Meguro, Tokyo, 152-8552, Japan
Shinji Mizuno: Department of Industrial Engineering and Management, Tokyo Institute of Technology, 2-12-1-W9-58, Oo-Okayama, Meguro, Tokyo, 152-8552, Japan
Asia-Pacific Journal of Operational Research (APJOR), 2013, vol. 30, issue 03, 1-10
Abstract:
Recently, Kitahara, and Mizuno derived an upper bound for the number of different solutions generated by the primal simplex method with Dantzig's (the most negative) pivoting rule. In this paper, we obtain an upper bound with any pivoting rule which chooses an entering variable whose reduced cost is negative at each iteration. The upper bound is applied to a linear programming problem with a totally unimodular matrix. We also obtain a similar upper bound for the dual simplex method.
Keywords: Linear programming; the number of basic solutions; pivoting rule; the simplex method (search for similar items in EconPapers)
Date: 2013
References: View complete reference list from CitEc
Citations:
Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595913400125
Access to full text is restricted to subscribers
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:30:y:2013:i:03:n:s0217595913400125
Ordering information: This journal article can be ordered from
DOI: 10.1142/S0217595913400125
Access Statistics for this article
Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao
More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().