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 ().